Trie vs. Suffixbaum vs. Suffixarray

Question

Welche Struktur bietet die besten Performance-Ergebnisse; trie (Präfix-Baum), Suffixbaum oder Suffixarray? Gibt es andere ähnliche Strukturen? Was sind gute Java-Implementierungen dieser Strukturen?

Edit:. In diesem Fall hat ich String-Matching zwischen einem großen Wörterbuch des Namen und einem großen Satz von natürlichsprachlichen Texten machen will, um die Namen des Wörterbuchs auf Texte zu identifizieren

Answer 1

Die Trie wurde die erste Datenstruktur dieser Art entdeckt.

Der Suffix-Baum ist eine Verbesserung gegenüber dem Trie (es Suffix Links hat die lineare Fehlersuche zu ermöglichen, die Suffixbaum trimmt unnötige Zweige des Trie daher ist es nicht so viel Platz benötigt).

Das Suffix-Array ist eine abgespeckte Datenstruktur basierend auf dem Suffix-Baum (keine Suffix Links (slow Fehler Ursachen), doch Pattern-Matching ist sehr schnell).

Die Trie ist nicht für reale Welt Verwendung, weil es zu viel Platz verbraucht.

Der Suffix-Baum ist leichter und schneller als die trie und zu indizieren DNA oder optimiert einige große Web-Suchmaschinen verwendet.

Das Suffix-Array ist langsamer in einigen Mustern suchen als der Suffixbaum aber benötigt weniger Platz und mehr verwendet wird weithin als der Suffix-Baum.

In der gleichen Familie von Datenstrukturen:

Es gibt auch andere Implementierungen ist der CST eine Implementierung des Suffixbaum ein Suffix-Array und einige zusätzliche Datenstrukturen einige der Suffixbaum Suchfunktionen zu erhalten.

Die FCST dauert es weiter, er führt eine abgetastete Suffixbaum mit einem Suffix-Array.

Die DFCST ist eine dynamische Version des FCST.

Die Erweiterung:

Die beiden wichtigsten Faktoren sind Raumnutzung und den Betrieb der Ausführungszeit. Man könnte denken, dass mit modernen Maschinen nicht relevant ist, sondern die DNA eines einzelnen Menschen zu indizieren würde 40 Gigabyte Speicher erfordern (unter Verwendung eines nicht komprimierten und nicht optimierten Suffixbaum). Und über diese viele Daten einen dieser Indizes bauen können Tage dauern. Stellen Sie sich vor Google, es viele durchsuchbare Daten hat, müssen sie eine große Übersicht über alle Web-Daten und sie es nicht jedes Mal ändern jemand baut eine Webseite. Sie haben eine Form für das von Caching. Doch der Hauptindex ist wahrscheinlich statisch. Und alle paar Wochen oder so versammeln sie sich alle neuen Websites und Daten und bauen einen neuen Index, die die alte ersetzt, wenn die neue fertig ist. Ich weiß nicht, was sie zu indizieren verwenden Algorithmus, aber es ist wahrscheinlich ein Suffix-Array mit Suffixbaum Eigenschaften über eine partitionierten Datenbank.

Die CST verwendet 8 Gigabyte, aber die Suffixbaum Operationen Geschwindigkeit stark reduziert.

Das Suffix-Array kann in einigen 700 megas bis 2 Gigas das gleiche tun. Allerdings werden Sie nicht genetische Fehler in der DNA mit einem Suffix-Array finden (was bedeutet: für ein Muster mit einem Wildcard-Suche ist viel, viel langsamer)

.

Die FCST (vollständig komprimiert Suffixbaum) einen Suffix-Baum in 800-1,5 gigas erstellen. Mit einer eher kleinen Geschwindigkeit Verschlechterung gegenüber der CST.

Die DFCST verwendet 20% mehr Platz als die FCST und verliert Geschwindigkeit der statischen Umsetzung des FCST (jedoch ein dynamischer Index ist sehr wichtig).

Es gibt nicht viele tragfähige (Raum weist) Implementierungen des Suffixbaum, weil es sehr schwierig ist, die Operationen Geschwindigkeitsschub zu machen, die Datenstrukturen RAM Raumkosten kompensieren.

Dieser sagte, hat der Suffixbaum sehr interessante Suchergebnisse für Mustervergleich mit Fehlern. Der aho Corasick ist nicht so schnell (wenn auch fast so schnell für einige Operationen, nicht Fehler matching) und die boyer moore im Staub gelassen werden.

Answer 2

