# String mit Wörterbuch vergleichen



## dict (3. Okt 2011)

Ich habe viele Strings ohne Leerzeichen, in denen ein Wort enthalten sein kann, nun möchte ich diese herausfiltern, die ein deutsches Wort enthalten.
Dazu habe ich mir ein Wörterbuch mit 300 000 Einträgen als .txt runtergeladen und in ein Array eingelesen und bin wie unten zu sehen vorgegangen, doch dauert diese Methode relativ lang ( ca. 1 Sekunde ), das ist bei mehreren 1000 Strings zu viel.
Ich nehme von jedem Wort die z.B. ersten 4 Buchstaben und lasse diese suchen, wenn nicht gefunden, dann die nächsten 4 Buchstaben usw., weil es ja keine Leerzeichen gibt und die Länge unbekannt ist.

Mir fällt aber auch keine effizientere Methode ein, wenn ihr einen Link oder irgendwelche Vorschläge habt, wäre ich sehr erfreut, programmieren noch nicht so lange und bei bspw. Office geht die Rechtschreibprüfung auch sehr schnell voran.


```
dict( String output, String[] dictionary, byte minLength )
  {
  String word; //aktuelles Wort
  while( output.length() >= minLength //solange Gesamtstring größer ist als die Mindestwortlänge)
   {
     word = output.substring( 0, minLength ); 
           Pattern p = Pattern.compile(word);
     for( int i = 0; i < dictionary.length; i++ ) //alle Wörterbucheinträge werden durchlaufen
     {
      Matcher m = p.matcher(dictionary[i]);

       if( m.find() )
       {
        return true;
       }
     }
     output = output.substring( 1 );
   }
   return false;

  }
```


----------



## XHelp (3. Okt 2011)

Mit RegEx einen String durchzusuchen ergibt kein Sinn, es gibt effizientere Verfahren: Shift-OR, Boyer-Moore+Modifikationen etc.
Ansonsten kannst du diese Aufgabe auch schön parallelisieren, was die bestimmt eine Effizienzsteigerung bringt.


----------



## dict (3. Okt 2011)

Die Algorithmen werde ich mir anschauen, wird wohl etwas dauern.

Mit was für einer Steigerung kann ich ungefähr rechnen bei den Algorithmen?


----------



## XHelp (3. Okt 2011)

Öhm... k.a., ich kann mir vorstellen, dass diese RegEx-Suche auf O(n*m) hinausläuft, die oben genannten Algos müssten in O(n) sein. Und dazu kommt noch parallele Abarbeitung.
Aber ich würde an deiner Stelle nicht jedes möglich Wort im Wörterbuch suchen, sondern Wörter aus dem Wörterbuch in der gesamten Zeichenkette suchen.


----------



## faetzminator (3. Okt 2011)

Ich kenn da eine Datenstruktur, aber mir fällt der Name gerade nicht ein. Man erstellt einen Baum, bei welchem jeder Knoten ein Zeichen ist. So hätte man bei den Wörtern [c]Aas[/c], [c]Aal[/c] und [c]Abend[/c] etwa folgende Struktur:

```
A
|- a
   |- l
   *- s
*- b
   *- e
      *- n
         *- d
```
Das Ergebnis ist, dass man pro Wort im Input nur ein Mal durch den Baum laufen muss.


----------



## XHelp (3. Okt 2011)

Hat was von Patricia-Trie ? Wikipedia oder generell ein Präfixbaum


----------



## faetzminator (3. Okt 2011)

Ah ja, ich meinte den "normalen" Trie ? Wikipedia, danke


----------



## XHelp (4. Okt 2011)

Der Trick ist eben auch nicht nach Buchstaben zu trennen, sondern nach dem Präfix. In deinem Beispiel würde also "bend" in einem Blatt landen. Wenn später das Wort "Aber" rein soll, dann wird eben nach dem "be" aufgesplittet und dann hast du A>be>r und A>be>nd


----------



## dict (12. Okt 2011)

Habe mir folgendes zu BoyerMoore runtergeladen und ausprobiert:
Boyer 1.5 - Fast string search (indexOf) using the Boyer-Moore algorithm. - SharewarePlaza

Ist aber eher langsamer als schneller, habe schon verschiedene probiert.


----------



## dict (13. Okt 2011)

Diese Algorithmen eignen sich wohl eher für lange Strings ( > 1000 Zeichen ), was bei mir aber nicht der Fall ist, das Muster ist vielleicht durchschnittlich 8 Zeichen und der String, in dem gesucht werden soll zwischen 20 und 40 Zeichen.
Gibt es da was anderes, nutze jetzt übrigens, wie vorgeschlagen, die Möglichkeit die Wörterbucheinträge im String zu suchen.


----------



## XHelp (13. Okt 2011)

Bei der Größe wirst du nicht vernünftig optimieren können. Da wird die Vorverarbeitung ggf Länger als 
	
	
	
	





```
indexOf
```
 dauern. Du könntest aber vlt deine ganzen String zu einem zusammenschmeißen oder so.


----------



## kay73 (14. Okt 2011)

- Wo hast Du denn das *.txt file her?

- Um Dein Problem zu verstehen:
Dein Dictionary kann so aussehen:
HAUS
BAUM
AUTO

Dein Text so:
THE AUTO CRASHES IN THE BAUM

Dein Algorithmus soll die Liste [AUTO,BAUM]  liefern? Oder ist das Problem wirklich  allgemeiner, wie z.b ABCDBAUMXYZ?

- Willst Du auch Flexion erkennen? Z. B. wenn im Text der Genitiv "BAUMES" vorkommt, soll dann auch "BAUM" im Woerterbuch gefunden werden? Dann wird's computer-linguistisch mit Lemmatisierung usw...


----------



## XHelp (14. Okt 2011)

Lemmatisierung oder selbst Stemming ist für die deutsche Sprache ziemlich schwer. Und mit "ziemlich schwer" meine ich: es gibt nichts vernünftiges, was man benutzen könnte. Deutsch ist eine stark flektierende Sprache, deswegen fallen die Standardalgorithmen raus. Und auch die zusammengesetzten Wörter sollten nicht unterschätzt werden. Snawball könnte man da neben, aber das hat eben eine große Fehlerquote.
Da lohnt es sich eher ein ziemlich großes Wörterbuch zu nehmen (wordnet oder so).


----------

