Wörter aus Text extrahieren beschleunigen

[negaH]

DAWG zu klein und Datei zu groß. Man könnte das DWAG anpassen damit es mit wesentlich größeren Datenmengen auskommt ist aber nicht ganz so einfach. Primär habe ich es entwickelt als hoch effiziente Suchmachine in einer Wortdatenbank mit ca. 200.000 deutschen und 250.000 englischen Wörtern. Dabei werden aber nur sehr wenige Wortseparatoren benutzt, also die Sonderzeichen die ein Wort von einem anderen separieren. Das wären nur die Sonderzeichen ' ', #13, #10 und TabSpace. Alle anderen Sonderzeichen werden als Wortbuchstaben interpretiert. Du müsstest also den Source für die EXE leicht abändern:

Delphi-Quellcode:

  // Zeichenmapping definieren, Großbuchstaben werden in Kleinbuchstaben umgewandelt
  // TDawg.LoadWordsFromFile() führt auch somit eine Konvertierung und Filterung durch
    for I := Low(C) to High(C) do C[I] := I;
    CharLowerBuff(@C, SizeOf(C));

    FDawg := TDawg.Create;
    FDawg.SetMapping(C, [#0,#10,#13,';',' ',',']);
    FDawg.LoadWordsFromFile(OD1.FileName);

da muss das Zeichenmapping -> FDawg.SetMapping() verändert werden. Wenn nur Buchstaben und Ziffern gültige Wörter sein sollen dann so abändern

Delphi-Quellcode:

var
  Chars: TDawgMapping;
  Separators: TDawgCharSet;
  I: TDawgChar;
....
begin
....
  // Zeichenmapping definieren, Großbuchstaben werden in Kleinbuchstaben umgewandelt
  // TDawg.LoadWordsFromFile() führt auch somit eine Konvertierung und Filterung durch
    for I := Low(TDawgChar) to High(TDawgChar) do 
      Chars[I] := I;
    CharLowerBuff(@Chars, SizeOf(Chars));

  // erzeuge das Set der Wort-Separatoren-Zeichen
  // alle Zeichen die nicht Buchstaben/Ziffern sind sind Separatoren    
    Separators := [];
    for I := Low(TDawgChar) to High(TDawgChar) do 
      if not (I in ['a'..'z', 'A'..'Z', '0'..'9']) then
        Separators := Separators + [I];

    FDawg := TDawg.Create;
    FDawg.SetMapping(Chars, Separators);
    FDawg.LoadWordsFromFile(OD1.FileName);
....
end;

Nun werden Wörter nur dann akzeptiert wenn sie aus Buchstaben oder Ziffern bestehen, alle anderen Zeichen trennen die einzelnen Wörter voneinander. Obige Änderung könnte dein Problem lösen, aber auch nur dann wenn viele Sonderzeichen im Text vorkommen. Das DAWG kann soviele absolut unterschiedliche Wörter speichern so das die Buchstabenanzahl all dieser Wörter nicht 2^21 überschreitet, also 2^21 Nodes a 4 Byte. Ein im Text mehrfach vorkommendes Wort wird natürlich nur einmalig im DAWG gespeichert. Sogar bei Wörter mit gleichem Anfang wird dieser Anfang nur einmalig gespeichert.

Wenn also immer noch der Fehler kommt dann muß man das DAWG so umbauen das es mehr Nodes aufnehmen kann. Der Aufwand lohnt aber nicht wenn mit deiner Methode die 122Mb in 3 Sekunden gelesen werden kann, das ist schon ein sehr guter Wert.

Gruß Hagen

[negaH]

Ich habe mal eine 144Mb Textdatei erzeugt, das DAWG benötigt 1.6 Sekunden um daraus alle Wörter sortiert zu extrahieren. Deine Methode ist also mit 3 Sekunden wirklich schon sehr schnell. Könntest du hier deinen Source posten ?

Gruß Hagen

[kng]

Naja ich verwende einfach die TRegExprEx Komponente von dieser Seite mit dem Ausdruck "[a-zA-Z0-9]+".

Das Laden der Datei war in den 3 Sekunden allerdings nicht miteinbezogen, trotzdem schnell genug für meine Zwecke.

[omata]

Zitat:

Zitat von kng

Hab die ganze Prozedur jetzt mit einem regulären Ausdruck abgedeckt.

:thumb:

Reguläre Ausdrücke sind einfach genial und dieses Beispiel zeigt mal wieder das sie eben nicht langsamer sind.

[negaH]

Zitat:

...dieses Beispiel zeigt mal wieder das sie eben nicht langsamer sind.

Vorsicht, bisher wurde kein aussagekräftiger Vergleich angestellt. Zb. möchte ich per RegEx eine große Textdatei durchsuchen und die Anzahl unterschiedlicher Wörter im Text ermitteln. Ich wette einen Kasten Bier das das DAWG als komplett anderer Algorithmus diese Aufgabe bei weitem besser erledigt als RegEx. Es hängt also von den Rahmenbedingungen ab und später beim Vergleich der verschiedenen Verfahren untereinander müssen dann auch identische Testbedingungen herrschen. Meine Angabe von oben mit 144Mb Textdatei in 1.6 Sekunden enthält das Laden und Sortieren der gefundenen Wörter aus der Textdatei. Zusätzlich wird auch noch on the fly die so erzeugte Wortdatenbank im Speicher komprimiert.

Gruß Hagen