Re: Bugreport für Rechtschreibung
On Sunday 20 April 2014 09:55:22 Kai-Martin Knaak wrote:
> Michael Schuerig wrote:
> > On Thursday 17 April 2014 19:57:59 Michael Höhne wrote:
> >> Die Frage ist dann aber: Welche Ressourcen frisst dann ein
> >> "komplettes" Wörterbuch mit 200000 Wörtern? Wenn ich nach jedem
> >> geschriebenen Wort mehrere Sekunden warten müsste, oder mein
> >> Rechnerlüfter "aufheult"...
> >
> > 200.000 Wörter
> > x geschätzte 14 Buchstaben pro Wort
> > x geratene 1,5 Bytes pro Buchstabe
> > = 4.200.000 Bytes =ungefähr 4 MB
> >
> > Nehmen wir noch etwas Overhead für eine geeignete Datenstruktur an
> > (die ganz passend üblicherweise als "dictionary" bezeichnet wird),
> > kommen vielleicht 5 bis 6 MB dabei heraus. Wenn du ein Smartphone
> > hast, dann könnte das vermutlich pro Sekunde 100.000 Wörter darauf
> > überprüfen, ob sie im Wörterbuch vorkommen.
>
> Wobe es natürlich den dümmst-möglichen Suchalgorithmus anwendet, der
> alle Wörtbuchwörter einzeln abklappert.
Nun, ein oder mehrere Dictionary-Implementierungen (Hash, Tree) ist
üblicherweise heute bei den meisten Programmiersprachen im Lieferumfang;
nach einem Trie muss man schon etwas suchen. Könnte man aber auch nach
der Vorlage des Meisters selbst implementieren, wenn man ansonsten unter
der "dümmst-möglichen" Datenstruktur Hash leiden würde:
http://homepages.cwi.nl/~storm/teaching/reader/BentleyEtAl86.pdf
> Sinnvollerweise ist für das
> Wörterbuch aber ein im voraus berechneter Indexbaum erstellt worden.
> Im einfachsten Fall orientiert sich der Index am Alphabet. Dann
> funktioniert die Such so ähnlich wie wir das Wort "Haus" im Wörterbuch
> aus Papier finden: Erst wird im Index die Seite ermittelt, auf der
> die Worte mit dem Anfangsbuchstabe H beginnen. Dann wandert der
> Zeigefinger zu den Worten, die mit Ha anfangen. von dort ist es nicht
> mehr weit zu den Hau-Worten und schon ist man beim Haus. Im
> schlimmsten Fall braucht man so viele Schritte, wie das Wort
> Buchstaben hat.
>
> Dieses Verfahren skaliert wunderbar. Es ist daher leicht modifiziert
> die Basis für die index-basierte Suchfunktion "locate" in allen
> Dateinamen eines Linux-Systems. Oder die Volltextsuche mit swish-e,
> oder recoll, oder auch google...
Bist du übrigens sicher, dass ein Trie gegenüber einem Hash tatsächlich
schneller ist? Die Speichereinsparung ist offentsichtlich, der
Geschwindigkeitsvorteil (mir) nicht.
Michael
--
Michael Schuerig
mailto:michael@schuerig.de
http://www.schuerig.de/michael/
Reply to: