TRIE 勉強用レポジトリ
Ruby
Latest commit 9ad0e3f Dec 8, 2010 @tily delete unnecessary file.

README.md

He Tried

TRIE に関する勉強用のレポジトリ。

TRIE の実装

  • ハッシュ
  • 配列
    • 空間効率が悪いため実用的ではない
  • リスト
  • ダブル配列 (Double-Array)
    • ChaSen や MeCab で採用されている方式
    • base と check の 2 つの配列を用いて TRIE を表現する
  • Succint Data Structure

TRIE の周辺

  • パトリシア木
  • AC 法 (エイホ-コラシック法、Aho-Corasick algorithm)

TRIE クラスに実装されているべきメソッド

  • 挿入
    • insert(key, value)
      • TRIE にキーを挿入する
      • ただし DoubleArray の場合には入力の順序がソート済みである必要あり
  • 検索
    • exact_match(key)
      • 引数の文字列に完全一致するキーが TRIE に含まれているかどうかを真偽値で返す
    • common_prefix_search(key)
      • 引数の文字列と共通の接頭辞を持つキーの配列を返す (共通接頭辞探索)
  • 列挙
    • each
      • 検証用、ブロックを受け取り TRIE の各ノードで yield する
  • その他
    • save
      • TRIE をファイルに出力する (gzip 圧縮のオプションとかあったほうがよい?)
    • fetch
      • 用途よく分からない、darts のソースの中にあった

メモ

  • Double-Array + マルチバイト文字列

Links

Copyright

Copyright (c) 2010 tily. See LICENSE.txt for further details.