Trie mit Assoziation zwischen Wörtern

Question

Ich habe einen Anwendungsfall, wo ich Wörter korrigieren möchte. Ich habe richtige und falsche Wörter [Rechtschreibfehler] gesetzt. Ich bevölke den Trie mit allen Wörtern. Ich habe sowohl die richtige als auch die falsche Version jedes Wortes.

im Fall Nun, wenn ich Wort als „a“ für die Korrektur zu erhalten,

- ich es in trie.if trie zu suchen hat dieses Wort, ich will mit der richtigen Version dieses Wortes, dieses Wort assoziieren.

Lösung: ich kann korrekte Version ["a1"] des Wortes am letzten Knoten des falschen Wortes in Trie einstellen. Und kann es auf "a1" auflösen.

Aber ich muss korrekte Version jedes Wortes am letzten Knoten speichern, die den Speicherfußdruck erhöhen wird. Da habe ich alle Wörter geladen, um [richtig/falsch] zu trie. Gibt es eine Möglichkeit, eine Verbindung zwischen korrektem und falschem Wort herzustellen, ohne das gesamte Wort im letzten Knoten erneut als Wert zu speichern? Irgendein Zeiger?

public class TrieNode<T> { 

    private Map<Character, TrieNode<T>> childs; 
    private boolean complete; 
    private T value; 

    .... 
    } 

Answer 1

Sie könnten ein einzelnes Wörterbuch dafür verwenden. In C# würde, dass sein:

Dictionary<string, string> MisspellingsLookup = new Dictionary<string, int>(); 

Der Schlüssel ist die falsche Schreibweise, und der Wert ist die korrekte Schreibweise.

Nun werden einige Wörter häufig auf mehrere Arten falsch geschrieben. Zum Beispiel wird "Gelegenheit" oft als "Gelegenheit" oder "Gelegenheit" falsch geschrieben. Wenn Sie den von den mehreren Rechtschreibfehlern verwendeten Speicher reduzieren möchten, können Sie während der Konstruktion ein temporäres Wörterbuch verwenden. Immer, wenn Sie einen Rechtschreibfehler hinzufügen, suchen Sie die richtige Schreibweise im Wörterbuch für gute Wörter, und wenn sie bereits vorhanden ist, verwenden Sie diesen Wert. Sie speichern also nur einen Verweis auf ein vorhandenes Wort, anstatt eine neue Zeichenfolge zu erstellen. Hier ein Beispiel:

Dictionary<string, string> GoodWords = new Dictionary<string, int>(); 
Dictionary<string, string> Misspellings = new Dictionary<string, string>(); 

void AddMisspelling(string misspelled, string correct) 
{ 
    string goodWord; 
    if (!GoodWords.TryGetValue(correct, out goodWord)) 
    { 
     goodWord = correct; 
     GoodWords.Add(correct, correct); 
    } 

    // Always use goodWord here, so you're not creating duplicate strings. 
    Misspellings.Add(misspelled, goodWord); 
} 

Wenn Sie also fertig sind hinzufügen, können Sie das GoodWords Wörterbuch löschen um Platz zu sparen:

GoodWords = null; 

ein Wörterbuch hier empfehlen, weil es fast sicher weniger Speicher verwenden werden und Nachschlagen ist O (1) und nicht O (Wortlänge).