ファイル名検索を高速化するためにRubyとGroonga（Rroonga）を使った話（Windows対応）

きっかけ

最近、自分のマシンのファイル数が激増して、findコマンドやdir /b /sコマンドが遅くなりました。

findコマンドとは、指定したフォルダー（ディレクトリ）内のファイルの一覧を表示するUnix系OSのコマンドです。
ファイル名の一部を指定して、ファイル名検索することもできます。Windowsでは、dir /b /sコマンドで
似たようなことができます。エクスプローラーの右上の検索ボックスを思い浮かべてもらってもよいです。

以下のコマンドは、両方ともカレントフォルダー以下の拡張子が.logのファイルを一覧表示します。

Unix

$ find . -name "*.log"

Windows

> dir /b /s "*.log"

ただし、ファイルが増えてファイルパスが深くなると、フォルダー階層を行ったり来たりするのでどんどん遅くなります。
この問題を解決するために、RubyとGroonga（Rroonga）を使ってみました。

オブジェクト指向スクリプト言語 Ruby
Groonga - カラムストア機能付き全文検索エンジン
RubyでGroonga使って全文検索 - ラングバ

アウトプットした方が身に付きそうなので、チュートリアル形式で書いてみます。
進め方はRroongaのチュートリアルを参考にしました。

RubyとGroongaを使ったファイル名検索のチュートリアル

Rubyのインストール

前提条件は、Rubyというプログラミング言語を実行できる環境がインストールされていることです。
インストールされていない場合は、以下のリンク先などから最新版をダウンロードしてインストールします。

RubyInstaller for Windows

2013年12月11日時点では、2.0.0-p353あたりを使うのがよさそうです。
http://dl.bintray.com/oneclick/rubyinstaller/rubyinstaller-2.0.0-p353.exe

RroongaとGroongaのインストール

Rubyがインストールできたら、RubyからGroongaを使うためのライブラリーであるRroongaをインストールします。
Rroongaをインストールすると、Groongaも一緒にインストールされます。

コマンドプロンプトなどを起動して、以下のコマンドを実行してください。（少し時間がかかります）

> gem install rroonga

gem listコマンドでrroongaが出てくればOKです。

> gem list

作業用フォルダー作成

既存のファイルと混ざらないように、作業用フォルダーを作成します。好きな場所で結構ですが、
ここではユーザーのホームフォルダーの下にgroonga_workというフォルダーを作成し、
さらにその下にdbというフォルダーを作成します。

> cd C:\Users\ユーザー名 （Windows7の場合）
> mkdir groonga_work
> cd groonga_work
> mkdir db
> cd db

Rubyとの対話ツールを起動

いちいちファイルを修正して実行するのは面倒なので、対話ツールを使います。
対話ツールを使えば、コードを直接実行して結果を確認することができます。
irbという対話ツールがRubyに付属しており、手軽に使えるので便利です。

ここでは出力を見やすくするために--simple-promptオプションを付けますが、なくてもいいです。

> irb --simple-prompt

Groongaライブラリーの読み込み

requireメソッドを使って、Groongaライブラリーを読み込みます。

irb

>> require "groonga"

これで準備完了です。次項からは、Groongaのオブジェクトを操作していきます。

エンコーディングの設定

はじめに、エンコーディングの設定です。Unixの場合は:utf8、Windowsの場合は:sjisにします。
登録するデータによっては、Windowsでも:utf8にする場合もあります。

irb

>> Groonga::Context.default_options = {:encoding => :sjis}
=> {:encoding=>:sjis}

データベース作成

データベースを作成するときは、作成したい場所のファイルパスを指定します。
拡張子は.dbにするのがお作法らしいので、find.dbとしておきます。

irb

>> Groonga::Database.create(:path => "find.db")
=> #<Groonga::Database id: <nil>, name: (anonymous), path: <find.db>, domain: (nil), range: (nil), flags: <>>

データベースを作成すると、指定した場所に以下のファイルが作成されます。

C

find.db
find.db.0000000
find.db.001

以降は、特に指定しなくてもここで作成したデータベースが使われます。
irbを終了してしまった場合など、既存のデータベースを使うときはopenメソッドで開き直します。

>> Groonga::Database.open("find.db")

テーブル作成

ファイルパスを主キーとして、ファイル名のカラムを持つテーブルを作成します。

Groongaにはテーブルの種類が4つありますが（ 8.5. テーブル — Groonga ドキュメント）、
ファイルパスは前方一致検索できるとうれしいのでパトリシアトライを使ってみます。

テーブル名はFiles、カラム名はfilename、カラムのデータ型はText型にします。

irb

>> Groonga::Schema.create_table("Files", :type => :patricia_trie) do |table|
?>   table.text("filename")
>> end
=> [#<Groonga::Schema::TableDefinition:0x2b45008 @name="Files", @definitions=[#<Groonga::Schema::ColumnDefinition:0x2b44cf0 @name="filename", @options={:persistent=>true, :named_path=>nil}, @type="Text">], @options={:context=>#<Groonga::Context encoding: <:sjis>, database: <#<Groonga::Database id: <nil>, name: (anonymous), path: <find.db>, domain: (nil), range: (nil), flags: <>>>>, :type=>:patricia_trie}, @table_type=Groonga::PatriciaTrie>]

インデックス用テーブル作成

もうひとつ、インデックス（索引）を使った検索をするためのテーブルを作ります。
このテーブルには、トークナイザー（文字列を単語に分解するオブジェクト）を指定します。
ここでは、TokenBigramというトークナイザーを指定しています。（参考：7日目の記事）

また、:normalizer => :NormalizerAutoを設定すると、大文字小文字の区別なく検索できます。

ブロック内では、先ほど作成したFilesテーブルのfilenameカラムに対するインデックスを定義しています。

irb

>> Groonga::Schema.create_table("Terms",
?>                              :type => :patricia_trie,
?>                              :normalizer => :NormalizerAuto,
?>                              :default_tokenizer => "TokenBigram") do |table|
?>   table.index("Files.filename")
>> end
=> [#<Groonga::Schema::TableDefinition:0x2b2ea90 @name="Terms", @definitions=[#<Groonga::Schema::IndexColumnDefinition:0x2b2e7d8 @name=nil, @options={:persistent=>true, :named_path=>nil}, @target_table="Files", @target_columns=["filename"]>], @options={:context=>#<Groonga::Context encoding: <:sjis>, database: <#<Groonga::Database id: <nil>, name: (anonymous), path: <find.db>, domain: (nil), range: (nil), flags: <>>>>, :type=>:patricia_trie, :normalizer=>:NormalizerAuto, :default_tokenizer=>"TokenBigram"}, @table_type=Groonga::PatriciaTrie>]

テーブル作成後にはファイルが増えます。

C

find.db
find.db.0000000
find.db.0000100
find.db.0000101
find.db.0000102
find.db.0000103
find.db.0000103.c
find.db.001

テーブルのレコード数を確認

テーブルのレコード数を確認してみます。
テーブルにはGroonga["テーブル名"]でアクセスでき、レコード数はsizeメソッドで取得できます。

irb

>> Groonga["Files"].size
=> 0

まだ何も登録していないので、期待通り0でした。

ファイルパスの収集

それでは、検索対象のファイルパスを収集します。
一例として、親フォルダー（".."）以下のファイルパスを登録してみます。

ファイルパスの取得には、Rubyのfindライブラリーを使います。
ファイル数が少なければDir.globでもいいですが、findの方が逐次処理されるので
高速だと思います。File.expand_pathを使っているのは絶対パスで登録するためです。

irb

>> require "find"
=> true
>> Find.find(File.expand_path("..")) do |path|
?>   Groonga["Files"].add(path, :filename => File.basename(path))
>> end
=> nil

ファイル数が多いと数分～数十分程度かかる場合がありますが、
マシンを使っていないときに実行するようにしておけば、それほど苦にはならないと思います。

テーブルの内容を確認

ファイルパスがデータベースに登録されていることを確認します。
Groonga["Files"]はRubyの配列のように使えるので、eachメソッドなどが使えます。
主キーの値は_keyで取得できます。

irb

>> Groonga["Files"].size
=> 10
>> Groonga["Files"].each {|record| puts record._key}
C:/Users/ユーザー名/groonga_work
C:/Users/ユーザー名/groonga_work/db
C:/Users/ユーザー名/groonga_work/db/find.db
C:/Users/ユーザー名/groonga_work/db/find.db.0000000
C:/Users/ユーザー名/groonga_work/db/find.db.0000100
C:/Users/ユーザー名/groonga_work/db/find.db.0000101
C:/Users/ユーザー名/groonga_work/db/find.db.0000102
C:/Users/ユーザー名/groonga_work/db/find.db.0000103
C:/Users/ユーザー名/groonga_work/db/find.db.0000103.c
C:/Users/ユーザー名/groonga_work/db/find.db.001
=> nil

ちゃんと登録されていました。

全文検索

いよいよ検索です。検索にはselectメソッドを使います。検索方法はいくつかあり、
=~演算子を使うとトークナイザーで作成したインデックスを使った部分一致検索になるようです。

まずは検索条件にdbを指定して検索してみます。

irb

>> records = Groonga["Files"].select {|record| record.filename =~ "db"}
=> #<Groonga::Hash id: <2147483651>, name: (anonymous), path: (temporary), domain: <Files>, range: (nil), flags: <WITH_SUBREC>, size: <9>, encoding: <:utf8>, default_tokenizer: (nil), normalizer: (nil)>
>> records.size
=> 9
>> records.each {|record| puts record._key}
C:/Users/ユーザー名/groonga_work/db
C:/Users/ユーザー名/groonga_work/db/find.db
C:/Users/ユーザー名/groonga_work/db/find.db.0000000
C:/Users/ユーザー名/groonga_work/db/find.db.0000100
C:/Users/ユーザー名/groonga_work/db/find.db.0000101
C:/Users/ユーザー名/groonga_work/db/find.db.0000102
C:/Users/ユーザー名/groonga_work/db/find.db.0000103
C:/Users/ユーザー名/groonga_work/db/find.db.0000103.c
C:/Users/ユーザー名/groonga_work/db/find.db.001
=> nil

ファイル名にdbが含まれている9レコードがヒットしました。

別の条件でも検索してみます。001ではどうでしょうか。

irb

>> records = Groonga["Files"].select {|record| record.filename =~ "001"}
=> #<Groonga::Hash id: <2147483653>, name: (anonymous), path: (temporary), domai
n: <Files>, range: (nil), flags: <WITH_SUBREC>, size: <1>, encoding: <:utf8>, de
fault_tokenizer: (nil), normalizer: (nil)>
>> records.size
=> 1
>> records.each {|record| puts record._key}
C:/Users/ユーザー名/groonga_work/db/find.db.001
=> nil

ファイル名に001が含まれているレコードは他にもありますが、ヒットしたのは1レコードだけでした。
おそらく、トークナイザーによって切りのいい場所で区切られているためだと思います。

慣れていないと戸惑いそうですが、単なる部分一致検索よりもノイズ（余分な検索結果）が少ない
という利点があります。使用するトークナイザーによって、結果も変わってきそうです。

なお、==演算子を使うと完全一致検索になるようです。

irb

>> records = Groonga["Files"].select {|record| record.filename == "db"}
=> #<Groonga::Hash id: <2147483649>, name: (anonymous), path: (temporary), domai
n: <Files>, range: (nil), flags: <WITH_SUBREC>, size: <1>, encoding: <:utf8>, de
fault_tokenizer: (nil), normalizer: (nil)>
>> records.size
=> 1
>> records.each {|record| puts record._key}
C:/Users/ユーザー名/groonga_work/db
=> nil

これくらいの数だとありがたみがありませんが、ファイル数が何十万何百万と増えるにしたがって、
速度の違いが実感できるようになります。

文字化けしたら

出力が文字化けしてしまったら、ファイルパス文字列のエンコーディングと、Groongaに設定したエンコーディングが
合っていなかったのかもしれません。エンコーディングの設定を間違えた場合、以下のような状態になっていると思われます。

• GroongaとRubyは文字列のエンコーディングがAだと思っている
• しかし、実際の文字列の中身のエンコーディングはBになっている

Windowsで文字化けする場合の多くは、AがUTF-8、BがWindows-31J（Shift_JIS）だと思います。

Groongaのエンコーディングを修正して登録し直してもいいですが、force_encodingを使う手もあります。
force_encodingを使うと、実際の文字列の中身を変更することなく、Rubyが持っているエンコーディング情報を
変更することができます。引数には実際の文字列の中身のエンコーディングを指定します。

irb

>> records.each {|record| puts record._key.force_encoding("Windows-31J")}

正しいエンコーディングがわからなければ、Encoding.find("locale")を指定するとうまくいく場合が多いです。

irb

>> records.each {|record| puts record._key.force_encoding(Encoding.find("locale"))}

前方一致検索

せっかくテーブルの種類をパトリシアトライにしたので、前方一致検索も試してみます。
言い忘れていましたが、Groonga["Files"]は変数に入れると便利です。
File.expand_path("~")で、ユーザーのホームフォルダーを取得することができます。

irb

>> files = Groonga["Files"]
=> #<Groonga::PatriciaTrie id: <256>, name: <Files>, path: <find.db.0000100>, domain: <ShortText>, range: (nil), flags: <>, size: <9>, encoding: <:sjis>,default_tokenizer: (nil), normalizer: (nil)>
>> prefix = File.join(File.expand_path("~"), "groonga_work", "db", "find.db.000")
=> "C:/Users/ユーザー名/groonga_work/db/find.db.000"
>> records = files.prefix_search(prefix)
=> #<Groonga::Hash id: <2147483649>, name: (anonymous), path: (temporary), domain: <Files>, range: (nil), flags: <>, size: <6>, encoding: <:sjis>, default_tokenizer: (nil), normalizer: (nil)>
>> records.size
=> 6
>> records.each {|record| puts record._key}
C:/Users/ユーザー名/groonga_work/db/find.db.0000103.c
C:/Users/ユーザー名/groonga_work/db/find.db.0000103
C:/Users/ユーザー名/groonga_work/db/find.db.0000102
C:/Users/ユーザー名/groonga_work/db/find.db.0000101
C:/Users/ユーザー名/groonga_work/db/find.db.0000100
C:/Users/ユーザー名/groonga_work/db/find.db.0000000
=> nil

prefix_searchメソッドにファイルパスを指定するだけで、前方一致検索ができました。

成果物

毎回、長々とコードを入力するのは面倒なので、短いコマンドにまとめたgemを作成して
12月9日（いー肉の日）にバージョン0.0.1をリリースしました。名前はRroongaにあやかって
Findrr（ふぁいんどる）にしました。

GitHub: https://github.com/myokoym/findrr
RubyGems.org: https://rubygems.org/gems/findrr

まだ機能は少ないですが、使い方はこんな感じです。

インストール

> gem install findrr

インストールすると、findrrコマンドが使えるようになります。

ファイルパス収集

findrr collectコマンドでファイルパスを収集します。
↓はカレントフォルダー以下のファイルパスを収集する例です。

> findrr collect .

Findrrは、ホームフォルダーの下に.findrrというフォルダーを作成し、その中にデータベースファイルを作成します。

ファイル名を全文検索

findrr searchコマンドでファイル名を全文検索します。
↓はdbにマッチするファイル名を検索する例です。

> findrr search db

まとめ

ファイル名検索が遅いという問題を解決するために、RubyとGroonga（Rroonga）を使って高速化を実現しました。
今回はファイル名検索に特化した話でしたが、いろいろな場面に応用できそうだと感じます。