SQLで高速にあいまい検索してみよう

スキル | データベーススキル

» 2009/08/05

　リクエストがあったので、OracleでN-Gram（今回は2-Gram バイグラム）で顧客を抽出するSQL＆ストアドプロシージャを作ってみました。

　全文検索ではありますが、Googleなどであればキーワードとキー（GoogleはURL）ごとにあらかじめスコアリングしています。それで、実際には上から×××件（スコアーの低いコンテンツは無視され漏れる）という仕組みになりますが、50万人ぐらいの顧客の中から、特定の顧客を特定するような処理であれば、スコアリングはできないし漏れることはマズイのでそれほど高速にはできません。たかだか50万件ではもともと速いから、パフォーマンス的にはあまり効果はないかも。

　また、N-Gramは、ゴミを拾い易い検索方式ですが、チューニングしだいで防ぐことも可能です。

　パフォーマンスチューニング、ヒット率のチューニング含めて、大体1人日で作れました。資料は作ってないけど作ったら2人日かな。一番面倒だったのが50万件ダミーを作ることだったりして……。

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

　ここにソースコードをアップして、すべて解説するのはとても無理なのでしませんが、ソースコードが欲しい方は info@g1sys.co.jp にメールをいただければ差し上げます。ソースに5万件ダミーデータがあるのでちょっとデカく4MByteあります。それを10倍に水増ししています。

　ソースを読んでもわからない人は、ぜひ、セミナーに出てください（笑）。

　Oracle Textを使ってもいいのですけど、なぜ、N-Gramなのか？というと……。

　分かち書き（形態素解析）は名称や住所など辞書に当たりにくいものの精度が落ちるし、この程度なら手組みしても1日あったらできるので、個人的にはオリジナルで作った方がよいと判断してしまうわけです。

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

　どのように使うかというと、たとえば、コールセンターで顧客を検索する画面を作るとすると、よくあるのが、

　　　　氏名
　　　　氏名カナ
　　　　住所
　　　　住所カナ
　　　　電話番号
　　　　携帯番号

と、検索ボックスがいくつもあって、それぞれに正しいデータを入れないといけない。しかも、あいまい検索にすると遅くなる。（数十万件ならそんなに遅くなかった……ハードの進化に嫉妬するわ）これらを防ぐために作ります。

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

　さらに、Oracle Textがどのレベルかしりませんが、自分で作れば

　　　　斎齋　→　斉
　　　　冨　→　富
　　　　之乃　→　の
　　　　ヶヵ箇　→　か

などなど、コールセンターで苦労しそうな（名前・住所で使われそうな）異体字も独自に調整できます。

　しかし、良いことばかりはなくN-Gramはインデックスデータが膨大になります。メールで差し上げますよ。といっている50万件のインデックスデータは、2000万件近くになっています。

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

　レコード件数が増えると怖いと思う人が大勢いるのは知っています。

　しかし、本当に怖い？

　例えば、1億2万人分の携帯電話番号が市町村ごとに分かれた電話帳があったとしましょう。

　「大阪市 生島勘富」の携帯電話番号を探せませんか？ 大阪市で同姓同名はほぼいないでしょうから、大阪市の電話帳にたどり着ければ人間がやってもたかが知れています。

　Googleの様に巨大になっても同じでしょう。

　巨大になったときは、キーワードごとに何件あるかあらかじめ数えておいて（くだんの2000万件のテーブルの件数を全件キーワードごとに数えましたが20秒ぐらいでした）Googleなども何種類かの抽出方法を作っているとは思う。

　同じように、キーワード毎に件数テーブルにを元に、今回抽出する件数を調べる。少ないキーワードと、件数の多いキーワードの組み合わせの場合、少ないキーワードを含むURLのデータを件数が多いキーワードで調べることになるでしょう。上の例なら、“勘富”はそんなにヒットしないので、“勘富”がヒットしたものだけ、"生島"がヒットするか調べて、さらに、“大阪市”がヒットするものを探すわけです。

