Volltextsuche

[jandelph]

Hallo,
ich möchte eine art wörterbuch erstellen. dabei soll wenn der benutzer z.b. 'go' eingibt, alle wörter erscheinen die mit 'go' anfangen.
brauch ich dafür eine datenbank? bin leider erst ein anfänger...
Danke!
LG
Jan

[DeddyH]

Du kannst natürlich eine Datenbank benutzen, bei überschaubarer Datenmenge ist die allerdings nicht nötig. Delphi hat da ganz nette Funktionen parat wie AnsiStartsText/AnsiStartsStr, um nur ein Beispiel zu nennen.

[edit] Sry, Willkommen in der DP :dp: [/edit]

[patti]

Hi und willkommen in der DP ;)

Naja, eine "echte" Datenbank brauchst du dafür nicht unbedingt. Im einfachsten Fall kannst du eine StringList nehmen, in der alle Wörter drin stehen. Wenn der Benutzer Buchstaben eingibt, durchläufst du alle Einträge der StringList und schaust bei jedem Eintrag, ob er mit den Buchstaben, die der Benutzer eingegeben hat, beginnt (z.B. mittels Pos). Das ist allerdings alles andere als performant (sobald ein paar Einträge in der StringList stehen, kann das Suchen so u.U. ewig dauern). Wenn die Wörter in der StringList nach dem Alphabet sortiert vorliegen, dann kann man das ganze schon deutlich beschleunigen, aber auch das dürfte einigermaßen Zeit in Anspruch nehmen...
Die beste Lösung besteht wahrscheinlich darin, einen lexikalischen Suchbaum zu erstellen, in dem alle Worte gespeichert werden und der eine solche Funktionalität bietet. Ich hab das schonmal gemacht, allerdings in Java und die Sourcen hab ich grad auch nicht zur Hand. Ich meine aber, dass Luckie (User aus der DP) sowas mal für Delphi erstellt hat...

[DeddyH]

Das finde ich für einen Anfänger allerdings reichlich übertrieben. Die angesprochene TStringlist sollte es vorerst auch tun. Solange da nicht Abermillionen Einträge drinstehen kann man wahrscheinlich mit der Performance auch leben.

[patti]

Zitat:

Zitat von jandelph (Beitrag 1128091)

alle wörter erscheinen die mit 'go' anfangen.
Jan

Kommt halt drauf an, was man unter "alle Wörter" versteht...

[jandelph]

Hey! danke für eure schnellen antworten! ich verstehe leider nicht wie ich die AnsiStrings anwenden soll :(

[himitsu]

AnsiStrings?

Wenn du AnsiStartsText meinst, dann steht alles Nötige in der OH.
http://docwiki.embarcadero.com/VCL/d...AnsiStartsText (ich hoffe AnsiStartsText gab es schon im Delphi 7)

AnsiStartsStr wird genauso verwendet, wie Pos, nur daß es ein, für deine Anforderungen, geeigneteres Funktionsergebnis liefert.

Delphi-Quellcode:

if Pos('go', S) > 0 then

// entspricht genau (nur daß AnsiStartsStr schneller ist, da es nicht gen ganzen String durchsucht)

if AnsiStartsStr('go', S) then

StartsStr = beginnt (engl: start) der String (str) mit dem angebenem Wert?

und bei dieser Art der Funktionen gilt dann noch:
...Str = unter Berücksichtigung der Groß-/Kleinschreibung
...Text = Groß-/Kleinschreibung ignorieren

[DeddyH]

Ich habe mal schnell eine kleine Klasse zusammengehackt, die intern eine sortierte Stringliste verwendet (allerdings ganz einfach über Sorted auf true, das dürfte also case-sensitive sein).

Delphi-Quellcode:

type
  TWoerterbuch = class
  strict private
    FWoerter: TStringlist;
  public
    constructor Create;
    destructor Destroy; override;
    function Add(const Wort: string): integer;
    procedure Clear;
    procedure Delete(Index: integer);
    procedure Filter(const Suchwort: string; FilterResult: TStrings);
  end;

...

implementation

...

uses StrUtils;

{ TWoerterbuch }

function TWoerterbuch.Add(const Wort: string): integer;
begin
  Result := FWoerter.Add(Wort);
end;

procedure TWoerterbuch.Clear;
begin
  FWoerter.Clear;
end;

constructor TWoerterbuch.Create;
begin
  inherited;
  FWoerter := TStringlist.Create;
  FWoerter.Sorted := true;
end;

procedure TWoerterbuch.Delete(Index: integer);
begin
  FWoerter.Delete(Index);
end;

destructor TWoerterbuch.Destroy;
begin
  FWoerter.Free;
  inherited;
end;

procedure TWoerterbuch.Filter(const Suchwort: string; FilterResult: TStrings);
var
  i: integer;
begin
  Assert(Assigned(FilterResult));
  FilterResult.BeginUpdate;
  try
    FilterResult.Clear;
    for i := 0 to FWoerter.Count - 1 do
      if (Suchwort = '') or AnsiStartsText(Suchwort, FWoerter[i]) then
        FilterResult.Add(FWoerter[i]);
  finally
    FilterResult.EndUpdate;
  end;
end;

Das ist natürlich die billigste Variante, läuft auf meinem Rechner allerdings erstaunlich performant (Athlon II X4 2,8 GHz, 2 GB RAM).

@jandelph: Ich erwarte natürlich nicht, dass Du den Code verstehst, trotzdem kannst Du ihn ja einmal gedanklich nachvollziehen und zu unklaren Begriffen in der Hilfe nachlesen. Bei weiteren Fragen einfach fragen ;)

