単語間の関連性を持つトライ

Question

私はどこで単語を訂正したいのですか？ 正しい単語と間違った単語[スペルミス]が設定されています。 トライにすべての単語を入力します。 私はすべての単語の正しいバージョンと正しくないバージョンの両方を持っています。

今場合は、私は「」補正のため、

としての単語を取得する場合 - 私はtrie.ifトライでそれを検索するには、この言葉を持って、私はこの言葉の正しいバージョンでこの言葉を関連付けます。

解決方法： トライの間違った単語の最後のノードで正しいバージョン["a1"]を設定できます。それを "a1"に解決できます。

しかし、私はメモリの足のプリントを増加させる最後のノードに各単語の正しいバージョンを格納する必要があります。 私はすべての単語がtrie [正しい/間違っている]に読み込まれているので。 正しい単語と間違った単語の間に関連付けを行う方法はありますか？最後のノードに単語全体を値として再度保存する必要はありませんか？ ポインタはありますか？

public class TrieNode<T> { 

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

    .... 
    } 

Answer 1

これには1つの辞書を使用できます。 C＃では、次のようになります。

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

キーにはスペルミスがあり、値は正しいスペルです。

ここで、いくつかの単語には一般に複数の方法でスペルミスがあります。たとえば、「機会」のスペルが間違っている場合があります。複数のスペルミスによって使用されたメモリを減らす場合は、作成中に一時的な辞書を使用できます。スペルミスを追加するたびに、良い単語辞書の正しいスペルを検索し、すでにある場合はその値を使用します。つまり、新しい文字列を作成するのではなく、既存の単語への参照を保存するだけです。ここでは例です：

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); 
} 

あなたは言葉の追加が完了したら、あなたがスペースを節約するためにGoodWords辞書をクリアすることができます。

GoodWords = null; 

それはほぼ確実に、より少ないメモリを使用しますので、私はここに辞書をお勧めします、検索はO（単語長）ではなくO（1）です。