Schnellster Stringmatching-Algorithmus in ASM übersetzen

[Sereby]

www.FastCode.Org existiert nichtmehr :/

und ich hab die beiden optionen eingeschaltet im projekt allerdings knallt das genauso wie vorher ohne ne andere meldung. Was sollte da denn passieren?

Ahja wenn ich Set8087CW($133F); benutze, dann knallts nicht aber der anfang (XML datei) ist dann zerschossen mit #0 und € und so

[alzaimar]

www.fastcodeproject.org, sorry.

[negaH]

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

[alzaimar]

Hi Hagen, danke für die Ausführungen. Dann werde ich meine Kentnisse über DAWGs nochmal auffrischen. Insbesondere die kompakten Datenstrukturen hatte ich in den Implementierungen bisher vergeblich gesucht. Muss aber zugeben, zu schnell aufgegeben zu haben.

Ich dachte immer, die Verkettung pro Buchstabe sei so speicheraufwändig.

[negaH]

Ja das stimmt ja auch ;) Aber durch die Entfernung der Suffixe/Prefixe spart man das wieder enorm ein. Hängt natürlich vom Inhalt des Wörterbuches selber ab.
Bei meinem DWAG (kannste bei Luckie downloaden) benutze ich 4 Bytes pro Buchstaben und auf dieses treffen auch die 6Mb -> 800Kb -> 200000 deutsche Wörter zu.
Zudem gilt bei Gleichverteilung von 2000000 Wörtern und 26 Buchstaben also pro Buchstabe 7600 Wörter beginnen, 26 Nodes für den Anfangsbuchstaben von 200000 Wörtern. Also für die Basenode "A" sind 7600 Wörter untergeordnet, für 4 Bytes in meinem DWAG also 7600 Worte. Danach wieder 1/26'tel pro Subnode = 290 wörter, dann wieder 1/26'tel pro Subsubnode = 11 Wörter usw. Diese Rechnung ist aber der Worstcase, also wenn die 7600 alle Kombinationen aller Buchstaben enthielten, was aber fern der Realität eines Wörterbuches ist.

Gruß hagen