パスワードを忘れた? アカウント作成
587213 journal

kzkの日記: trie木 1

日記 by kzk

by ruby

--- 実行結果 ---
[]
      [a]
            [i]
                  [u]
                        [e]
                              [o]
                  [j]
                        [i]
                              [n]
                  [k]
                        [o]
            [u]
      [t]
            [u]
string = aiko
string = iko
string = ko
string = o
search aiko = true
string = aijo
string = ijo
string = jo
string = o
search aijo = false

anthyのsrc-diclibで使われているデータ構造。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by tabatee (1637) on 2005年01月05日 0時43分 (#674262) 日記
    anthyのtrieはpatricia trieという変種です。(素のtrieより良く使われていると思います)
    bitごとの二分木になっていることと、複数の分岐を一つのノードに格納することが素のtrieと異なる点です。(たとえば、0001と0000を格納する場合、prefixの000は一つのノードに格納されます)

    anthyで使った理由は (1)検索がそこそこ速く、速度が安定していること。 (2)ツリーの中で要素の順序が保存されていること。 (3)最長マッチの検索ができること。などがあったと記憶しています。
typodupeerror

Stay hungry, Stay foolish. -- Steven Paul Jobs

読み込み中...