[edit] Wobei mir einfällt: das Sorted kann man sich hier eigentlich auch sparen, da in dieser Variante sowieso die ganze Liste durchlaufen wird. Aber durch geschickte Abbruchbedingungen kann man das ja unterbinden, was die ganze Sache wohl enorm beschleunigen kann ;) [/edit]

[himitsu]

Zitat:

Zitat von DeddyH (Beitrag 1128101)

das dürfte also case-sensitive sein

Aber nur, wenn TStringList.CaseSensitive auf true gesetzt wurde.

Du könntest über TStringList.Find den Anfang innerhalb der sortierten Liste suchen, also das was als Erstes dem gesuchten Wortanfang "ähnlich" ist.

[jandelph]

danke!
AnsiStartsStr funktioniert nicht, der sagt mir 'undeklarierter Bezeichner AnsiStartsStr'!
muss ich dafür irgentetwas in die uses liste einfügen?

[patti]

Und warum lässt du die StringList sortieren? Du läufst ja trotzdem die komplette Liste durch, also macht das Sortieren gar keinen Sinn - sondern kostet nur Zeit beim Insert/Delete.

Edit: Sehe gerade dein Edit...

[DeddyH]

StrUtils, steht auch im Source ;)

[himitsu]

Zitat:

Zitat von DeddyH (Beitrag 1128106)

StrUtils, steht auch im Source ;)

Und in der (verlinkten) OH. :angle2:

[DeddyH]

Um mein Edit (und pattis Einwand) jetzt nicht so doof da stehen zu lassen:

Delphi-Quellcode:

procedure TWoerterbuch.Filter(const Suchwort: string; FilterResult: TStrings);
var
  i: integer;
  MatchingFound: Boolean;
begin
  Assert(Assigned(FilterResult));
  FilterResult.BeginUpdate;
  try
    (* Noch keine Treffer gefunden *)
    MatchingFound := false;
    FilterResult.Clear;
    for i := 0 to FWoerter.Count - 1 do
      if (Suchwort = '') or AnsiStartsText(Suchwort, FWoerter[i]) then
        begin
          FilterResult.Add(FWoerter[i]);
          MatchingFound := true;
        end
      else
        (* Wenn bereits Treffer gefunden wurden, der aktuelle String
           aber nicht mehr passt, sind auch keine weiteren Treffer mehr
           zu erwarten -> Schleife verlassen *)
        if MatchingFound then
          break;
  finally
    FilterResult.EndUpdate;
  end;
end;

[himitsu]

Um den Anfang auch noch wegzuoptimieren...

Delphi-Quellcode:

procedure TWoerterbuch.Filter(const Suchwort: string; FilterResult: TStrings);
var
  i: Integer;
begin
  Assert(Assigned(FilterResult));
  FilterResult.BeginUpdate;
  try
    FilterResult.Clear;
    if Suchwort <> '' then begin
      FWoerter.Find(SearchWord, i);
      while (i < FWoerter.Count) and AnsiStartsText(Suchwort, FWoerter[i]) do
        FilterResult.Add(FWoerter[i]);
    end else
      FilterResult.AddStrings(FWoerter);
  finally
    FilterResult.EndUpdate;
  end;
