AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Schnellster Stringmatching-Algorithmus in ASM übersetzen

Schnellster Stringmatching-Algorithmus in ASM übersetzen

Offene Frage von "Sereby"
Ein Thema von alzaimar · begonnen am 5. Dez 2007 · letzter Beitrag vom 3. Jul 2008
Antwort Antwort
Seite 8 von 8   « Erste     678
Sereby

Registriert seit: 31. Mär 2008
91 Beiträge
 
#71

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 2. Jul 2008, 16:19
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
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#72

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 2. Jul 2008, 16:20
www.fastcodeproject.org, sorry.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#73

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 3. Jul 2008, 01:32
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
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#74

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 3. Jul 2008, 08:05
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#75

Re: Schnellster Stringmatching-Algorithmus in ASM übersetzen

  Alt 3. Jul 2008, 11:07
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
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 19:50 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz