洋食の日記

「た・である」調ではなく「です・ます」調で書きはじめれば良かったなと後悔してる人のブログです

ダブル配列ライブラリDarts-cloneのRuby bindingを作成した

はじめに

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に適用してみて、辞書の読み込み速度改善に効果があるかを、調査・検討したい。

github.com