go-shellinford
https://bitbucket.org/oov/go-shellinford/
echizen_tm さんの shellinford をGo言語で使いたくて愚直に移植を試みていて、最低限動くようになってきたので公開します。データの読み込み／書き出しが未実装とか（多分）速度が遅いとか、課題も色々あります。
なお使用可能なのはウェーブレット行列のみで、ウェーブレット木は移植していません。
環境変数が設定されている環境で
サンプルプログラムも一応用意しました。
shellinford の C++ のソースコードは綺麗で読みやすくて、テストケースも書かれていたのでGo言語側でも同じようなテストケースを書き、考えずに淡々と書いていっても大体上手く移植できた。
std::map でキーがソート済みであることを利用した処理があることに気付かずにGo言語の map に単純に置き換えてしまい少しハマったものの、処理を少しずつ理解しながら読み直してたら自然と気付いて解決した。
まだ理解してない部分も多いけど自分のペースで地道に読み解こうと思う。
ひょんなことから接尾辞配列とかウェーブレット木とかウェーブレット行列とか FM-Index とかに興味を持って調べ始めたものの、難しいことは得意ではないのでできることから始めてそれを取っ掛かりにしようと思って愚直な移植をやってみた次第。
Go言語の標準パッケージにも index/suffixarray があって、現在のものは "Faster Suffix Sorting" という論文を元にした実装みたいです。
2013-09-20 追記 ----
ブロックソーティングを書きなおして 0.1 秒強速くなりました。
2013-09-21 追記 ----
色々見直して更に 0.1 秒強速くなりました。
2013-09-21 追記2 ----
ウェーブレット行列構築部分を書き直して2倍弱ぐらい速くなりました。
最初のリリースから比べると 0.827436secs から 0.378995secs になりました。
2013-09-23 追記3 ----
データのインポート／エクスポートの実装と、キャストを減らすため型を見直し。
もうちょっとだけ速くなって 0.341257secs ぐらいに。
2013-09-25 追記4 ----
0.334682secs ぐらいに。
echizen_tm さんの shellinford をGo言語で使いたくて愚直に移植を試みていて、最低限動くようになってきたので公開します。
なお使用可能なのはウェーブレット行列のみで、ウェーブレット木は移植していません。
環境変数が設定されている環境で
$ go get bitbucket.org/oov/go-shellinford/shellinfordみたいな感じで使えるようになります。
サンプルプログラムも一応用意しました。
$ cd $GOPATH/src/bitbucket.org/oov/go-shellinford/example $ go run main.go 2142 Entry added. (0.002163secs) Creating indexes...done. (0.827436secs) Keyword "探偵" found 19 entries. (0.000079secs) Night Walker -真夜中の探偵- 1 Hit(s) 探偵オペラ ミルキィホームズ 1 Hit(s) 時空探偵ゲンシクン 1 Hit(s) CLAMP学園探偵団 1 Hit(s) 魔人探偵脳噛ネウロ 1 Hit(s) あにゃまる探偵 キルミンずぅ 1 Hit(s) 心霊探偵 八雲 1 Hit(s) 名探偵ホームズ 1 Hit(s) わんぱく探偵団 1 Hit(s) 快傑蒸気探偵団 1 Hit(s) 探偵学園Q 1 Hit(s) 名探偵コナン 1 Hit(s) ファーブル先生は名探偵 1 Hit(s) 素敵探偵ラビリンス 1 Hit(s) 魔探偵ロキRAGNAROK 1 Hit(s) 探偵少年カゲマン 1 Hit(s) アリス探偵局 1 Hit(s) アガサ・クリスティーの名探偵ポワロとマープル 1 Hit(s) やっとかめ探偵団 1 Hit(s) $ cat /proc/cpuinfo | grep "model name" model name : Intel(R) Atom(TM) CPU D510 @ 1.66GHz model name : Intel(R) Atom(TM) CPU D510 @ 1.66GHz model name : Intel(R) Atom(TM) CPU D510 @ 1.66GHz model name : Intel(R) Atom(TM) CPU D510 @ 1.66GHz大体こういう感じです。CPU が Atom D510 のマシンで 2142 件のアニメタイトルのインデックス構築に 0.8秒強ぐらい。
shellinford の C++ のソースコードは綺麗で読みやすくて、テストケースも書かれていたのでGo言語側でも同じようなテストケースを書き、考えずに淡々と書いていっても大体上手く移植できた。
std::map でキーがソート済みであることを利用した処理があることに気付かずにGo言語の map に単純に置き換えてしまい少しハマったものの、処理を少しずつ理解しながら読み直してたら自然と気付いて解決した。
まだ理解してない部分も多いけど自分のペースで地道に読み解こうと思う。
ひょんなことから接尾辞配列とかウェーブレット木とかウェーブレット行列とか FM-Index とかに興味を持って調べ始めたものの、難しいことは得意ではないのでできることから始めてそれを取っ掛かりにしようと思って愚直な移植をやってみた次第。
Go言語の標準パッケージにも index/suffixarray があって、現在のものは "Faster Suffix Sorting" という論文を元にした実装みたいです。
2013-09-20 追記 ----
ブロックソーティングを書きなおして 0.1 秒強速くなりました。
2013-09-21 追記 ----
色々見直して更に 0.1 秒強速くなりました。
2013-09-21 追記2 ----
ウェーブレット行列構築部分を書き直して2倍弱ぐらい速くなりました。
最初のリリースから比べると 0.827436secs から 0.378995secs になりました。
2013-09-23 追記3 ----
データのインポート／エクスポートの実装と、キャストを減らすため型を見直し。
もうちょっとだけ速くなって 0.341257secs ぐらいに。
2013-09-25 追記4 ----
0.334682secs ぐらいに。