トライ (データ構造)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
トライ木から転送)
ナビゲーションに移動 検索に移動
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ

トライ: trie)、デジタル木: digital tree)、プレフィックス木: prefix tree)とは、順序付きの一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス(接頭部)があり、ルート(根)には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。

キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。

トライは一種の決定性有限オートマトンと見ることもできるが、エッジ(枝)に対応する記号(文字)はその順序が暗黙のうちに決定される(辞書順など)。

キーは必ずしもノードに格納される必要はない。右図はトライの概念を示したもので実装は一般に異なる。

トライのキーは必ずしも文字列である必要はない。トライのアルゴリズムを文字列以外の任意のデータ構造に適用することは容易である。

利点と欠点(2分探索木との比較)[編集]

以下に2分探索木と比較したトライの主な利点を挙げる:

  • キー検索が高速である。長さ m のキー検索は最悪で O(m) の時間がかかる。2分探索木では O(log n) の時間であり、n は木を構成するノード数である(木の深さに応じた時間がかかり、2分探索木の深さは n の対数となる)。トライが検索処理で行う文字でインデックス付けした配列の操作なども、実際のマシンでは高速である。
  • 多数の短い文字列を格納する場合にはトライの方がメモリを節約できる。これはキーが明示的に格納されないためであり、複数のキーによってノードが共有されるためである。
  • トライは最も長いプレフィックスとマッチするので、あるキーと最も長いプレフィックスが共通なキーを効率的に捜すこともできる。そのような共通プレフィックスに対応したノードに新たに値を格納することもできる。
  • トライは木構造として平衡を保つ必要はない。2分探索木は深さが平衡していないと性能に悪影響がある(平衡2分探索木参照)。

また、トライの欠点は次の通り:

  • トライはキーの順序を与えるが、それは辞書式順序でなければならない。
  • トライは状況によっては極めて巨大になる。例えば、少数の非常に長い文字列を格納するトライなどである(この場合はパトリシア木が適している)。
  • トライのアルゴリズムは単純な2分探索木よりも複雑である。
  • データを文字列として表すのは常に簡単とは言えない。例えば、複雑なデータ構造や浮動小数点数などをキーとする場合、工夫が必要となる。

トライは基本的にキーとして文字列を必要とするが、様々なデータ型を文字列に変換することもできる。例えば、整数を単にビットの列と見れば、文字列と何ら変わらない。ルーティングテーブルやページテーブルではその性質から、プレフィックスが共通の整数がキーとしてよく使われる(つまり偏りがある)。

トライはキーの長さが可変でキー検索が失敗する場合があるとき(そのキー文字列がキーとされていない場合)、最も便利である。固定長のキーで常に検索が成功するならパトリシア木の方が適している。これは子ノードが1つしかないノードをその子ノードとまとめてしまう方法である(図の例で言えば、"i" のノードと "in" のノードをまとめる)。例えば、経路がほとんど分岐しない構造になっている場合、これはメモリ使用量を削減することになる。

アルゴリズム[編集]

トライは、検索と挿入の操作をサポートするノードのツリーである。Find はキー文字列の値を返し,Insert は文字列(キー)と値をトライに挿入する。Insert と Find はどちらも O(m) 時間で実行され、m はキーの長さである。

シンプルな Node クラスを使用して、トライ内のノードを表現することができる。

 class Node:
    def __init__(self) -> None:
        # (この実装のように)子にディクショナリーを使用しても、デフォルトでは子を辞書式ソートしないことに注意。
        # これは、次のセクション(ソート)で説明する辞書式ソートで必要である。
        self.children: Dict[str, Node] = {}  # 文字からノードへのマッピング
        self.value: Optional[Any] = None

children はノードの子への文字のディクショナリーであり、「終端」ノードは完全な文字列を表すノードであると言われていることに注意。

トライの値は以下のように調べることができる。

 def find(node: Node, key: str) -> Optional[Any]:
     """ノードのキーで値を検索する"""
     for char in key:
         if char in node.children:
             node = node.children[char]
         else:
             return None
     return node.value

このルーチンを少し変更して以下のために利用することができる。

  • トライに指定された接頭辞で始まる単語があるかどうかを確認するため、そして
  • 指定された文字列のいくつかの接頭辞に対応する最も深いノードを返すため。

