Effiziente Trie-Implementierung für Unicode-Strings

12

Ich habe nach einer effizienten String-Trie-Implementierung gesucht. Meistens habe ich folgenden Code gefunden:

Referenzielle Implementierung in Java (per Wikipedia)

Ich mag diese Implementierungen aus zwei Gründen nicht:

  1. Sie unterstützen nur 256 ASCII-Zeichen. Ich muss Dinge wie Kyrillisch behandeln.
  2. Sie sind extrem speichereffizient.

Jeder Knoten enthält ein Array mit 256 Referenzen, dh 4096 Byte auf einem 64-Bit-Computer in Java. Jeder dieser Knoten kann bis zu 256 Unterknoten mit jeweils 4096 Byte Referenzen haben. Ein vollständiger Trie für jede ASCII 2-Zeichenfolge würde also etwas mehr als 1 MB erfordern. Drei Zeichenketten? 256 MB nur für Arrays in Knoten. Und so weiter.

Natürlich habe ich nicht vor, alle 16 Millionen drei Zeichenfolgen in meinem Trie zu haben, also wird viel Platz nur verschwendet. Die meisten dieser Arrays sind nur Nullreferenzen, da ihre Kapazität die tatsächliche Anzahl der eingefügten Schlüssel bei weitem überschreitet. Und wenn ich Unicode hinzufüge, werden die Arrays noch größer (char hat 64k-Werte anstelle von 256 in Java).

Gibt es Hoffnung, einen effizienten Versuch für Saiten zu machen? Ich habe einige Verbesserungen gegenüber diesen Arten von Implementierungen in Betracht gezogen:

  • Anstatt ein Array von Referenzen zu verwenden, könnte ich ein Array vom primitiven Integer-Typ verwenden, das in ein Array von Referenzen auf Knoten indiziert, deren Größe nahe an der Anzahl der tatsächlichen Knoten liegt.
  • Ich könnte Strings in 4-Bit-Teile aufteilen, was Knoten-Arrays der Größe 16 auf Kosten eines tieferen Baums ermöglichen würde.
RokL
quelle

Antworten:

2

Wofür benutzt du diesen Versuch? Was ist die Gesamtzahl der Wörter, die Sie halten möchten, und wie spärlich sind ihre konstituierenden Charaktere? Und am wichtigsten ist, ist ein Versuch überhaupt angemessen (im Vergleich zu einer einfachen Karte des Präfixes zur Liste der Wörter)?

Ihre Idee einer Zwischentabelle und des Ersetzens von Zeigern durch Indizes funktioniert, vorausgesetzt, Sie haben einen relativ kleinen Satz kurzer Wörter und einen spärlichen Zeichensatz. Andernfalls besteht die Gefahr, dass der Platz in Ihrer Zwischentabelle knapp wird. Und wenn Sie nicht nur einen extrem kleinen Satz von Wörtern betrachten, sparen Sie nicht wirklich so viel Platz: 2 Bytes für einen Kurzschluss gegenüber 4 Bytes für eine Referenz auf einem 32-Bit-Computer. Wenn Sie mit einer 64-Bit-JVM arbeiten, sind die Einsparungen höher.

Ihre Idee, die Zeichen in 4-Bit-Blöcke aufzuteilen, wird Ihnen wahrscheinlich nicht viel ersparen, es sei denn, alle erwarteten Zeichen befinden sich in einem äußerst begrenzten Bereich (möglicherweise in Ordnung für Wörter, die auf US-ASCII in Großbuchstaben beschränkt sind, wahrscheinlich nicht mit einem allgemeinen Unicode-Korpus ).

Wenn Sie einen spärlichen Zeichensatz haben, ist a HashMap<Character,Map<...>>möglicherweise die beste Implementierung. Ja, jeder Eintrag wird viel größer sein, aber wenn Sie nicht viele Einträge haben, erhalten Sie einen Gesamtsieg. (als Randnotiz: Ich fand es immer lustig, dass der Wikipedia-Artikel über Versuche ein Beispiel zeigte - vielleicht immer noch -, das auf einer gehashten Datenstruktur basiert und die räumlichen / zeitlichen Kompromisse dieser Wahl völlig ignorierte)

