Zitat:
Noch etwas zu Tries, DAWGs etc. Das sind wahre Performancewunder, aber leider verbraten sie so dermaßen viel Speicher, das sie sich in der Praxis nicht zum Suchen in langen Texten eignen. Als Wörterbuch sind sie dagegen wirklich 'kinky'.
Nur um dieses kleine Detail richtig zu stellen, DAWGs also Suffix/prefixtries, sind für Wörterbücher konstruiert und im Gegensatz zu allgmeinen Annahme sind es auch fast perfekte Komprimierungen (sprich sie entfernen Redundanzen in den Wörterebücher besser als viele herkömliche Komprimierungsalgo.) Kurz: die Aussage das sie viel Speicher verbraten gilt nicht generell. DWAGs zb. speichern Wörterbücher so kompakt das manche Zipper verblassen. Und dabei meine ich die real im Speicher liegende Datenstruktur. Eine Wortdatenbank mit 200.000 deutschen Wörtern verbraucht 6 Mb und 800kB als DAWG im Speicher.
Allerdings sollte man nicht Äpfel mit Birnen vergleichen, heist die Zielsetzungen von Tries/DWAGs ist nicht das schnelle Aufsuchen von Phrasen in vorher unbekannten und nicht preprozessierten Texten.
Ich habe aber auch DWAGs für schnelle pseuoparallele Textsuchen, bei denen eine kleine Datenbank von Wörtern per DAWG gespeichert wurde, umgesetzt. Diese Suchmethode dürfte im Vergleich zu den oben besprochenen Verfahren wesentlich effizienter sein, heist um mehrfaches schneller. Aber! das Ziel hat sich abei geändert, nämlich das Durchsuchen von sehr vielen Textdokumenten (Streambasiert) nach sehr vielen Suchbegriffen in parallel, quasi ein Scanner. Wenn man zb. 1000 Schlagworte innerhalb mehrer textbasierter
TCP/
IP Streams online suchen möchte dann sind solche Verfahren wie Boyer-Moore etc.pp. schlicht ineffizient. Man kann aber DWAGs so umbauen das sie diese 1000 Wörter als Datenbank effizient speichern und dann in parallel damit mehrere Textstreams scannen. Rechnet man das um, in normale Textdateien mit Größe X mal Anzahl Y an Suchbegriffen und vergleicht die sich ergebenende Gesamtkomplexität eines solchen DAWG-basierten Scanners mit einem auf Boyer-Moore Verfahren das ebenfalls nach diesen Schlagwörtern suchen soll, dann habe ich die Erfahrung gemacht das das DWAG weit besser ist. Eine zweite interssante Anwednung dieses Scanners ist es das er kombinatorische online Suchen durchführen kann. Dh. die Wortdatenbank dient als Referenz der Suchworte aber während der Suche können auch effizient Rekombinationen dieser Suchworte (selbst Buchstaben-Permutationen innerhalb der Suchwörter) im Text gefunden werden. Ok, das sind jetzt aber wirklich Äpfel im Vergleich zu Birnen (Boyer-Moore etc.pp
)
Es hängt also, wie bei jedem hochspezialisierten informationstechnischen Verfahren, ganz entscheidend von den Rahmenbedingungen und Zielsetzungen ab.
Gruß Hagen