挿入は、挿入する文字列に応じてトライを歩き、トライに含まれていない文字列の接尾辞に対応する新しいノードを追加することで行われる。

 def insert(node: Node, key: str, value: Any) -> None:
     """キーと値のペアをノードに挿入する"""
     for char in key:
         if char not in node.children:
             node.children[char] = Node()
         node = node.children[char]
     node.value = value

ソート[編集]

キーの集合の辞書式ソートは、各ノードの子を辞書式ソートした状態で、それらからトライを構築し、それを事前に順にトラバースして、葉の値だけを印刷することで実現できる[1]。このアルゴリズムは、基数ソートの一形態である[2]

トライはBurstortの基本的なデータ構造であり、キャッシュの効率的な利用により、(2007年当時は)最も高速な文字列ソートアルゴリズムとして知られていた[3]。現在はもっと速いものがある[4]

全文検索[編集]

サフィックスツリーと呼ばれる特別な種類のトライは、高速な全文検索を実行するためにテキスト中のすべてのサフィックスをインデックス化するために使用することができる。

性能の定量化[編集]

トライの探索時間は、キー文字列の長さが一定であれば O(1) とみなせるが、より詳細に検討する。キーが N 個あるとき、文字の種類が k なら、最も長いキーは logkN 文字がその長さの下限となる。このことから、トライの探索時間は厳密には Ω(logN) であり、これは2分探索と同じである。

この結果は必ずしもトライの利点を否定するものではない。トライの高速性の利点は個々の比較が高速である点にある。2分探索では文字列の比較を行い、一回の比較は比較対象の文字列の短いほうを m 文字としたとき O(m) が最悪時間となる。一方トライでは個々の比較は1文字の比較であるため、その時間は一定である。これは単に理論上の違いというわけではない。というのも2分探索木で末端に近いノードまで行くと常にプレフィックスが共通なノードで文字列比較を行うことになり、文字列比較時間が長くなってしまうのである。

応用[編集]

他のデータ構造の代替[編集]

既に述べたようにトライは2分探索木に比較して様々な利点がある。トライはハッシュテーブルの代替としても使用でき、次のような利点がある:

  • 理論上、平均検索性能は同じだが、実測するとトライの方が速い。
  • ハッシュテーブルの検索の最悪時間は O(N) である。
  • キーの衝突(コリジョン)が発生しない。
  • ハッシュ関数を用意する必要がない。
  • トライではキーの辞書順を自動的に生成できる。

トライをハッシュテーブルとして使用した際の欠点は次の通り:

  • 格納されている全キーを文字列として取り出すのが簡単ではない。
  • ハッシュテーブルよりもメモリ効率が悪い。
  • ハッシュテーブルはプログラミング言語に最初から用意されているが、トライはそうではない。

辞書表現[編集]

トライの典型的な応用として辞書の格納がある。例えば、携帯電話などで使われている。トライの利点として検索の高速性と新たなエントリの挿入やエントリの削除の容易性が活用されている。しかし、単に辞書の単語を格納するだけなら(つまり、各単語の意味などが必要とされない場合)、非輪状決定性有限オートマトンのほうがメモリ効率がよい。

トライはスペルチェッカなどの近似的マッチングアルゴリズムの実装にも適している。

擬似コード[編集]

以下の擬似コードは与えられた文字列がトライにあるかどうかを判定する汎用のアルゴリズムを示したものである。ここで、children は子ノード群の配列であり、terminal ノードとは格納された単語に対応するノードを意味する。

function find(node, key) {
  if (key is an empty string) {  # 基本ケース。キーが空文字列の場合
    return is node terminal?
  } else {  # 再帰ケース
    c = first character in key  # キーが空でないので、その1文字目を取り出す
    tail = key minus the first character  # 1文字目を除いた文字列
    child = node.children[c]  # 文字コードが配列キーとなる
    if (child is null) {  # 子がないので再帰できないがキーは空になっていない
      return false
    } else {
      return find(child, tail)
    }
  }
}

ソート[編集]

