永続連想配列の一実装であるKyoto Cabinetを用いた辞書検索システム（仮称：kcdict）の機能について前回の記事で説明した。今回は辞書検索システムの内部の実装について紹介する。 データベースの構造 デフォルトでは検索語の前方一致検索を行うので、前方一致検索が高速に行えるデータ構造が求められる。辞書順の比較関数を使ったB+木はまさにその目的に叶うので、それを採用する。 辞書データには同じ検索語を持つ複数のエントリが存在するという、いわゆる重複キー状態が発生するが、KCのB+木は重複キーを許さない実装になっている。そのため、検索語の末尾に識別用の文字列を連結して、各々のエントリのユニーク性を確保する。同一検索語のエントリ同士の順序をユーザが操作できるようにするためにもこの識別用文字列は利用される。各々のエントリにはユーザが任意の数値を付与することができるようになっており、同一検索語の
英和辞書や和英辞書などの辞書データは、検索文字列をキーとして使って、その値である説明文を取得するための連想配列である。Kyoto Cabinetを使うと非常に簡単に辞書検索システムを実装できることを2回に渡って示したい。これを読めば、英辞郎やWordNetのデータを使って自分の好みの辞書検索システムを簡単に作れるようになるはずだ。第1回目は、辞書検索システムの仕様策定と実際の機能について説明する。 デモ WordNetを使った英英辞書の検索システムを設置したので、まずは使ってみて欲しい。前方一致検索や完全一致検索はもちろん、曖昧検索や正規表現検索もできるスグレモノである。そして、早い。このサーバは、さくらVPSの一番安いプランで動作させているのだが、それでも大抵の動作がほぼ一瞬で完了するのがおわかりいただけるだろう。 http://fallabs.com/kyotocabinet/dict
いわゆるkey-value storeを使っている際に、レコードの挿入もしくは更新を検知して即座に何らかの処理を行いたくなることはないだろうか。俺はあんまりないけど、結構そういう質問が来るので、きっと巷にはそういう要求があるのだろう。Kyoto Cabinetでそれを実現してみた。 ジョブキュー もうちょい具体的な例を挙げると、ジョブキューである。ここで、「foo」という名前のタスクを考えてみる。読み出し側（ワーカ）は、適当な名前をつけた条件変数を常に監視していて、そこにシグナルが飛んできたら即座にレコードを取得して処理を行いたい。しかし、「一定の間隔毎にレコードの検索を繰返して発見したら処理を行う」というポーリングスタイルにはしたくない。操作にどうしてもタイムラグが出るし、ポーリングのための無駄なトラフィックが発生するからだ。 シグナル待機処理と該当レコードの取得処理を行う擬似コードは以
Ruby と MessagePack-RPC があれば、簡単なkey-valueストレージは簡単に作れます。54行で書けます（レプリケーションと負荷分散機能付き。サーバー38行、クライアント16行）。 簡単なKVSをベースにして、ログ集計や遠隔デプロイ、遠隔管理機能などの機能を追加していけば、ちょっと便利なサーバープログラムをサクサク自作できるハズ。 この分散KVSは、（keyのハッシュ値 % サーバーの台数）番目のサーバーにkeyを保存します。また、サーバーの名前順でソートしたときの「次のサーバー」と「次の次のサーバー」にデータをレプリケーションします。 すべてのサーバーで同じ設定ファイルを使います。サーバーごとの設定は引数を自分のホスト名に書き換えるだけなので、デプロイが容易です。 MessagePack-RPC for Ruby を使うと、分散しないkey-valueストレージ*1は
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