　“大阪市　北区”のように、いずれも大量にヒットするなら、いくらかずつ（たとえば、3000件）抽出して、スコアーの高いもの同士をマッチング。表示する件数集まったところでやめて、それまでのヒット率と、キーワードの件数を掛け合わせて概算の件数とすればいい。たとえば2％のヒット率で10000件だったとしたら、“約200件中10件を表示”って出せばいいわけです。概算ですからね。（オプティマイザがコストベースでやっていることですね）

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

　先ほどのキーワードごとの件数を保存したテーブルの横に、保存されているサーバ名でも、アドレスでも、保存しておけばよいわけです。サーバを増やしてから必要なデータをコピーして、サーバアドレスを書き換えれば何台でも増やせます（その後、重複データを削除）。

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

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

 

◇　　◇　　◇　　◇

　いつものオチで、Twitterで1000万人ユーザーがいたとしても、ユーザー検索はおそらく数人日で作れる、サーバを分散しても1人月かな。つぶやきの検索をオーバーヘッドの大きなSQLで作ったらまずいけれど、ユーザーの検索は「とりあえずSQL」で、もっとまっとうなモノが作れたはずです。

　何度も書いているけれど、「とりあえずSQLで」というのは、とりあえずC言語で書いてみて、どうしても遅いならアセンブラでとか、とりあえずVBで作ってみて遅かったらC++で、というのと同じです。逆に、「とりあえず単純なSQLのみで」というのは、C言語に対して「とりあえずアセンブラで」と言っているのと同じで馬鹿げています。

　単純なSQLを選んで、開発コスト＋パフォーマンスとトレードオフされるものは、教育コスト（習得コスト）ですが、それは顧客ではなく開発会社側の都合です。

　絶対におかしい。

　それでも「とりあえず単純なSQLで」という人が多いのは、複雑なSQLが理解できない人たちが教育して、SQLのスキルのゴールが極めて中途半端なところに設定されるためだと思う。

　大阪の方なら安いコストで習得可能です！

　よろしければこちらまで。http://www.g1sys.co.jp/

◇　　◇　　◇　　◇

　検索つながりで……。

　傲慢なわたしは、Googleが作れないと思ったことはない。検索エンジンは言語的に日本語が一番難しいから、日本語から作れれば英語や他の言語なんて楽勝です。早稲田の千里眼は何で消えたのかな……。スタンフォード大学にできて、なんで早稲田にできないんだ！ って高卒の癖に言ってみる。

　それはともかく、わたしはあの時期に、「外部リンクを評価すればよい」ということに気づかなかったし、気づいたとしても信じてそれに賭ける能力も、開発費やランニングコスト数年分の資金を集める能力もなかった。

　そこが悔しい……。

　YouTubeで毎日1億円以上の赤字が出ても平気というぐらいに資金を持てば何でもできる。Googleがすごいのは、大変な資金を持っていることでも、技術力でもない。「あの時期に、『外部リンクを評価すればよい』ということに気づいたこと」だとわたしは思っている。

　Twitterは、わたしには絶対に思いつかないし、いまだに何がすごいのか分からんけど、「外部リンクを評価すればよい」というようなオポテュニティをいつも探しています。今の自分が見つけることがができたら、それなりの答えが出せると思ってるけど、Twitterが分からないようでは見つけられないのだろうな。

　わたしがオポテュニティを見つけて大成功できなくても、もう少し脳ミソの柔らかい若い人を支援できるぐらいには大きくなりたい。日本の若い人から、「Googleぐらいナンボのもんじゃい！」っていう人がたくさん出てきてほしいと思っています。

　ともかく、零細企業ですが心はベンチャーです。ボロボロの零細企業の社長がGoogleに悔しいといってるのはこっけい以外の何者でもないけど、悔しい……。

　SQLにこだわっているように見えるし、実際にこだわってはいるのですが、わたしの中では小さなことで「必要ならやるよ」ぐらいのものなのですけど、「こく屁の音まで『SQL』」ってな誤解をよくされるのでちょっと言い訳でした。