2

私は Trie データ構造を持っており、瞬く間に 100,000 個の要素を検索します。ただし、検索された文字列で始まる単語のみを検索します。たとえば、「Fi」は「Final」を見つけますが、「GooFi」は見つけられず、「GooFi」も返したいと思います。そのため、この場合、これが正しい構造であるかどうかを尋ねています。私はそれを自分で実装し、単体テストを作成したので、これまでのところ機能しています。私が必要としているのは、私の目標を達成する方法のヒントです。誰かにコードを書いてもらいたくありません。それが私がここにいる理由ではありません。とにかく、ここに私の検索の実装があります:

public List<string> Seach(string word)
{
    List<string> results = new List<string>();
    this.DoSearch(this.Root, 0, new StringBuilder(word), results);
    return results;
}

private void DoSearch(TrieNode currentNode, int currentPositionInWord, StringBuilder word, List<string> results)
{
    if (currentPositionInWord >= word.Length)
    {
        this.DfsForAllWords(currentNode, word, results);
        return;
    }

    char currentChar = word[currentPositionInWord];

    bool containsKey = currentNode.Children.ContainsKey(currentChar);
    if (containsKey)
    {
        if (currentPositionInWord == word.Length - 1)
        {
            results.Add(word.ToString());
        }

        TrieNode child = currentNode.Children[currentChar];
        this.DoSearch(child, ++currentPositionInWord, word, results);
    }
}

private void DfsForAllWords(TrieNode currentNode, StringBuilder word, List<string> results)
{
    foreach (var node in currentNode.Children.ToArray())
    {
        word.Append(node.Value.Value);
        if (node.Value.IsWord)
        {
            results.Add(word.ToString());
        }

        this.DfsForAllWords(node.Value, word, results);
        word.Length--;
    }
}

どんな助けでも大歓迎です。

4

2 に答える 2

0

https://github.com/gngeorgiev/Trie

誰かがそれを必要とするなら、ここにTrieのレポがあります。接頭辞と部分文字列の検索をサポートします。

于 2014-07-09T09:29:10.190 に答える