Erweitern Trie zu höherer Anzahl von Blättern

Ich muss ein Wörterbuch mit tries machen, die Anzahl der Buchstaben im Alphabet wird von 26 auf 120 steigen, und daher wird die Anzahl der Blattknoten exponentiell ansteigen. Welche Optimierungen kann ich verwenden, damit meine Zeit zum Suchen, Einfügen und Löschen nicht exponentiell zunimmt?Erweitern Trie zu höherer Anzahl von Blättern

EDIT macht die Frage klarer, sorry für den Mangel an Details Ich bin eine Mehrweg-trie wie Radix Baum mit und einigen Änderungen daran vornehmen. Meine Frage ist, wenn ich weiß, dass die Wortgröße (mit Sicherheit) von 26 auf 120 steigt, wird es die Tiefe des Baumes erhöhen. Ist es möglich, den Anstieg in der Tiefe zu verringern, indem der Schlüssel auf mehr als 64 Bits erhöht wird (das Register kann maximal 64 Bits ausgeben)?

Quelle

2016-03-24 Anonymous

Warum wird es exponentiell zunehmen? –

Es ist unklar, was Sie fragen. Erweitert sich dein Alphabet oder wächst die Länge der Wörter? Ein konkretes Beispiel wäre hilfreich. –

Anfänglich wurde der Trie so entworfen, dass er Wörter mit einer Länge von 32 Zeichen verarbeiten kann, jetzt muss der Trie mit Wörtern der Länge 120 Zeichen umgehen. Die Länge der Wörter wächst. –

Es ist oft besser, binäre Versuche mit Pfadkomprimierung (Patricia probiert) basierend auf der binären Darstellung Ihrer Schlüssel zu verwenden. Auf diese Weise erhalten Sie die Vorteile des kleinstmöglichen Alphabets, und Sie haben immer noch nur 2 Knoten (einen Blatt und einen internen) pro Schlüssel.

Quelle

2016-03-25 04:37:21

Ich mache Änderungen an der Art und Weise, wie ein Radix-Baum implementiert wird (ein Mehrweg-Trie, wobei M = 2^k), wobei k die Anzahl der für die Suche verwendeten Bits ist. Wenn k = 6 ist, dann passt es zu der Größe von Registern der 64-Bit-CPU-Architektur, aber angenommen, dass ich k auf 10 erhöhe, wie kann ich das implementieren? Hinweis: Ich möchte M statt Tiefe erhöhen, um die Zeit zu verringern. –

Obwohl es möglicherweise einige Optimierungen gibt, aber unser Lookup, die Zeit für das Einfügen und Löschen wird nicht exponentiell zunehmen. Wenn Sie Ihr Alphabet erhöhen, bedeutet dies, dass Ihre Trie-Knoten jetzt größer sind. Der Pfad zu jedem Wort hat immer noch die gleiche Länge wie die Buchstaben im Wort.

Quelle

2016-03-25 04:42:59 displayName

Erweitern Trie zu höherer Anzahl von Blättern

Antwort

Verwandte Themen