end;

(ich hoffe es funktioniert)

Delphi-Quellcode:

function TDictionary.Filter(const SearchWord: string; FilterResult: TStrings; OnlyAtTheBeginningOfWords: Boolean): Boolean;
var
  i: Integer;
begin
  Assert(Assigned(FilterResult));
  FilterResult.BeginUpdate;
  try
    FilterResult.Clear;
    if SearchWord <> '' then begin
      FListOfWords.Find(SearchWord, i);
      while (i < FListOfWords.Count)
          and ((not OnlyAtTheBeginningOfWords and AnsiContainsText(SearchWord, FListOfWords[i]))
            or (OnlyAtTheBeginningOfWords and AnsiStartsText(SearchWord, FListOfWords[i]))) do 
        FilterResult.Add(FListOfWords[i]);
    end else
      FilterResult.AddStrings(FListOfWords);
  finally
    Result := FilterResult.Count <> 0;
    FilterResult.EndUpdate;
  end;
end;

Und wenn man nun noch Names und Values verwendet, bekommt man auch noch die Übersetzung mit rein.

[haentschman]

:roll: ganz ehrlich ?
und wenn es nur 1000 Wörter sind würde ich eine Query auf eine Tabelle in einer DB loslassen. Diese Performance ist glaub ich kaum zu toppen...
...und das alles ohne Kopfschmerzen :stupid: man kann alles unnötig verkomplizieren...

[himitsu]

Wobei es notfalls auch ohne Datenbank ginge.
Also einfach nur ein TClientDataSet. :angle: (da gibt es Insert, Post, Locate und einen Filter)

Aber zum Lernen hat die manuelle Pascal-Variante doch auch ihre Vorteile.

[DeddyH]

Find funktioniert für Teilstrings? Da muss ich was überlesen haben.

[himitsu]

Zitat:

Zitat von DeddyH (Beitrag 1128139)

Find funktioniert für Teilstrings?

Jain, eigentlich nicht.

Find findet nur ganze Strings. :angle2:

Aber wenn es nichts findet, dann gibt es dennoch die Stelle zurück, wo das Wort zu finden wäre, wäre es vorhanden gewesen.
Also die perfekte Stelle, um dort mit der Suche zu beginnen. (oder um ein Insert zu machen, so wie es praktisch vorgesehn ist)

Aber notfalls könnte man das ja nochmal ausprobieren, um ganz sicher zu gehn. :oops:

[haentschman]

...findest du immer eine Ausrede ? :lol:

[patti]

Hab gerade eben mal einen Suchbaum geschrieben (allerdings in Java) und hinsichtlich der Geschwindigkeit mit der TWoerterbuch-Klasse von DeddyH verglichen. Hab das ganze mal mit dem deutschen Ubuntu-Wörterbuch getestet (über 300.000 Wörter) und beispielhaft nach dem Präfix "Katze" gesucht (53 Treffer!). Das ganze hab ich auf einem Netbook laufen lassen (Single-Core, 1,7 GHz). Die Lösung von DeddyH benötigt bei mir im Schnitt etwa 80 ms, meine Suchbaum-Implementierung 2-3 ms. Wenn es also nicht auf extreme Geschwindigkeit ankommt oder der Umfang des Wörterbuchs gering ist, dann ist die Lösung von DeddyH auf jeden Fall voll in Ordnung (vor allem, weil sie einfacher zu implementieren und zu verstehen ist) :thumb: Allerdings ließe sich durch eine etwas komplexere Implementierung als Suchbaum doch noch einiges an Geschwindigkeit rausholen ;)

Nur so als Info, denn das hier:

Zitat:

Zitat von DeddyH

Das finde ich für einen Anfänger allerdings reichlich übertrieben.

stimmt natürlich auch wieder ;) Hatte aber eben gerade Lust dazu, so ein Teil zu schreiben ;)

[DeddyH]

Ja sicher, meine Lösung ist ja auch mehr auf Verständlichkeit (obwohl das für den absoluten Anfänger wohl auch schon hard stuff ist) als auf Performance ausgelegt. Wenn Du magst, kannst Du ja trotzdem einmal Deine Variante posten, ich denke, daran bin nicht nur ich interessiert (wer weiß, ob man das nicht mal brauchen kann?) ;)

[patti]