Schließlich möchten Sie vielleicht einen Versuch ganz vermeiden. Wenn Sie sich ein Korpus normaler Wörter in einer menschlichen Sprache ansehen (10.000 Wörter im aktiven Gebrauch, mit Wörtern von 4 bis 8 Zeichen Länge), sind Sie wahrscheinlich mit a viel besser dran HashMap<String,List<String>, wobei der Schlüssel das gesamte Präfix ist.

Parsifal
quelle
- Referenzen sind 8 Bytes auf 32-Bit- und 16 Bytes auf 64-Bit-Computern. - Dies dient der automatischen Vervollständigung. - Die Mehrheit der Zeichen in Zeichenfolgen liegt im ASCII-Bereich, es werden jedoch einige mitteleuropäische Zeichen eingegeben. Aus diesem Grund wollte ich eine kleinere Verzweigung als 256, weil es eine große Anzahl von Zeichen ausschneidet. Ich sehe HashMap <String, List <String >> nicht besser oder schneller oder weniger speicherintensiv, obwohl es wirklich einfach zu schreiben und zu verwenden ist. Aber ich werde die HashMap-Idee <Character, Map> akzeptieren. Wäre in Ordnung für Zeichen über 128 (in meinem Fall selten - wäre schlecht für chinesischen Text).
RokL
4

Wenn Sie die Zeichenfolgen in UTF8 codieren, können Sie den Standard-256-Verzweigungsversuch verwenden und trotzdem Unicode-kompatibel sein

Außerdem sollten Sie beachten, dass nur etwa 70 Zeichen von den möglichen 128 ASCII-Zeichen (die alle in UTF8 auf 1 Byte codiert sind) am stärksten gefunden werden, die Sie dafür optimieren können (z. B. die allgemeinen Digraphen anstelle der nicht verwendeten Steuerzeichen )

Ratschenfreak
quelle
Ich weiß, dass UTF8 so dargestellt werden kann. Dies löst jedoch immer noch nicht den Speicherverbrauch, der immer noch ziemlich hoch ist. Das Vertauschen von Zeichen in den Basisbereich von 256 würde einige Wechselsätze erfordern. Ich bezweifle, dass es sich lohnen würde. Was UTF-8 angeht ... das ist eigentlich ein Thema, über das ich gerade nachdenke. Java String verwendet UTF-16-Zeichen, die ich leicht erhalten kann. Ich kann diese Byte für Byte codieren. Oder ich kann auf UTF-8 konvertieren und das verwenden. Zu diesem Zeitpunkt ist mir unklar, ob die Kosten für die Konvertierung von UTF-16 zu UTF-8 unerschwinglich sind oder nicht.
RokL
In welcher Sprache verwenden Sie diese meistens? Der Versuch, für alles zu optimieren, ist unmöglich (oder es wäre bereits geschehen), also optimieren Sie für den allgemeinen Fall
Ratschenfreak
1
Dies ist einer der wenigen Anwendungsfälle, in denen CESU-8 UTF-8 vorzuziehen wäre: Der große Vorteil besteht darin, dass es trivial ist, von einem UTF-8-Codepunkt zum entsprechenden CESU-8-Codepunkt zu gelangen (während Sie dies benötigen würden) 1-2 UTF-16-Codepunkte zu dekodieren, um zu den entsprechenden UTF-8-Codepunkten zu gelangen).
Joachim Sauer
1
@ Ratchetfreak Java. Obwohl ich denke, dass die Frage auf die meisten Sprachen verallgemeinert werden kann. Ich denke, in C könnte man einfach einen Zeiger auf setzen byte*, um einen beliebigen Typ in einem bitweisen Versuch zu codieren.
RokL
@UMad Ich meinte, in welchen Sprachen die Eingabezeichenfolgen sein werden (Englisch, Französisch, Deutsch, ...)
Ratschenfreak