Trieデータ構造：無視された宝石

プログラマーとしての最初の日から、私たちはすべてデータ構造を扱ってきました。配列、リンクリスト、ツリー、セット、スタック、キューは私たちの日常の仲間であり、経験豊富なプログラマーはそれらをいつ、なぜ使用するかを知っています。 この記事では、ワードゲームなどの特定の機能を備えたアプリケーションドメインで、見過ごされがちなデータ構造であるトライが実際にどのように輝いているかを見ていきます。

トライの例としてのワードゲーム

手始めに、簡単な単語パズルを考えてみましょう。4x4の文字ボードですべての有効な単語を見つけ、隣接する文字を水平、垂直、または斜めに接続します。 たとえば、次のボードでは、文字「W」、「A」、「I」、および「T」が接続して「WAIT」という単語を形成していることがわかります。

すべての有効な単語を見つけるための素朴な解決策は、左上隅から始めて、深さ優先からより長いシーケンスに移動し、最初の行の2番目の文字から再び開始するというようにボードを探索することです。 4x4ボードでは、垂直、水平、斜めの動きが可能で、長さが1〜16文字の12029640シーケンスがあります。

今、私たちの目標は、この有効な単語チェッカー、つまり語彙を実装するための最適なデータ構造を見つけることです。 覚えておくべきいくつかのポイント：

• 論理的な観点からは、各単語のコピーが1つだけ必要です。つまり、語彙はセットです。
• 特定の単語について、次の質問に答える必要があります。
  • 現在の文字シーケンスは有効な単語で構成されていますか？
  • このシーケンスで始まる長い単語はありますか？ そうでない場合は、深さ優先探索を中止できます。深さ優先を行うと、有効な単語が生成されないためです。

2番目のポイントを説明するために、次のボードについて考えてみます。辞書には「ASF」で始まる単語がないため、後続の動きを調べる意味はありません。

これらの質問にできるだけ早く答えるために、データ構造が必要です。 〜O（1）アクセス時間（シーケンスをチェックするため）が理想的です！

語彙インターフェースは次のように定義できます（GitHubリポジトリについてはこちらをご覧ください）。

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

トライデータ構造と代替案

contains()メソッドを実装するには、要素を効率的に検索できるバッキングデータ構造が必要ですが、 isPrefix()メソッドでは、「次に大きい要素」を検索する必要があります。つまり、語彙を何らかの方法で並べ替えておく必要があります。

候補のリストからハッシュベースのセットを簡単に除外できます。このような構造では、 contains()を常時チェックできますが、 isPrefix()でのパフォーマンスは非常に低く、最悪の場合、全体をスキャンする必要があります。セットする。

まったく逆の理由で、ソートされたリンクリストを除外することもできます。これは、少なくとも検索された単語またはプレフィックス以上の最初の要素までリストをスキャンする必要があるためです。

2つの有効なオプションは、ソートされた配列に裏打ちされたリストまたはバイナリツリーを使用することです。
ソートされた配列に裏打ちされたリストで、バイナリ検索を使用して、現在のシーケンス（存在する場合）またはO（log2（n））のコストで次に大きい要素を見つけることができます。ここで、 nは辞書内の単語数です。

標準のjava.util.ArrayListとjava.util.Collections.binarySeachを使用して、このような順序を常に維持する配列に基づく語彙を実装できます。

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

二分木を使用することにした場合、実装はさらに短く、よりエレガントになる可能性があります（ここでもコードへのリンクがあります）。

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

どちらの場合も、各アクセスメソッド（ contains()およびisPrefix() ）のO（log n）パフォーマンスを期待できます。 スペース要件に関しては、アレイに裏打ちされた実装とツリーに裏打ちされた実装の両方でO（n + M）が必要です。ここで、nは辞書内の単語数、Mは辞書のバイトサイズ、つまり辞書の文字列。

トライアプリケーション：トライを使用する時期と理由

対数パフォーマンスと線形メモリは悪くありません。 ただし、アプリケーションドメインには、パフォーマンスの向上につながる可能性のあるいくつかの特性があります。

• すべての単語が小文字であると安全に想定できます。
• 句読点、ハイフン、アクセントなどのaz文字のみを受け入れます。
• 辞書には、複数形、共役動詞、複合語（例：house –> housekeeper）などの多くの語形変化が含まれています。 したがって、多くの単語が同じ語幹を共有します。
• 単語の長さには制限があります。 たとえば、4x4ボードで作業している場合、16文字を超えるすべての単語を破棄できます。

ここでトライ（「トライ」と発音）が登場します。しかし、トライとは正確には何ですか？ 試行は無視されたデータ構造であり、本には見られますが、標準ライブラリにはめったに見られません。

動機付けとして、まずコンピュータサイエンスのポスターの子である二分木について考えてみましょう。 ここで、二分木のパフォーマンスを分析し、操作xがO（log（n））であると言うとき、常に対数基数2について話します。しかし、二分木の代わりに三分木を使用した場合はどうなりますか。すべてのノードには3つの子があります（または、3つのファンアウト）。 次に、ログベース3について話します（これは、一定の要因によってのみですが、パフォーマンスの向上です）。基本的に、ツリーは広くなりますが短くなり、完全に下降する必要がないため、ルックアップの実行回数を減らすことができます。とても深い。

さらに一歩進んで、データ型の可能な値の数に等しいファンアウトを持つツリーがある場合はどうなりますか？

これがトライの背後にある動機です。 ご想像のとおり、トライは確かに木であり、いわばトライの木です。