Zitat:

Zitat von DeddyH (Beitrag 1128154)

Wenn Du magst, kannst Du ja trotzdem einmal Deine Variante posten

Ist halt wie gesagt in Java, weil (1) Lazarus im Moment nicht so mag wie ich und (2) ich demnächst selber mal sowas in Java brauchen werde... Ist auch kein bisschen kommentiert und sicherlich auch noch nicht perfekt, ist mehr oder weniger schnell runtergetippt... Löschen aus dem Suchbaum fehlt auch noch. Ich hänge es trotzdem mal an, wenn jemand Interesse daran hat ;)

lg

[DeddyH]

*Puh* das muss ich mir mal ganz in Ruhe anschauen, obwohl ich arg bezweifle, dass meine Java-Grundkenntnisse von 2004 da noch ausreichen.

[patti]

Hm, vielleicht kommentiere ich das Teil auch mal ordentlich, dann sollte es relativ einleuchtend sein ;)

[BUG]

Ich hab das Teil afaik als Trie-Struktur beigebracht bekommen.
Wir durften eine Art T9 damit basteln :mrgreen:

[himitsu]

Delphi-Quellcode:

uses DB, DBClient, MidasLib;  // unit MidasLib, damit man diese blöde Midas.dll nicht mitgeben muß

type
  TWoerterbuch = class(TClientDataSet)
    constructor Create;
    procedure Add(const Word: string);
    function Filter(const SearchWord: string): Boolean;
    procedure Delete(const Word: string);
    procedure Clear;
    procedure GetList(Result: TStrings);

    //property FileName: string;  // ist alles in TClientDataSet deklariert
    //procedure LoadFromFile(const FileName: string = '');
    //procedure SaveToFile(const FileName: string = ''; Format: TDataPacketFormat = dfBinary);
    //procedure LoadFromStream(Stream: TStream);
    //procedure SaveToStream(Stream: TStream; Format: TDataPacketFormat = dfBinary);
  end;

procedure TWoerterbuch.Add(const Word: string);
begin
  Insert;
  try
    Self['Word'] := Word;
    Post;
  except
    Cancel;
    raise;
  end;
end;

procedure TWoerterbuch.Clear;
begin
  EmptyDataSet;
end;

constructor TWoerterbuch.Create;
begin
  CreateDataSet;
  FieldDefs.Add('Word', {$IF SizeOf(Char) = 2}ftWideString{$ELSE}ftString{$IFEND}, 30);
  AddIndex('WordIdx', 'Word', [ixUnique, ixCaseInsensitive]);
  IndexName := 'WordIdx';
end;

procedure TWoerterbuch.Delete(const Word: string);
begin
  if Locate('Word', Word, [loCaseInsensitive]) then
    inherited Delete;
end;

function TWoerterbuch.Filter(const SearchWord: string): Boolean;
begin
  if SearchWord <> '' then begin
    Filtered := False;
    FilterOptions := [foCaseInsensitive, foNoPartialCompare];
    Filter := '[Word] LIKE ''' + SearchWord + '%''';
    Filtered := True;
  end else
    Filtered := False;
  Result := RecordCount > 0;
end;

procedure TWoerterbuch.GetList(Result: TStrings);
begin
  Result.BeginUpdate;
  try
    First;
    while not Eof do begin
      Result.Add(Self['Word']);
      Next;
    end;
  finally
    Result.EndUpdate;
  end;
end;

(hoffentlich hab ich das jetzt richtig zusammenbekommen)

Oder direkt an eine datenbank ran, aber dann ohne CreateDataSet (im Constructor) und ohne SaveToFile und LoadFromFile.

Statt GetList kann man es auch direkt, über eine TDataSource, an einen DBGrid hängen.
Oder man nimmt die TDataSource als Vorfahre und das TClientDataSet in die Klasse rein.

[patti]

Also den Namen Trie kannte ich bisher nicht (finde ich ehrlich gesagt auch etwas "gewöhnungsbefürftig"), aber das Prinzip ist genau das Gleiche ;) Das Beispiel mit dem T9 klingt interessant, da mach ich mir mal Gedanken dazu ;)

[DeddyH]

Zu #27: Jetzt noch eine Client-/Server-Datenbank mit MySQL auf einem Webserver mit Abfragen über HTTPS, und wir haben auch den letzten Anfänger vergrault. Geht es hier eigentlich um Hilfe oder darum, wie man sich selbst am Besten darstellt? *Koppschüttel*

