類似文字列検索してますか？ - Overlasting::Life

類似文字列検索
してますか
@overlast
自己紹介
• 名前 : 佐藤敏紀(@overlast)
• blog : Overlasting::Life (http://diary.overlasting.net/)
• 仕事 : 宝の地図探し
– クエリ訂正システムの開発に従事
• 関心 : 検索・関係抽出・データ圧縮・機械学習
参考文献
• Flexible Pattern Matching
in Strings
• バイオインフォマティクスの
ためのアルゴリズム入門
• 高速な類似文字列検索アルゴ
リズム,岡崎直観, 辻井潤一
アジェンダ
• 曖昧な情報を処理する能力
• ゼロ件ヒット問題
• 曖昧な文字列で正しい文字列を探す方法
• Apporo の紹介と動作デモ
曖昧な情報を処理する能力
• 人間の曖昧な情報の処理能力は高い
– 曖昧な質問に対する答えを見つけられる
• ものまね芸、や、各種の画像検索
– 結果がユーザの記憶や欲求と関連すれば正解
• 曖昧情報の処理は文字列処理にこそ必要
– 結果の理由を明確に説明できれば正解
– 結果の理由説明が困難でも便利なら正解
ゼロ件ヒット問題
• 検索結果がゼロ件になってしまう問題
– ゼロヒット、ゼロマッチなど様々な呼び方
• ゼロマッチ後に、ワンクリックorゼロクリックで
目的のページに辿りつくのが便利なサイト
• 大手サイトは対応してる場合がある
• 中小サイトだとなかなか対応する余力がない現実
• 「ゼロ件ヒットは機会損失」だ、と覚えましょう
「正しい文字列」は少なくとも2種類 • 正しさ1. 表記誤りが無い
• 表記誤りあり 「スータバックスコーヒー」
• 表記誤り無し 「スターバックスコーヒー」
• 正しさ2. 心の底で求めている
• 何とか思いついた文字列 「トトロの森美術館」
• 心の底で探してる文字列 「三鷹の森ジブリ美術館」
– 異表記同義語、同表記異義語、異言語表記等もある
正しい文字列を探す手法
クエリ表記誤りなし クエリ表記誤りあり
⃝ 探したい対象が明確 普通の検索
△ : 表記がヒント 表記の似た 文字列を検索
△ :表記以外がヒント × 探したい対象が曖昧 同じ対象に到達で 対処できない。 きる文字列を探す 人気順結果を表示
• パターン1. 表記をヒントにできる場合
→ 事前に用意した資源から文字列距離の近い文字列を探す
• パターン2. 表記をヒントにできない場合
→ 文字列と文書の共起からグラフを作り、そこから探す
曖昧な文字列で正しい文字列を探す方法
• 「正しさ」はユーザの心のなかによって変わる
– 表記誤りの無い文字列 or 心の底で求めている文字列
• 低コストで対応できる 2 種類の曖昧な文字列
– 表記があいまい + 探したい対象が明確
• 事前に用意した辞書から、正しい表記を探す
– 表記に誤りがない + 探したい対象が曖昧
• 与えられた正しい表記から、関連する別の語を探す
• 後者に高性能で対応するには大規模ログが必要
Approximate String Matching Engine
近似文字列照合エンジン
Apporo
http://code.google.com/p/
apporo/
Apporoの用途の例
• 検索結果がゼロになることを防止するために使う
– クエリ訂正の簡易版を実現できる
• メリット
– 検索結果ゼロ件による機会損失が減る
– 検索結果ゼロ件を防ぐための辞書を
メンテナンスするためのコストを減らす
• 表記ゆれ(既知な単語とほぼ同じ表記 & 既知な単語と完
全に同義)対応、略語対応、ノイズ文字の事前削除など
• デメリット
– (きちんと調整すれば) とくにない
Apporoの使い方
• 事前準備
– 結果を得られる単語で辞書をつくる
• 例) 結果がゼロ件に(ならない|なる)クエリを収集する
– ゼロ件にならないクエリで辞書をつくる
– ゼロ件になるクエリは詳細に分析する
– 辞書をApporoでindexingする
• ユーザによる検索時 : 結果がゼロの時だけApporoを起動
– 誤りクエリに表記が近い辞書中の単語をApporoで探す
– Apporoから得た結果を使い、ユーザのストレスを減らす
使用例) - 第一位の結果で勝手に検索する
- 結果リストの上位を表示する
Apporo 割と良いですよ
• Apporoは小∼中規模のWebサービスで
検索クエリの訂正をする用途にオススメ
– Apporo 以外にも優秀なライブラリがある
• SimString : http://www.chokkan.org/software/simstring/
• 現在は文字列の表層に基づき検索している
– 今後は「読み仮名」や「ローマ字表記」に
基づく類似文字列検索を実現する
• 高速化のための改良も頻繁にしている
Apporoの
技術概要
Apporoの概要
• 用途
– 事前に用意した辞書のエントリを、
誤りを含むクエリに見た目が似ている順で取得する
• 今後、読みが似ている順で取得できるようになる
• 目立った技術 : 独自の新技術は特に無し
– Suffix Array
– N-gram Search ベースの近似文字列照合
– Bit Parallel Matching による編集距離計算
• 使用しているプログラミング言語 : C++
• 他言語対応 : Perl (今後 Python, Ruby, Java)
ngram化
スータバ
あ、スタバ
Ngram
Query
Suffix Array
文字列距離で 昇順ソート
String
Distance
SA上での位置を取得 位置頻度で昇順ソート
Doc
ID
SAからIDのKeyを取得
DocID を取得 頻度を集計
Apporoのソースコード
コード名
概要
apporo.cc
一番外側のインターフェイス
apporo_config.cc
configファイルの読み込み
apporo_search.cc
検索機能のコア部分
apporo_query.cc
ngramクエリの生成
apporo_strdistance.cc
文字列間距離の計算
apporo_tsubomi_db.cc Suffix Array のtsubomiをラップ
apporo_utf8.cc
UTF-8文字に関する処理
apporo_util.cc
どこにも属さない便利関数群
apporo_searcher.cc
apporo_searcherの本体
apporo_index.cc
apporo_indexerの本体
apporo.cc
approximate_match()とサンプル設定ファイルで流れは分かる
conf/sample.conf
apporo_query.cc & apporo_strdistance.cc
コンストラクタ周辺が理解に役立つ
apporo_search.cc
検索まわりは毎日更新しまくり
apporo_tsubomi_db.cc
簡潔構造でrankが速い実装と置き換えたい
apporo_strdistance.cc
64bit以下はビット並列マッチで距離を得る
簡単な実験
• データ : 英語のWikipediaのタイトル
– 8,636,112 エントリ, 199.6Mbyte
• クエリ : micael_jackson
• 環境 : 2.4GHz Intel Core Duo2, Memory 4GB, HDD 500GByte
検索パラメタ
検索時間
2gram is_pref is_suf
8.04sec
2gram is_pref is_suf dice(0.7)
2.85sec
3gram is_pref is_suf
2.04sec
3gram is_pref is_suf dice(0.7)
0.36sec
4gram is_pref is_suf
1.37sec
4gram is_pref is_suf dice(0.7)
0.18sec
5gram is_pref is_suf
0.05sec
Apporoの今後のToDO
• • • • • マニュアル、ドキュメントの整備
テストコードの整備
索引とクエリの各種正規化
読み仮名検索、ローマ字検索
高速化
– 探索の枝刈りの精度を向上
– Vertical Code
– Suffix Array から Trie への置き換え
– pthread
• • • • 形態素単位index
各種言語バインディング
自前のDBを利用する
現実社会で導入してもらう
Apporoの開発モチベーション
• 日常の無駄な時間を減らしたい
• 時間を得するライブラリをつくる
• 現実社会に広く導入してもらう
• 便利なアプリケーションが増える
• まわりまわって、いつか自分が得をする
まとめ
• 人間は曖昧な情報を処理する能力が高い
• ゼロ件ヒット問題は放置すると機会を損失
• 誤りクエリの訂正は検索ログなしでもできる
• Apporo は誤りクエリの訂正に気軽に使える
ご清聴どうもありがとう
ございました。