Trie が提供すべき操作について検討してみる
nokuno さんの記事「オープンソースのTrieライブラリまとめ」あたりを参考に、まず既存の Trie ライブラリ群がどのような API を提供しているのかを調査し、その上でこれから Trie を実装する場合に、どのような操作・API を提供すべきかを検討した結果のメモです。 記事にあるすべての Trie 実装を確認するのはしんどいので、代表的な感じのものを適当にピックアップしてみました。 Tx ... 岡野原さんによる簡潔データ構造を利用した Trie の実装。 prefixSearch() ... prefix search。Trie に格納されている文字列の中で、対象文字列の接頭辞としてもっとも長く一致する文字列を探し出す。common prefix search で列挙される文字列のうち、長さが最長のものと同じ。 commonPrefixSearch() ... common p
Ruby で Double-Array を実装して Common-Prefix Search を試してみる - P A R A G R A P H S
lib/trie/double_array.rb at master from tily's ruby-gardening - GitHub Double-Array (ダブル配列) は トライ木を実装するためのアルゴリズムの 1 つで、他の実装よりも高速に TRIE から文字列を検索できるらしい。ChaSen や MeCab で、形態素解析を行うために必要な Common-Prefix Search (共通接頭辞探索) を行うために使われている。これを理解のために Ruby で実装してみた。 基本的な動作確認 ここに書いてある bird, bison, cat の 3 単語で構築した Double-Array の例。 コード： require 'trie/double_array' da = Trie::DoubleArray.new da.build(%w|bird bison cat
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