[patti]

Ehrlich gesagt finde ich den "Informationsaustausch" voll in Ordnung. Es geht darum, mögliche Lösungswege aufzuzeigen - darum geht es ja schließlich in einem Forum. Der TE hat ziemlich schnell eine funktionierende und relativ leicht verständliche Lösung bekommen, also kann der schonmal glücklich sein. Der Rest braucht ihn ja nicht zu interessieren, aber für andere User ist das hier evtl. durchaus interessant.

[himitsu]

Zitat:

Zitat von DeddyH (Beitrag 1128162)

Geht es hier eigentlich um Hilfe oder darum, wie man sich selbst am Besten darstellt? *Koppschüttel*

Zitat:

Brauch ich dafür eine datenbank?

Er wollte ja wissen wie man es machen kann. :stupid: (uns fehlt das Negieren :cry:)
- ja, es geht über eine Datenbank
- nein, es geht auch ohne (siehe die letzen Posts, welche eine ganz ganz kleine Auswahl aller Möglichkeiten darstellen)
- und für den Anfang wäre auch eine einfache TStringList ausreichend (die muß man nichtmal irgendwo wegkapseln)

Zitat:

Der Rest braucht ihn ja nicht zu interessieren

Kann er sich ja interessehalber dennoch ansehn. :angle:

[DeddyH]

In dem Fall fände ich persönlich aber angebrachter, dafür einen neuen Thread zu eröffnen. Wenn ich eine Frage habe, dann lese ich mir auch den kompletten Thread durch, und wenn dann da Antworten kommen, die ich beim besten Willen nicht mehr nachvollziehen kann, erhöht das meinen Frustfaktor enorm. Aber es kann natürlich auch sein, dass es nur mir so geht.

[himitsu]

PS:

Zitat:

Brauch ich dafür eine datenbank?

Die Daternbankseite wurde hier vollkommen vernachlässig.

Der Code selber ist doch noch recht übersichtlich?
Und die zwei/drei heiklen Stellen erklärt die OH auch recht gut. (falls man den Code ganz verstehen will)

Für die große Datenbankgeschichte gibt es dann noch die passendenden Tutorials.

[DeddyH]

Braucht er eine? Nein, wie von uns allen bewiesen. Also, was willst Du da vernachlässigen? Ich werde mal darum bitten, den Thread an geeigneter Stelle abzuspalten, da kann es dann weitergehen. Einverstanden?

[himitsu]

Er hat danach gefagt?
Und es hat keiner gesagt, daß er diese nicht doch gebrauchen könnte (vorallem Er nicht),
nur daß es anders eventuell auch möglich wäre.

Zitat:

bei überschaubarer Datenmenge ist die allerdings nicht nötig

Wir kennen ja sein Wörterbuch nicht.


Sonst beschweren sich doch auch alle, wenn jemand mal nach etwas "geziehlt" fragt
und dann alle nur über die Alternativen reden, aber die ursprüngliche Frage nicht beantworten.

[mkinzler]

Zitat:

Zitat von DeddyH (Beitrag 1128167)

Braucht er eine? Nein, wie von uns allen bewiesen. Also, was willst Du da vernachlässigen? Ich werde mal darum bitten, den Thread an geeigneter Stelle abzuspalten, da kann es dann weitergehen. Einverstanden?

Gant wichtig fände ich eine obfuskierte Brainfuck Variante

[jobo]

Typisch, ausgerechnet am Tag der Deutschen Einheit!

Piece, eyh! ;)

[BUG]

Zitat:

Zitat von himitsu (Beitrag 1128166)

PS:

Zitat:

Brauch ich dafür eine datenbank?

Die Daternbankseite wurde hier vollkommen vernachlässig.

Ich glaube die Datenbank kommt bei Anfängern oft ins Spiel, weil manche Informatiklehrer alles, angefangen bei einer zeilenweisen Speichung in einer Textdatei, als Datenbank bezeichnen.

Wen man hier tatsächlich mit einer (SQL-)Datenbank arbeiten möchte, könnte LIKE eventuell ein guter Ansatzpunkt sein.

Die Datenbanken-Entwickler kochen auch nur mit Wasser, so dass man am Ende mit einer clever konstruierten Datenstruktur für solche spezielle Probleme vielleicht sogar schneller ist.