词与词之间的关联

Question

我有一个用法，我想纠正单词。我有一套正确和不正确的单词[拼写错误]。我用所有的话填充了trie。我对每个词都有正确和不正确的版本。

如果我得到一个“A”字来更正，

--我在trie中搜索它。如果trie有这个词，我想把这个词和这个词的正确版本联系起来。

解决方案：我可以在Trie中错误单词的最后一个节点设置单词的正确版本[“A1”]。并可将其解析为“A1”。

但是我必须在最后一个节点存储每个单词的正确版本，这将增加内存足印。因为我把所有的单词都加载到trie[正确/不正确]。是否有任何方法我可以使正确和不正确的单词之间的关联，而不是再次存储整个单词在最后一个节点作为值？有指针吗？

public class TrieNode<T> {

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

    ....
    }

Answer 1

你可以用一本字典来做这个。在C#中，这将是：

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

关键是拼写错误，值是正确的拼写。

现在，一些单词通常有多种拼写错误。例如，“community”经常被错误地拼写为“ocassion”或“athysion”。如果您想减少多个拼写错误所使用的内存，可以在构造过程中使用临时字典。无论何时添加拼写错误，都要在好单词词典中查找正确的拼写，如果已经存在，则使用该值。因此，您所做的就是存储对现有单词的引用，而不是创建新字符串。这里有一个例子：

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(1)而不是O（单词长度）。