はじめに
Susumu Yataさんが作られたDarts-cloneは、Darts（Double-ARray Trie System）というライブリのクローンで、共通接頭辞検索を実現するデータ構造のダブル配列（Double Array）の実装である。Darts-cloneは、DartsとAPI互換性があり、検索の機能や速度そのままに、辞書サイズの削減を実現している。ダブル配列は、MeCabをはじめ、多くの形態素解析器で採用されているデータ構造で、例えばSudachiPyは、Darts-clonenのPython bindingを使用している。また、Darts-cloneは、Taku Kudoさんが書かれた形態素解析器に関する本でも取り上げられており、ダブル配列を利用するなら標準的なものと言える。
以前から、Ruby製の形態素解析器のSuikaで、辞書の読み込みの遅さを改善したいと思っていた。解決策にDarts-cloneを利用することを考えたが、Ruby bindingが見つからなかったので、まずはコレを作ることにした。
dartsclone | RubyGems.org | your community gem host
使い方
インストールは、native extensionをビルドできれば、gemコマンドでインストールできる。別で外部ライブラリをインストールする必要はない。
gem install dartsclone
darts-clone.rbによる共通接頭辞検索は以下のようになる。
require 'dartsclone' da = DartsClone::DoubleArray.new # 辞書を構築する. 単語は事前にソートされている必要がある. keys = ['東京', '東京都', '東京都中野区', '東京都庁'] da.build(keys) # 共通接頭辞を検索する. 検索結果は, 単語と添字によるArrayを返す. k, v = da.common_prefix_search('東京都中野区') p k # => ["東京", "東京都", "東京都中野区"] p v # => [0, 1, 2] # 検索結果がゼロ件の場合は、空のArrayを返す. p da.common_prefix_search('中野区') # => [] # 完全一致検索もできる. 添字を返す. p da.exact_match_search('東京都中野区') # => 2 # 辞書にない単語の場合は-1を返す. p da.exact_match_search('中野区') # => -1 # 外部ファイルへの保存・読込は次のようになる. da.save('foo.dat') da2 = DartsClone::DoubleArray.new da2.open('foo.dat') p da2.common_prefix_search('東京都中野区') # => [["東京", "東京都", "東京都中野区"], [0, 1, 2]]
Darts-cloneの仕様上、辞書を作成するbuildメソッドに渡す単語のArrayは、ソートされている必要がある。最初の単語の並びに意味がある場合は、buildメソッドに、その添字によるArrayをvaluesキーワード引数で渡すとよい。
require 'dartsclone' # ソートされていない単語によるArray. base_keys = ['うえお', 'いうえ', 'あいう'] # 単語とその添字によるArrayを作成する. base_sets = base_keys.map.with_index { |v, i| [v, i] }.sort_by { |v| v.first } p base_sets # => [["あいう", 2], ["いうえ", 1], ["うえお", 0]] # 単語と添字それぞれでArrayを作る. keys = base_sets.map(&:first) vals = base_sets.map(&:last) p keys # => ["あいう", "いうえ", "うえお"] p vals # => [2, 1, 0] # ダブル配列を作り検索する. da = DartsClone::DoubleArray.new da.build(keys, values: vals) # 検索で元の配列の添字が返る. p da.exact_match_search('あいう') # => 2
おわりに
Darts-cloneは、完成されたライブラリであるが、更新あればdarts-clone.rbでも追随したいと思う。また、bugfixはもちろんのこと、私のnative extension力の向上にあわせて改善していきたいと思う。次はSuikaに適用してみて、辞書の読み込み速度改善に効果があるかを、調査・検討したい。
