Double Array 実装してみた - 木曜不足
今作りかけのもので、素性(文字列片)を格納するのに Trie を使っていたのだけど、50万件を超えたあたりからメモリに載らなくなってきて。 まあ dict を使っためちゃめちゃナイーブな実装だったので、そろそろダメかなあとは思っていたんだけど(苦笑)。 というわけで、それよりきっと省スペース＆きっと高速だろうと期待して Double Array を Python で実装してみた。 参考にしたのは WEB+DB Press vol. 64 の徳永さんの記事。 現時点での実装がこちら。 https://github.com/shuyo/iir/blob/master/trie/da.py ソート済みのテキスト列を与えると、Double Array を構築。 get を呼び出すと、最初に与えたテキスト列の中でのキー文字列のインデックスを返す。 シンプル機能。 trie = da.DoubleAr
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
最近のDoubleArrayの性能 - 射撃しつつ前転 改
DoubleArrayの性能に関して、最近は少し改善されているかも知れませんとあるので、具体的にどれぐらい改善されているのか、少し書いてみます。もちろん、現実逃避です。 まず、DoubleArrayがなんなのかというところから説明をします。DoubleArrayは、簡単に言うとTrieを実現するためのデータ構造の一種です。日本語ではダブル配列と呼ばれているようです。Trieに関しては横着プログラミング 第6回: chatty: 小うるさい端末あたりを読めば良いでしょうか。要するにTreeを表現するためのデータ構造です。使い道はいろいろありますが、辞書的なものに使われることが多いでしょうか。 Trieを単純に実現しようとすると、すごくたくさんメモリを使ってすごく速い実装をするか、速度を多少犠牲にしてメモリ消費量を削減するかの選択を迫られます。多くの場合はメモリを節約しないと使いものにならない
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