ただし、文字列の並べ替えに使用するほとんどの二分木とは異なり、単語全体をノードに格納するものとは異なり、トライの各ノードは1つの文字を保持します（これについては後で説明します）。アルファベットの長さに等しい最大ファンアウトがあります。 この場合、アルファベットの長さは26です。 したがって、トライのノードの最大ファンアウトは26です。また、平衡二分木はlog2（n）の深さを持ちますが、トライの最大深さは単語の最大長に等しくなります。 （繰り返しますが、幅は広くなりますが短くなります。）

トライ内では、同じ語幹（接頭辞）を持つ単語は、語幹に対応するメモリ領域を共有します。

違いを視覚化するために、5つの単語で構成された小さな辞書を考えてみましょう。 ギリシャ文字がポインタを示していると仮定し、トライでは、赤い文字が有効な単語を保持しているノードを示していることに注意してください。

JavaTrieの実装

ご存知のように、ツリーでは、最大ファンアウトが2に固定されているため、子要素へのポインターは通常、左右の変数で実装されます。

26文字のアルファベットのインデックスを作成するトライでは、各ノードに26の可能な子があり、したがって26の可能なポインターがあります。 したがって、各ノードは26個の（ポインタを指す）サブツリーの配列を備えており、各値はnull（そのような子がない場合）または別のノードのいずれかである可能性があります。

では、どのようにしてトライで単語を検索するのでしょうか。 String sが与えられた場合、ツリーに存在する場合、単語の最後の文字に対応するノードを識別するメソッドは次のとおりです。

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

LOWERCASE.getIndex(s.charAt(i))メソッドは、アルファベットのi番目の文字の位置を返すだけです。 返されたノードで、ブールプロパティnodeは、ノードが単語の最後の文字、つまり前の例で赤でマークされた文字に対応することを示します。 各ノードは子の数のカウンターを保持しているため、このカウンターが正の場合、現在の文字列をプレフィックスとして持つ長い単語が辞書にあります。 注：ノードは、トライ内の位置に暗黙的に含まれているため、対応する文字への参照を保持する必要はありません。

パフォーマンスの分析

これらの状況でトライ構造が実際にうまく機能するのは、単語または接頭辞を検索するコストが固定されており、語彙のサイズではなく、単語の文字数のみに依存することです。

特定のドメインでは、最大16文字の文字列があるため、語彙に含まれる単語を見つけるには正確に16ステップが必要ですが、否定的な回答、つまり単語または接頭辞がトライに含まれていない場合は取得できます。最大16ステップでも！ 配列に基づくソート済みリストと文字列の比較に隠されているツリーの両方の実行時間計算量を計算するときに文字列の長さを以前に無視したことを考慮すると、ここでそれを無視して、ルックアップが行われたことを安全に述べることができますO（1）時間で。

スペース要件を考慮すると（そして、辞書のバイトサイズをMで示したことを思い出してください）、最悪の場合、2つの文字列がプレフィックスを共有していなければ、トライはMノードを持つ可能性があります。 しかし、辞書には高度な冗長性があることがわかったため、実行する必要のある圧縮がたくさんあります。 サンプルコードで使用されている英語の辞書は935,017バイトで、250,264ノードが必要で、圧縮率は約73％です。

ただし、これにも関わらず、圧縮されたトライでさえ、通常、ツリーや配列よりも多くのメモリを必要とします。 これは、ノードごとに、少なくとも26 x sizeof(pointer)バイトが必要であり、さらにオブジェクトと追加の属性にいくらかのオーバーヘッドが必要なためです。 64ビットマシンでは、各ノードに200バイト以上が必要ですが、文字列文字には1バイト、またはUTF文字列を考慮すると2バイトが必要です。

試行とパフォーマンステスト

では、パフォーマンスはどうですか？ 語彙の実装は、2つの異なる状況でテストされました。20,000,000のランダムな文字列をチェックすることと、同じ単語リストからランダムに生成された15,000のボードですべての単語を見つけることです。

4つのデータ構造が分析されました：配列に裏打ちされたソート済みリスト、バイナリツリー、上記のトライ、および文字自体のアルファベットインデックスに対応するバイトの配列を使用するトライ（マイナーで簡単に実装できるパフォーマンスの最適化）。 結果は次のとおりです（ミリ秒単位）。

ボードを解決するために行われた平均移動回数は2,188回です。 移動ごとに、単語ルックアップとプレフィックスルックアップが実行されます。つまり、すべてのボードをチェックするために、32Mを超える単語ルックアップと32Mのプレフィックスルックアップが実行されました。 注：これらは単一のステップで実行できます。説明をわかりやすくするために、これらを分離したままにしました。 それらを1つのステップで圧縮すると、ボードを解決するための時間がほぼ半分に短縮され、おそらくトライがさらに有利になります。

上記のように、単語ルックアップは、文字列を使用する場合でもトライでパフォーマンスが向上し、アルファベットインデックスを使用するとさらに高速になり、アルファベットインデックスは標準のバイナリツリーの2倍以上の速度で実行されます。 ボードを解くことの違いはさらに明白であり、高速のtrie-alphabet-indexソリューションはリストとツリーの4倍以上の速さです。

まとめ

トライは非常に特殊なデータ構造であり、ツリーやリストよりもはるかに多くのメモリを必要とします。 ただし、アルファベットの制限や文字列の最初の部分の冗長性の高さなど、特定のドメイン特性が適用される場合は、パフォーマンスの最適化に対処するのに非常に効果的です。

参考文献

トライとアルファベットの詳細な説明は、Robert Sedgewickの本「Algorithms、4thedition」の第5章にあります。 PrincetonのコンパニオンWebサイトには、AlphabetとTrieSTを実装するためのコードがあり、私の例よりも広範囲に渡っています。

トライの説明とさまざまな言語の実装はウィキペディアにもあり、このボストン大学のトライリソースも見ることができます。