!kiyoka.blog.2012_03 RSSPLAIN

Related pages: !kiyoka.blog.list
555555544444444444444444234222224444444444444444444444444444444444440444555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555505555555555555555555550555551555555555555555555555555505
5

kiyoka日記。NendoSekkaの開発や、最近思うことなど

5

最新10件!kiyoka.blog   過去記事一覧!kiyoka.blog.list

5

kiyoka.blog_header 

5

このブログを書いている人: 西山 清香(kiyoka) - twitter: @kiyokaEXT

5

5

 

5

 

4

kiyoka.2012_03_30[Sekka][KVS][TRIE] Sekkaにトライ木を実装するとしたら ver-2

4

 

4

先日の記事 「kiyoka.2012_03_07[Sekka][KVS][TRIE] Sekkaにトライ木を実装するとしたら ver-1」からの差分。

4

GitHub上で実際にdistributed-trieという名前でライブラリを実装してみた。

4

現在は鋭意パフォーマンス計測中。

4

 

4

分散トライ木

4

トライ木EXTは通常、C言語などのようなbit単位でデータを操作できる低レベル言語で実装されるのが一般的だ。

4

同一のマシンの同一プロセス空間にポインタなどを使って密結合なデータ構造を作るのがポピュラーなやりかた。

4

一方、今回私が作ったdistributed-trieはセオリーから外れており、Pure Rubyで書いてあるのと、複数のマシンから成る分散ハッシュテーブル(KVS)上にトライ木を構築するといったものだ。

4

 

4

分散のメリット

4

巨大な辞書を分散ストレージで一元管理し、パフォーマンスが足りなくなってきたらマシンをスケールアウトして対応することを狙っている。

4

Googleの「もしかして?」機能のようなスペルミス訂正などに使えると思う。

4

AWS EC2を使えば、リクエストが少ない時間帯は稼動マシン数を減らすなどしてコストを抑えることも可能だ。

4

 

4

distributed-trieの特徴

2
 構成図
3
 urEv
4

 

2

Trie木の例

2
 400px-Trie_example.svg
2

"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木

2

 

2

 

4

役割範囲はキー群の管理に限定

4

 

4

以下のキー部分の操作ライブラリが担当する。

4

 

4
        [key]      [value]
4
   1   node:$     "i$ t A$"
4
   2   node:i     "n$"
4
   3   node:in    "n$"
4
   4   node:t     "e o$"
4
   5   node:te    "a$ d$ n$"
4

 

4

つまり、トライ木のキーに対応するデータは、ライブラリの責任範囲外。アプリケーションは自分でデータを格納する。

4

データの内容はアプリケーションの都合で自由に決めれる。

4

 

4
   1   DATA:to    データ7
4
   2   DATA:i     データ11
4
   3   DATA:in    データ5
4
   4   DATA:inn   データ9
4
   5   DATA:tea   データ3
4
   6   DATA:ted   データ4
4
   7   DATA:ten   データ12
4
   8   DATA:A     データ15
4

 

4

トランザクション機能はKVS機能の担当

4

例えば、Tokyo Cabinetは複数エントリの一貫性を保持するトランザクション機能を持つ。

4

これも、ライブラリの責任範囲外。

4

トライ木の構築とトライ木に対応したデータの格納をトランザクションで括れば一貫性のあるデータ管理ができる。

4

※ 分散KVSで一貫性を持つものはほとんど無いため、あまりトランザクションを使う場面は無いかもしれないが…

4

 

4

KVSはプラッガブル

4

ユーザーがKvsIfクラスと同じ挙動を示すクラスを用意すれば、何にでもトライ木を構築できる。

4

例えば、DynamoDB、HBase、Okuyamaなど、Rubyのバインディングが存在するKVSなら簡単にトライ木を構築できる。

4

現段階では distributed-trie は Tokyo Cabinet / memcached / gdbm / SimpleDB / DynamoDB / Redis / ruby's pure hash をサポートしている。

4

 

4

パフォーマンスの特性がわかってきたら、またブログ記事を書く予定。

4

 

0

comment (disabled)

4

4

 

4

 

5

kiyoka.2012_03_07[Sekka][KVS][TRIE] Sekkaにトライ木を実装するとしたら ver-1

5

 

5

先日の記事 「kiyoka.2012_02_25[Sekka][KVS][TRIE] Sekkaにトライ木の実装が必要な理由」の続き。

5

Sekkaの曖昧文字列マッチングはかなり手抜きな実装になっている。

5

そこをトライ木で改善できるのではないかという話。

5

※ 本記事はKey-Value Store型データベースにトライ木を構築する方法を書いています。ポピュラーなtrieライブラリであるDouble ArrayやLOUDSなどのデータ構造の話では無いので、それを期待されて来られた方はすみません… そのあたりの話は全部次の本に書いてあります。私は買いました。ステマではありませんよ。

5
 4774149934 日本語入力を支える技術。変わり続けるコンピュータと言葉の世界: 徳永 拓之
