Javaでプレフィックスツリーを実装する方法

1. プレフィックス ツリー

1. プレフィックス ツリーとは

辞書ツリー (トライ ツリー) は、文字列の保存と検索によく使用されるツリー データ構造です。ディクショナリ ツリーの中心的な考え方は、文字列間に共通のプレフィックスを使用してストレージ スペースを節約し、クエリの効率を向上させることです。これはマルチツリーであり、各ノードは文字列の接頭辞を表し、ルート ノードから葉ノードまでのパスが文字列を構成します。

辞書ツリーのルート ノードには文字が含まれません。各子ノードは文字を表します。ルート ノードから任意のノードへのパス上の文字は、ノードが表す文字列に接続されます。各ノードは 1 つ以上の文字列を格納でき、通常はフラグを使用して、ノードによって表される文字列が存在するかどうかをマークします。一連の文字列の中から文字列を検索する必要がある場合、辞書ツリーを使用して効率的な検索操作を実現できます。

2. プレフィックス ツリーの例

たとえば、文字列配列 {"goog", "google", "bai", "baidu", "a"} のプレフィックス ツリーを作成します。現時点では、プレフィックス ツリーのいくつかの特徴がはっきりとわかります:

• ルート ノードは文字を格納しません

• プレフィックス ツリーはマルチフォーク ツリー

• プレフィックス ツリーの各ノードは 1 文字を保存します

• 同じプレフィックスを持つ文字列は同じパスに保存されます

• プレフィックス ツリーでは、文字列の末尾にも終了マークが付きます。プレフィックス ツリーの

Likou に関する質問 208 は、プレフィックス ツリーを実装することです: Li Kou

1. プレフィックス ツリーのデータ構造

コードを書くとき、私は次のようにすることを好みます。ハッシュを使用する テーブルはノード情報を格納するために使用されますが、一部のテーブルはノード情報を格納するために配列を使用することもできます。これらは本質的に同じです

public class Trie {
    Map<Character, Trie> next;
    boolean isEnd;
    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }
    public void insert(String word) {
    }
    public boolean search(String word) {
        return false;
    }
    public boolean startsWith(String prefix) {
        return false;
    }
}

2. 文字列を挿入します

    public void insert(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                trie.next.put(c, new Trie());//创建当前结点
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        trie.isEnd = true;
    }

3. 文字列を検索します String

    public boolean search(String word) {
        Trie trie = this;//获得根结点
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        return trie.isEnd;
    }

4. 接頭辞を見つけます

    public boolean startsWith(String prefix) {
        Trie trie = this;//获得根结点
        for (char c : prefix.toCharArray()) {
            if (trie.next.get(c) == null) {//当前结点不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        return true;
    }

次のステップは、接頭辞ツリーに関するいくつかの質問に答えることです

##3. 辞書にある最長の単語

# 1. 質問の説明

文字列配列

words

で構成される英語辞書を指定します。

words

内の最長の単語を返します。この単語は、

words

辞書内の他の単語に 1 文字を徐々に追加することによって形成されます。

実行可能な回答が複数ある場合は、回答の中で辞書順が最も小さい単語を返します。応答がない場合は、空の文字列が返されます。

リコウ: リコウ2. 問題分析これは典型的なプレフィックス ツリーの質問ですが、この質問にはいくつかの特別な要件があり、返される答えは次のとおりです:

1. 最長の単語

2. この単語は他の単語から徐々に構成されます

3. 同じ長さの場合、辞書順で最小の単語が返されます

したがって、プレフィックスツリーの関連コードを修正する必要がある 文字列を1つずつ挿入するコードは変更しない 主な修正は検索コードである trie.next.get(c) == null 条件に判定を追加するfalse の場合は、各ノードにフラグ true が必要であり、各ノードに単語が存在することを示し、最終的に最長の単語 (リーフ ノードの単語) がステップごとに形成されます。

rree

以上がJavaでプレフィックスツリーを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。