Welche Operationen planen Sie auf tun? libdivsufsort zu einem Zeitpunkt in C die beste Suffixarray Implementierung war.

Answer 3

Mit Suffix Bäume können Sie etwas schreiben, die Ihr Wörterbuch auf Ihren Text in O übereinstimmen (n + m + k) Zeit, in der n Buchstaben in Ihrem Wörterbuch ist, ist m Buchstaben im Text, und k die Anzahl der Spiele . Tries sind viel langsamer dafür. Ich bin mir nicht sicher, was ein Suffix Array ist, so kann ich nicht kommentieren, dass.

sagte, es ist nicht trivial, um Code und ich zufällig von keinen Java-Bibliotheken kennen, die die notwendigen Funktionen zur Verfügung stellen.

Answer 4

  

EDIT: In diesem Fall hat ich String-Matching zwischen einem großen Wörterbuch des Namen und einem großen Satz machen will von   natürlichsprachlichen Texten, um die Namen des Wörterbuchs auf Texte zu identifizieren.

Das klingt wie eine Anwendung für die Aho-Corasick Algorithmus : konstruieren einen Automaten aus dem Wörterbuch (in linearer Zeit), die alle Vorkommen eines der Wörter aus dem Wörterbuch in mehreren Texten (auch in linearer Zeit).

finden können dann verwendet werden

(Die Beschreibung in diese Skriptum , aus der „externen Links“ auf der Seite Wikipedia verknüpfen, ist viel einfacher als die Beschreibung lesen auf der Seite selbst.)

Answer 5

Trie vs Suffixbaum

beide Datenstruktur ein sicherzustellen, sehr schnell nachzuschlagen, die Zeit der Suche ist proportional zur Länge des Abfragewort, Komplexität O (m), wobei m die Länge des Abfragewort ist.

es ist gemein, wenn wir Abfragewort haben, die 10 Zeichen haben, so dass wir höchstens 10 Schritte benötigen, es zu finden.

Trie : ein Baum für Zeichenfolge, in denen die Speicherung gibt es einen Knoten für jeden gemeinsamen Präfix. Die Saiten werden in zusätzlichen Blattknoten gespeichert.

Suffixbaum : eine kompakte Darstellung eines Trie mit den Suffixen entsprechenden eine bestimmte Zeichenkette, in der alle Knoten mit einem Kind mit ihren Eltern zusammengeführt werden.

sind def aus: Wörterbuch von Algorithmen und Datenstrukturen

allgemein verwendet Trie indizieren Wörterbuch Wörter (Lexikon) oder irgendwelche Sätze von Saiten Beispiel D = {abcd, abcdd, bxcdf, ....., zzzz}

ein Baum Suffix Indextext verwendet, indem die gleiche Datenstruktur „Trie“ können auf alle Suffixe unseres Textes T = abcdabcg alle Suffixe von T = {abcdabcg, abcdabc, abcdab, ABCDA, abcd, abc, ab, a}

Jetzt sehen sie wie eine Gruppe von Strings. wir bauen eine Trie über über diese Gruppe von Strings (alle Suffixe von T).

die Konstruktion sowohl Datenstruktur ist in linear, nimmt es O (n) in Zeit und Raum.

bei dicionary (eine Reihe von Strings): n = die Summe der Zeichen aller Wörter. in Text:. n = Länge des Textes

Suffixarray: a. Technic ist ein Suffix-Baum in komprimiertem sapce darstellen, es ist eine Anordnung von allen Startpositionen von Suffixen einer Zeichenkette

es ist langsamer als Suffix-Baum auf der Suche Zeit.

Weitere Informationen finden Sie auf Wikipedia gibt es einen guten Artikel zu diesem Thema zu sprechen.

Answer 6

ziehe ich Suffix Auto Machine. Sie können weitere Informationen über meine Website finden: http://www.fogsail.net/2019/03/06/20190306/

eingeben image description hier

zuerst, wenn Sie normale Konstruktion verwendet wird, wird es dauert O (n ^ 2) alle Reise des Suffix

Wir verwenden Radix-Sortierung das Suffix Array von ersten Zeichen zu sortieren.

Aber wenn wir sortieren das erste Zeichen, können wir die Informationen verwenden.

Details durch die Bilder zeigten werden (Vernachlässigung Chinesisch)

Wir sortieren Array durch die erste schlüsselfertige, das Ergebnis durch das rote Rechteck dargestellt wird

Answer 7

Diese Implementierung der induzierten Sortieralgorithmus (genannt sais) eine Java-Version für Suffixarray zu konstruieren.