5

 

5

 

5

問題点

5

現状のSekkaではローマ字のキーワードが単純な文字列のリストで格納されているだけなので、ユーザが入力したローマ字との編集距離の比較が大量に発生する。

5

例えば、"Kanji" に対する編集距離(Jaro Winkler関数)の呼びだし回数は 113211回 (全文字列サイズデリミタのスペース文字を入れると1.6MByte)となる。

5

また "Ka"という2文字を入力した時と、"Kanji"という5文字を入力した時では同じ回数Jaro Winkler関数が実行される。

5

これはかなりひどい。

5

 

5

Key-Value Stroeの上に実装する理由

5

通常、トライ木のライブラリはCやJavaなどの言語を使って実装され、整数型の配列やポインタを駆使し(時にはビット演算まで使って)格納データサイズを圧縮することに主眼が起かれていることが多い。

5

しかしここでは、世間の常識に反してプレーンなKey-Value Stroe上に実装してみる。

5

理由は、C言語のtrieライブラリを使うとインストール作業の敷居が上がるのでやりたくないのと、分散ハッシュテーブルを使って曖昧文字列マッチングがスケールアウトする様を見てみたいというのがある。

5

実は、単純に趣味の問題も大きいが…

5

 

5

トライ木

5

トライ木EXTを使えば、計算しても意味が無い部分ツリーをばっさり枝刈りできると考えた。

5

文字列が短かければそれだけ計算量を減らすことができる。

5

 

5

トライ木の概念

5

プレフィックス木(Prefix Tree)とも言われるだけあって、検索したい文字列の先頭から1文字づつ比較しながら木を降りていける。

5

幅優先探索も、深さ優先探索もどちら簡単に実装できる。

5

概念図は下記のようなもので、各ノードから子に降りて行くエッジ部分に1文字のアルファベットが付いている。

5
 400px-Trie_example.svg
5

"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木

5

 

5

上の図はトライ木 - WikipediaEXTからコピーしてきたもので、これを使って考える。

5

 

5

Key-Value Storeでの実現方法

5

あるノードの子をたどれるようにするために以下のようなデータ構造を考えることが可能だ。

5

[key]はKey-Value Storeのキー、[value]はKey-Value Storeの値とする。

5

キーという用語が二つ出てくるので注意。

5

Key-Value Storeのキーを[key] 、トライ木のキーを「キー」と表記する。

5

なお、扱える文字クラスはアスキーの範囲しか考慮していない。また $ は特別な記号に使っているため $ も使えない。

5

 

5
        [key]      [value]
5
   1   node:$     "i$ t A$"
5
   2   node:i     "n$"
5
   3   node:in    "n$"
5
   4   DATA:i     11
5
   5   DATA:in    5
5
   6   DATA:inn   9
5
   7   node:t     "e o$"
5
   8   DATA:to    7
5
   9   node:te    "a$ d$ n$"
5
  10   DATA:tea   3
5
  11   DATA:ted   4
5
  12   DATA:ten   12
5
  13   DATA:A     15
5

 

5

順番に解説すると1行目の [key] "node:$" はスーパールートといってツリー全体の根になる。

5

value側の "i$ t A$" のうち "i$" は $が付いているのでトライのキーとして登録されていることを示す。

5

 

5

[key]の "node:" で始まっているものがトライ木のノード、"DATA:"で始まっているものがトライ木に上のキーに対応するデータである。

5

[value]の数字は実際のデータである。そのKey-Value Storeがサポートしたデータならなんでも良い。

5

13行目は A に対してのデータで数値の15を例として入れてある。(わかりやすいように上の図のノード番号を入れている)

5

 

5

prefix searchの手順

5

木全体から "in" で始まる単語を探索する場合

5
1行目の "node:$" の[value]を調べる
5
1文字目の i がキーワードとして終端している "i$" があるので、iをキーワードとして蓄積する。
5
iに続くキーワードがまだあるかも知れないので、KVSから"node:i"で引いてノードがあるか調べる。
5
2行目の "node:i" が見つかるので[value]を調べる。
5
2文字目の n がキーワードとして終端している "n$" があるので、inをキーワードとして蓄積する。
5
inに続くキーワードがまだあるかも知れないので、KVSから"node:in"で引いてノードがあるか調べる。
5
2行目の "node:in" が見つかるので[value]を調べる。
5
3文字目の n がキーワードとして終端している "n$" があるので、innをキーワードとして蓄積する。
5
innに続くキーワードがまだあるかも知れないので、KVSから"node:inn"で引いてノードがあるか調べる。
5
ノードが無いので、inn以下のトラバースはしない。
5
探索結果から、検索文字列 "in"よりも文字列長が短かい "i" を削除したリストをprefixの結果とする。
5

 

5

※ 途中、[value]に複数の子ノードが見つかったら、それぞれのエントリを再帰的にトラバースする。

5

 

5

編集距離による絞り込み探索

5

