79

文字列からさまざまなオブジェクトへの多くのマッピングを格納する Java プログラムがあります。

現在、私のオプションは、ハッシュ (HashMap 経由) またはバイナリ検索 (TreeMap 経由) に依存することです。人気のある高品質のコレクション ライブラリに、効率的で標準的なトライベースのマップ実装があるかどうか疑問に思っています。

私は過去に自分で書いたことがありますが、可能であれば標準的なものを使いたいと思います。

簡単な説明: 私の質問は一般的なものですが、現在のプロジェクトでは、完全修飾クラス名またはメソッド シグネチャによってインデックス付けされた多くのデータを扱っています。したがって、多くの共有プレフィックスがあります。

4

14 に答える 14

34

Limewire がGoogle Guava に貢献している Trie の実装を見たいと思うかもしれません。

于 2009-03-08T17:51:51.843 に答える
10

コアJavaライブラリにはトライデータ構造はありません。

これは、試行が通常文字列を格納するように設計されているのに対し、Javaデータ構造はより一般的であり、通常は任意の文字列を保持しているためですObject（等式とハッシュ操作の定義）が、 Comparableオブジェクトに限定される場合もあります（順序の定義）。「一連の記号」には一般的な抽象化はありませんが、文字列には適しています。他の種類の記号でCharSequenceも何かできると思います。Iterable

考慮すべきもう1つのポイントは、Javaで従来のトライを実装しようとすると、JavaがUnicodeをサポートしているという事実にすぐに直面することです。スペース効率を高めるには、トライ内の文字列をシンボルのサブセットに制限するか、シンボルでインデックス付けされた配列に子ノードを格納する従来のアプローチを放棄する必要があります。これは、試行がコアライブラリに含めるのに十分な汎用と見なされないもう一つの理由であり、独自のライブラリを実装したり、サードパーティのライブラリを使用したりする場合は注意が必要です。

于 2012-04-16T16:59:37.323 に答える
8

Apache Commons Collections v4.0 は、トライ構造をサポートするようになりました。

詳細については、org.apache.commons.collections4.trieパッケージ情報を参照してください。特に、PatriciaTrieクラスを確認してください。

PATRICIA Trie (英数字でコード化された情報を取得するための実用的なアルゴリズム) の実装。

PATRICIA Trie は、圧縮された Trie です。トライの端にすべてのデータを格納する (および空の内部ノードを持つ) 代わりに、PATRICIA はすべてのノードにデータを格納します。これにより、非常に効率的なトラバーサル、挿入、削除、先行、後続、プレフィックス、範囲、および選択 (オブジェクト) 操作が可能になります。すべての操作は最悪でも O(K) 時間で実行されます。ここで、K はツリー内の最大項目のビット数です。実際には、操作には実際には O(A(K)) 時間がかかります。ここで、A(K) はツリー内のすべてのアイテムの平均ビット数です。

于 2014-10-20T11:54:55.263 に答える
7

並行ツリーもチェックしてください。基数ツリーとサフィックス ツリーの両方をサポートし、同時実行性の高い環境向けに設計されています。

于 2013-08-21T19:53:39.403 に答える
1

以下は、Trie の基本的な HashMap 実装です。一部の人々はこれが便利だと思うかもしれません...

class Trie {

    HashMap<Character, HashMap> root;

    public Trie() {
        root = new HashMap<Character, HashMap>();
    }

    public void addWord(String word) {
        HashMap<Character, HashMap> node = root;
        for (int i = 0; i < word.length(); i++) {
            Character currentLetter = word.charAt(i);
            if (node.containsKey(currentLetter) == false) {
                node.put(currentLetter, new HashMap<Character, HashMap>());
            }
            node = node.get(currentLetter);
        }
    }

    public boolean containsPrefix(String word) {
        HashMap<Character, HashMap> node = root;
        for (int i = 0; i < word.length(); i++) {
            Character currentLetter = word.charAt(i);
            if (node.containsKey(currentLetter)) {
                node = node.get(currentLetter);
            } else {
                return false;
            }
        }
        return true;
    }
}
于 2014-12-09T12:28:19.423 に答える
1

Apache のコモンズ コレクション: org.apache.commons.collections4.trie.PatriciaTrie

于 2015-11-27T12:44:07.583 に答える
1

必要なのはorg.apache.commons.collections.FastTreeMapだと思います。

于 2009-03-08T17:09:19.513 に答える
1

完全に Java ライブラリを試すことができます。これにはPatriciaTrie実装が含まれています。この API は小さく、使い始めるのが簡単で、Maven 中央リポジトリで利用できます。

于 2016-11-05T11:44:29.977 に答える
0

この TopCoderも参照してください(登録が必要です...)。

于 2009-03-08T17:44:37.430 に答える
0

ソートされたマップが必要な場合は、試してみる価値があります。そうでない場合は、ハッシュマップの方が優れています。文字列キーを使用したハッシュマップは、標準の Java 実装よりも改善できます: 配列ハッシュ マップ

于 2012-05-21T08:52:42.330 に答える