ひ日記

ときどきの雑記帖経由で、たまに見ている このブログ(ベンチャー社長で技術者で)

基本キャラづけというか、マーケティングも含めて「他人があまり言わないことを大声で言ってみよう」という方法論で、 偉そうに間違ったことを言うというアプローチの一種だと思う訳です。

なので、原則失笑しながらスルーしていたのですが、このエントリにはつい釣られてしまいました。 SQLで高速にあいまい検索してみよう - ベンチャー社長で技術者で

数千万件オーダーの規模の検索サービスに少し関わっているので、ちょっといろいろとひっかかってしまうのです。

分ち書きとN-Gramと

wikipediaでもこの分類になっていますが、 (形態素解析を利用した分ち書きによる)単語ベースのインデックスとN-Gram法によるインデックスなんじゃないのかなあ……。 形態素解析は単なる前処理に過ぎない訳ですし。

N-Gramという話をする場合、「Nをいくつにするのか」というのは結構重要な問題なはずですがそこはスルーですか？

50万件のレコードに2000エントリのインデックスだと、レコード1件あたり400エントリということになります。 1レコードあたりの情報量が200文字前後と仮定するとN=2でしょうか。

分かち書き（形態素解析）で精度が落ちるというのは、Googleはかなりマシになってきていますが、Yahoo、MSNで“ウォーターフォール”と“ ウォータフォール”を検索すると、前者の方が数多くヒットします。つまり、ウォータフォールは新語として判断して、“ウォータ”・“フォール” と分かち書きできてないと思われる。つまり、“ウォータフォール”では、“ウォーターフォール”としか記載されていないページはヒットしません。住所や名前などはどこで切れるか機械的には分かりにくく、同じような検索漏れが起きると、顧客を抽出する機能としては問題があるわけです。

これは、嘘というかミスリードですよね？

N-Gram(bigram)インデックスであっても、“ウォーターフォール”のクエリで“ウォータフォール”を検索することはできません。 これは、インデックス、クエリの正規化や、類語辞書の整備で対処する問題で、全文検索用のインデックスがN-Gramなのか、単語ベースなのかには起因しません。

というより、検索精度という問題であれば

• 適切にメンテナンスされた辞書を持つ単語ベースのインデックス
• N-Gramインデックス
• 辞書のいいかげんな単語ベースのインデックス

の順に精度が高いと言えるはずです。

一般に業務で利用される検索システムでN-Gram(bigram)インデックスが選択される場合が多いのは、辞書のメンテナンスコストが高い(高過ぎる)と見做されるからにほかなりません。

Rosette形態素解析システムとか結構なお値段ですが、必要だと思うプロジェクトでは使用されていますしね。

検索速度

サンプルデータは個人情報っぽいけど、SI Object Browser で作り出したランダムのデータです。Oracle Express Editionで、わたしのちょっと速めのノートPC（ショップブランドの安いヤツ）で、インデックスを作るのに約15分、1件の更新は数十msec、 50万件から1000件程度の条件でほぼ1秒以内で返してきていますので、ノートPCでなく、最近のそこそこのサーバなら十分使えるんじゃないかと思います。

「ほぼ1秒以内」ってのが、1桁msなのか、1000ms前後なのかで話しは違ってきますが、「1秒を越える場合もある」のであれば遅いのでは？

ざっくり、50万件 x 200文字(UTF-8で符号化された日本語だとして期待値600bytes)と仮定すると、たかだか300MB程度のデータですよね。 「ちょっと速めのノートPC」とやらに4GBクラスのメモリが搭載されていれば、インデックス込みでオンメモリで処理できる規模です。 APIレベルでの検索クエリへの応答速度であれば、2桁msぐらいが「高速」と名乗って良いラインでしょうか。

あと、ヒット数=全レコード数となるような、最悪ケースでの処理時間も知りたいですね。 (経験的に言って、ほぼ全件にヒットするような複数の条件のAND/OR演算とかはかなりしんどいです)

インターフェイス

ともかく、ユーザーの作業（電話で顧客を特定する）を考えたら、検索ボックスは1つあればよいわけです。（GoogleやYahooでどんな検索しているのか考えればわかるでしょう）

噴飯もの。

無論、入力が1項目で良い場合も多分にありますが、要件によって必要になる入力項目は異なります。 Googleで検索オプションを押したことも無いのでしょうか。

ヘルプデスクでの業務を想定しても、"検索ボックスは1つあればよい"はありえないです。 大阪さん(実在の名前です)は、人名としては珍しくほぼユーザを特定できる情報だと思われますが、住所と照合されると絞り込みに使える条件ではなくなります。 どうするんでしょう？

データ量

その2000万レコードから、数百データ分を引っ張ってくるのに1秒以内です。GoogleやYahooのようにスコアーが低いデータを無視できるなら、もっと早く返すことも可能です。

2000万レコードから1900万レコードがヒットするような検索の1800万レコード目から100件とか言う極端な要件があったりもするんですがね……。 それはともかく、ofで検索された時(極端に大きな結果集合が見込まれる時)にどうするかってのは、検索UIをデザインする際には常に話題になるんじゃないのかなあ。

ちなみに、twitterの公称ユーザ数については、こんな記事もあります。

ユーザ情報のレコード数が5000万だと、このシステムでのインデックスのエントリ数は20億になる計算だけど、ちゃんとスケールできるんでしょうか？

データベースの分割

電話帳を分割するのとなんら変わらない。

理屈が分かっていれば怖くないのです。

長々と書いてあるわりに内容が無いというより、技術者が書く文章ではないです。 システムをスケールさせる話のはずなのに、スケールに対する認識が欠如しているように感じます。

分散化された個々のシステム(サーバ(?))が、割り当てられたデータに対して適切な処理能力を持っていることは誰が保証してくれるのでしょうか？

さらに大きくなったときは、キーワードごとに保存するサーバを変えてやればよいでしょう。（“A”から始まるサーバ、“B”から始まるサーバ、"あ"から始まるサーバ……）

そんなに簡単な話ではありません。

手元に辞書や辞典があるなら、索引を見てみると良いと思いますよ。

• "あ"と"ん"の索引は同じ分量の単語を収録していますか？
• 辞書の各ページの使い込み具合は均等ですか？

日本語……

ときどきの雑記帖でもツッコまれているけど

検索エンジンは言語的に日本語が一番難しいから、日本語から作れれば英語や他の言語なんて楽勝です。

酷いですね。

結論

LIKE別に遅くないよ(アレ？

というか、元記事の方法は「高速に」というほど速い実装では無いよね。

ぐるんがのテスト環境なんとかしよう。