0

三分探索木を変更して単語が存在することを確認し、その単語で始まる (またはその単語で終わる) すべての単語を検索することは可能でしょうか? たとえばdo=>dog dogsなど。

サンプルコードはこちらのサイトから。最初にすべての単語を三分木にロードしてから、メソッドを使用して単語が存在するかどうかを確認できます。

public class TernaryTree
{
    private Node m_root = null;

    private void Add(string s, int pos, ref Node node)
    {
        if (node == null) { node = new Node(s[pos], false); }

        if (s[pos] < node.m_char) { Add(s, pos, ref node.m_left); }
        else if (s[pos] > node.m_char) { Add(s, pos, ref node.m_right); }
        else
        {
            if (pos + 1 == s.Length) { node.m_wordEnd = true; }
            else { Add(s, pos + 1, ref node.m_center); }
        }
    }

    public void Add(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        Add(s, 0, ref m_root);
    }

    public bool Contains(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        int pos = 0;
        Node node = m_root;
        while (node != null)
        {
            int cmp = s[pos] - node.m_char;
            if (s[pos] < node.m_char) { node = node.m_left; }
            else if (s[pos] > node.m_char) { node = node.m_right; }
            else
            {
                if (++pos == s.Length) return node.m_wordEnd;
                node = node.m_center;
            }
        }

        return false;
    }
}

class Node
{
    internal char m_char;
    internal Node m_left, m_center, m_right;
    internal bool m_wordEnd;

    public Node(char ch, bool wordEnd)
    {
        m_char = ch;
        m_wordEnd = wordEnd;
    }
}

これにより、私は頭の中で大きくなります:(
その単語を取得する方法は何でもかまいません。しかし、私はそのレベルのアルゴリズムに弱いです..
これに関する質問を重複させないことを願っています. .

4

1 に答える 1

1

そのために三分木を使用することは可能ですが、お勧めしません (そうするのは簡単ではありません)。

使用できる2つの異なるアプローチがあると思います。

A.、三分木の代わりに標準のトライを使用すると、トライに含まれるアイテムの数に関係なく、シーク時間が一定と見なされます。AC# の実装は達成可能ですが、Trie には平均的/高レベルのアルゴリズム知識が必要であることを覚えておいてください。

B.、標準のソート済み配列 (string[]) を使用します。要件はプレフィックスに基づいてオートコンプリートを作成することだけであるため、すべての単語を string[] に保存し、その上でバイナリ検索を開始します。シーク時間は一定ではなく対数ですが、その配列に何百万もの単語が格納されている場合でも、各シークはミリ秒未満で測定できます (たとえば、その配列に百万の単語がある場合、20 回の操作のみ)探しているものを見つける必要があります)。二分探索が成功しなかった場合でも、最も近い一致のインデックスが得られます (ただし、インデックスは負の値になり、一致が失敗したことを示します)。したがって、この配列では次のようになります。

A 
C
D 
E

B を検索すると、A を指すインデックス 0 が取得されます。ステップアップを開始すると、「B」(または例では「犬」) の後に項目が表示されます。

したがって、二分検索後に完全一致または部分一致があったとしても、検索されたキーワードが辞書の単語の先頭に来るまで、配列からアイテムをリストし続けます。

于 2012-01-25T09:53:36.763 に答える