辞書式順序にキー文字列をソートする処理は次のようにトライで実現される:

  • 全キーをトライに挿入する。
  • 深さ優先探索のような決まった順序でトライから全キーを取り出す。

これは一種の基数ソートである。

トライを使って N 個のキーのソートを N 個のプロセッサで行うと(並列アルゴリズム)、その時間は Ω(1) となる。ただし、キーの長さはある一定の上限があるものとする。キーが共通のプレフィックスを持っていたり、同じキーが複数個あったりするので、並列処理の性能上の利点が小さくなるという問題はある。

全文検索[編集]

特殊なトライとしてサフィックス木がある。これを使って高速全文検索のためにテキストのサフィックス(接尾部)でインデックス付けを行うことができる。

実装の工夫[編集]

トライを二重連鎖木で実装した物。縦の矢印は子ポインタを表現し、横の点線の矢印は兄弟ポインタを表現する。このトライには baby, bad, bank, box, dad, dance が格納されている。リストはアルファベット順で走査出来るようにソートされている。

トライを表現する方法は何通りもある。メモリの使用量と操作の速さの間のトレードオフがある。

基本的な方法は、ノードに(文字, 子ポインタのリスト)を格納する方法である。これは単純であるが、木の葉の方に近づくと子供の少ないノードがたくさん出来るためメモリの無駄遣いである。

二重連鎖木[編集]

別の方法は、ノードに(文字, 子ノードへのポインタ, 兄弟ノードへのポインタ)の3つ組みを格納する方法である。つまり二重連鎖木である。子ノードへのポインタは1つ目の子供だけをさし、2つ目の子供は、その子供から兄弟ノードへのポインタを使い参照する。

三分探索木[編集]

更に別の方法は、子供の集合を2分探索木で表現する方法である。この場合、トライは三分探索木になる。

ダブル配列[編集]

1989年に青江順一がダブル配列を利用する方法を発表した[5]。トライは決定性有限オートマトンとして解釈する事が出来るが、決定性有限オートマトンはデフォルト(default)・ベース(base)・次(next) ・チェック(check)の4つの配列で表現できる[6][7]。トライの場合はデフォルトは不要である。その上で、s から t へ c により遷移する場合は、以下の関係が成立すれば良い。

check[base[s] + c] = s
next[base[s] + c] = t

動的に要素が増えていく場合 next と check は同じように増えていくのでまとめる事が出来るが、base は同じ速度では増えていかず分裂してしまう。そこで、ダブル配列では、base と next を統合し、以下の関係が成立するように管理する。

check[base[s] + c] = s
base[s] + c = t

すると、base と check だけが残り、この2つは同じ速さで増えていき、一つの構造体にまとめる事が出来る。

ある要素がトライに含まれているかどうか調べる際に、二重連鎖木を使った方法では、兄弟ノードはポインタ(連結リスト)をたどって行かないといけないが、ダブル配列では一発で遷移できる。

実装としては Theppitak Karoonboonyanan が libdatrie を公開している[8]

整数を格納するトライ[編集]

二分トライ[編集]

二分トライ: binary trie)やビット単位トライ: bitwise trie)とは、整数を格納するトライで、上位ビットから 0 また 1 で左右に分岐する[9]

高速化のためのテクニックとして、下記の2つの方法が使える。

  1. 葉ノードは子が無いので、子を指すポインタが空くので、葉ノード同士を双方向連結リストでつないでしまう。前後のノードを O(1) でたどれるようになる。
  2. jumpポインタをノードに付け、一気に葉ノードまでジャンプする。

x-高速トライ[編集]

x-高速トライ木の具体的な構造を例示する、4層の二分木。3層:(ラベルなし), 2層: (0) と (1), 1: (00) と (10)、0層: (001)、 (100) 、(101)。 3層のラベルのついていないのは根ノード。ノードの接続は、(ラベルなし)->(0), (ラベルなし)->(1), (0)->(00), 青い矢印で (0)->(001), (1)->(10), 青い矢印で (1)->(101), (00)->(001), 青い矢印でもう一本(00)->(001), (10)->(100), (10)->(101), (001)<->(100), (100)<->(101)。階層別にLSS<階層>というラベルのついた箱で囲まれている。
x高速トライの例。1 (0012), 4 (1002), 5 (1012)を格納する。青い矢印はdescendant pointerを表す。ノード(01)が無く、ノード(0)を見ることでpredecessor(0112) = 1であることがわかる。