prefix searchと違う点は文字列が完全一致しているかどうかを調べるかわりに、探索クエリ文字列とトラバース中に見つかったキーワード同士の編集距離が閾値に収まるかで判定する。

5

閾値に収まらないキーワード配下のツリーは探索対象としない。

5

 

5

キーワードの動的な登録

5

注意する点は、一般的なKVSは複数[key]の一貫性のある登録をサポートしていないので、登録中に参照があった場合、おかしな木が見える可能性があること。

5

対策として登録順を工夫する。

5

最初にデータ、次にツリーの葉のほうから根に向かって順に登録していくことで参照時のファントムリードが無いようにできる。

5

※ 参考:Tokyo Cabinetは複数エントリの一貫性のある登録(トランザクション)をサポートしている。

5

 

5

キーワードの動的な削除

5

注意する点は、一般的なKVSは複数[key]の一貫性のある削除をサポートしていないので、削除中に参照があった場合、おかしな木が見える可能性があること。

5

対策として削除順を工夫する。

5

最初にツリーの根のほうから葉に向かって順に削除、最後にデータという風に削除していくことで参照時のファントムリードが無いようにできる。

5

※ 参考:Tokyo Cabinetは複数エントリの一貫性のある登録(トランザクション)をサポートしている。

5

 

5

というわけで、一度実装してみて問題があれば、訂正記事を書こうと思う。

5

 

0

comment (disabled)

5

5

 

5

 

5

kiyoka.2012_03_04[本] 読んだ本など

5

ちょっとミーハーなやつも混ざっているけど…

5

 

5

この3冊の本を偶然同時期に見つけて読んだんだけど、この3冊をあわせて読むといい感じでつながってくる。

5

いろんな欲しいサービスや製品が頭の中で生まれては消え、という感じで脳の中に新しいネットワークが形成された感じ。

5

それぞれの本を単品で読んでも、あるいは時期がずれたらきっとこういう感じにはならないと思うので、何をどう読むのかって大事なんだなぁと考えさせられる。

5

もしかしたら、インフルエンザで寝込んでは起きてしながら本を読んでいた今だからこそ起きた現象なのかもしえないけど。

5

 

5

483341936X  トレードオフ―上質をとるか、手軽をとるか: ケビン・メイニー(著)

5

4163733507  選択の科学: シーナ・アイエンガー

5

4798124710  イノベーションのDNA 破壊的イノベータの5つのスキル: クレイトン・クリステンセン他

5

 

5

(先進国に済んでいる身として)これから自分はどこに向かうべきかについていろいろ考えたりする。

5

というか今のままではイカンのかなと思うのであった。

5

 

5

※ ちなみに、アルゴリズムの本も読んだけど、熱は無くてもインフルエンザの時に読むとトライ木をトラバースしてぐるぐる視点移動しまくる悪夢を見てしまった。

5

※ 悪夢をみやすい体調の時はアルゴリズムの本は向いてないな。注意されたし。

5

 

0

comment (disabled)

5

5

 

5

 

5

kiyoka.2012_03_03[Sekka] Sekka 0.9.7 リリース

5

SKKライクな日本語入力メソッド Sekka 0.9.7をリリースしました。(リリースノート Sekka.ReleaseNote)

1
 iStock_000016378483XSmall
5

 

5

リリースの概要

5

主に、Debianパッケージ化の作業が中心です。

5

rubygems-testに対応し、"gem test sekka"でテストが走るようにし、gem2debでDebianパッケージ化するとそのままではsekka-serverが起動しない問題を解決しました。

5

 

5

以下リリースノートです。

5

version 0.9.7

5
jewelerの仕様変更に対応した
5
カレントディレクトリにGemfileがあると、生成されたgemspecの依存規則に採用されてしまう。
5
SekkaのGemfileはTrivis CI専用なので gemfiles/Gemfile に移動した。
5
rubygems-testに対応した
5
.gemfileをgemに含めた。
5
"rake" のデフォルトタスクではredisのテストを省いた。
5
辞書データフォーマット変換の出力を簡潔にした。(MD5の結果値のみにした)
5
STDOUT出力と、STDERR出力を混ぜるとrubygems-testがブロックする問題の回避
5

テストのコンソール出力は、STDOUTのみ使うようにした。

5
gem2debでDebianパッケージ化してもsekka-serverが正常に起動するようにした。
5
sekka.ruのパスを RbConfig::CONFIG['vendordir'] を使って解決するようにした。
5
 但し、RbConfig::CONFIG['vendordir'] 配下にsekka.ruが無い場合は、
5
 これまで通りsekka-server自身からの相対パスを使う。
5

 

5

 

5

次の目標

5

先日のエントリ(kiyoka.2012_02_25[Sekka][KVS][TRIE] Sekkaにトライ木の実装が必要な理由)で書いたように、辞書のデータ構造に手を入れて辞書検索の計算量を減らす実験をしてみようと思います。うまくいくかは実験結果次第です。

5

 

0

comment (disabled)

5