今作りかけのもので、素性(文字列片)を格納するのに Trie を使っていたのだけど、50万件を超えたあたりからメモリに載らなくなってきて。
まあ dict を使っためちゃめちゃナイーブな実装だったので、そろそろダメかなあとは思っていたんだけど(苦笑)。
というわけで、それよりきっと省スペース＆きっと高速だろうと期待して Double Array を Python で実装してみた。
参考にしたのは WEB+DB Press vol. 64 の徳永さんの記事。
現時点での実装がこちら。
ソート済みのテキスト列を与えると、Double Array を構築。
get を呼び出すと、最初に与えたテキスト列の中でのキー文字列のインデックスを返す。
シンプル機能。
trie = da.DoubleArray() trie.initialize(["ca", "cat", "deer", "dog", "fox", "rat"]) print trie.get("ca") # => 0 print trie.get("cat") # => 1 print trie.get("deer") # => 2 print trie.get("dog") # => 3 print trie.get("c") # => None print trie.get("xxx") # => None
想定しているアプリケーションがあるので、いろいろそれに合わせた仕様や構成になっている。
- できあがった DA は最後に numpy.ndarray に突っ込んでいる。その方が消費メモリが少ないから。
- 記事では、まず trie を構築してからノードをたどって DA に再構築する手順だったが、最初に言ったとおり、もともと trie がメモリに載らないから作り始めたわけで……。二分探索で根っこからノードを探していき、子ノードはキューに放り込んで、枝を DA に突っ込む、そしたらまたキューから取ってきて繰り返し、という構成にした。遅いかなあ。
- DA のライブラリ側で入力をソートしないのは、返す値を「テキスト列の中でのキー文字列のインデックス」にしたいから。もし違反があれば例外を投げる。
- 記事では check に「次の空き要素のインデックスの符号を反転したものを入れ」ることで構築を高速化できるとあったが、実際に考えてみると「前の空き要素」も必要に思えたので、それを base に入れるようにした。「細かいところでバグを生みやすく、実装は面倒です」とあったとおり、しょうもないバグに二日ほど悩まされた(苦笑)。
- アプリで必要だったので、単純にキーに対して値を返すだけではなく、現在見ているサブツリー(を指すインデックス)を返したり、そのサブツリーから1文字進む(子ノードのインデックスを返す)機能などがある。
- 静的な DA を生成するだけで、修正(追加)や削除の機能は無し。素性を追加・削除したらどうせ value が変わるので、アプリ的に全体再構成せざるを得ないから。
そんな感じで一応動くものはできたのだけど、なんかこれでいいのかなあという部分がちらほらあるので(value は配列じゃあなくて連想配列の方がいいのかも？？？)、やっぱり原論文も読もうかなあ。今頃かい！ とか言われそうだけどｗ