x-高速トライ: x-fast trie)は、検索キーとして与えられた整数以上(以下)の値をもつ、キーに最も近い葉ノードを得る操作(successor, predecessor)を高速にできるようにした二分トライのバリエーションである。通常の二分トライとの相違点は、階層高さごとのハッシュテーブル、葉ノード同士の双方向連結リスト、中間ノードが子ノードを0側(1側)のひとつしか持たない時に格納される、その中間ノード下で最大(最小)値をもつ葉ノードへのリンク(descendant pointer)を持つことである。[10]。階層にたいして二分探索をおこなうことで、木に格納する整数のビット数 w に対し、Successor, Predecessorの時間計算量がO(log w)となる。1982年に Dan E. Willard が発表した[11]

y-高速トライ[編集]

y-高速トライ: y-fast trie)とは、格納する整数が w ビットの時、x-fast trie に全体の 1/w だけしか格納せず、残りを Treap などの平衡2分探索木に O(w) 個ずつに分けて入れる[12]。これにより全体の空間計算量が、実際に木に格納されたデータの数 n に対し O(n) となり、x-高速トライより改善する。また、追加・削除の時間計算量が O(log w) になる。1982年に Dan E. Willard が x-fast trie と同時に発表した[11]

関連項目[編集]

参考文献[編集]

  1. ^ Kärkkäinen, Juha. “Lecture 2”. University of Helsinki. Template:Cite webの呼び出しエラー:引数 accessdate は必須です。 “"The preorder of the nodes in a trie is the same as the lexicographical order of the strings they represent assuming the children of a node are ordered by the edge labels."”
  2. ^ Kallis, Rafael (2018年). “The Adaptive Radix Tree (Report #14-708-887)”. University of Zurich: Department of Informatics, Research Publications. Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
  3. ^ Ranjan Sinha and Justin Zobel and David Ring (Feb 2006). “Cache-Efficient String Sorting Using Copying”. ACM Journal of Experimental Algorithmics 11: 1–32. doi:10.1145/1187436.1187439. https://people.eng.unimelb.edu.au/jzobel/fulltext/acmjea06.pdf. 
  4. ^ J. Kärkkäinen and T. Rantala (2008). “Engineering Radix Sort for Strings”. In A. Amir and A. Turpin and A. Moffat. String Processing and Information Retrieval, Proc. SPIRE. Lecture Notes in Computer Science. 5280. Springer. pp. 3–14. doi:10.1007/978-3-540-89097-3_3 
  5. ^ Jun-ichi Aoe (1989). “An Efficient Digital Search Algorithm by Using a Double-Array Structure”. IEEE Transactions on Software Engineering 15 (9): 1066-1077. 
  6. ^ Stephen C. Johnson (1975). “YACC-Yet another compiler-compiler”. Computing Science Technical Report 32: 1-34. 
  7. ^ A.V. エイホ; R. セシィ; J.D. ウルマン; M.S. ラム (2009). コンパイラ―原理・技法・ツール (Information & Computing). ISBN 978-4781912295 
  8. ^ An Implementation of Double-Array Trie
  9. ^ 13.1 BinaryTrie: A digital search tree
  10. ^ Bose, Prosenjit; Douïeb, Karim; Dujmović, Vida; Howat, John; Morin, Pat (2010), Fast Local Searches and Updates in Bounded Universes, Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pp. 261–264, http://cccg.ca/proceedings/2010/paper69.pdf 
  11. ^ a b Willard, Dan E. (1983). “Log-logarithmic worst-case range queries are possible in space Θ(N)”. Information Processing Letters (Elsevier) 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3. ISSN 0020-0190. 
  12. ^ 13.3 YFastTrie: A Doubly-Logarithmic Time SSet
  • R. de la Briandais: File Searching Using Variable Length Keys. Proceedings of the Western Joint Computer Conference, 1959, pages 295–298.
  • E. Fredkin: Trie Memory. Communications of the ACM, 3(9):490-499, Sept. 1960.
  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.3: Digital Searching, pp.492–512.

外部リンク[編集]