このゴールデンウィークはまとまった休日を取ることができた。 そこでこの休日 (の自分の自由時間) 中に自然言語処理界隈で有名な何かの実装に取り組んで、開発スキルの経験値をあげようと思いいたり、 今まで何度も実装してみようと思って挫折してきたダブル配列を実装することを課題にしてみた。 ダブル配列はTRIEを実装するためのデータ構造の一つとして有名であり、形態素解析器のMeCabなどで用いられている。 入力がキーの集合に含まれるかどうかを調べる時間は、保存したキーの集合のサイズではなく、入力の長さに依存する。 そのため、高速にキーを検索することができる。

開発成果はここにアップロードした。 基本的にはダブル配列法によるトライ検索の実現法を素直に実装している。

休日中に実装できたの機能は以下の通りで、Key-Value Storeとしてなら利用することが可能な実装になっている (共通接頭辞検索などの機能は現在はない):

  • ダブル配列の動的な構築
  • キーの存在の確認
  • キーに対する値の取得
  • キーの削除
  • ダブル配列の保存・読み込み

動的な構築の高速化のための工夫は他の論文で提案されているらしいが、その実装は間に合わなかった。 またマルチバイト文字の対応はできていないため、日本語処理にはまだ使えない。 (まだ時間があったのでマルチバイトにも対応した。このあたりの文字の対応にはStatic Double Array Trie (DASTrie)を眺めて勉強させていただいた。 2017/05/07 17:43追記)

実装をするにあたり、他に参照した情報源を以下に挙げる:

いままで実装しようと持って挫折してきたものが時間をかければ最低限作れるようになったという意味で進捗を感じた。 この休日では間に合わず、今後試してみたいと思っているのは以下の通り:

  • マルチバイト文字の対応 (対応した 2017/05/07 17:43追記)
  • (構築、検索のベンチマーク 2017/05/07 17:43追記)
  • 分類器のオレオレ実装と組み合わせてメモリに載らない大きさの素性サイズのデータで文書分類の実験をしてみる

関連記事


最近の記事