Re: Bugreport für Rechtschreibung
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. 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...
---<)kaiamrtin(>---
Reply to: