Comments
Description
Transcript
類似文字列検索エンジンApporo の応用
類似文字列 検索エンジン Apporo の応用 @overlast アジェンダ • プロトタイプ開発と Perl • Apporo とは • Apporo の使いどころ • 使用例（コマンドライン、Perl） • まとめ • 当日の資料を改変しました。大筋は同じ内容です。 @overlast の自己紹介 • さとう としのり 柔軟 • blog : http://diary.overlasting.net/ • 普段やっていること • 企業でスペルミスを訂正する手法を研究開発 • 例 : 入力 : aiphone => 出力 : iphone では？ • 近況 • 類似文字列検索エンジン Apporo の開発 • DSIRNLP 勉強会を主催 • データ構造・検索・自然言語処理・機械学習 • Mining the Social Web の監訳に参加 プロトタイプ開発 と Perl 要素技術の開発には試作が必須 • 要素技術 = 製品を構成する要素に関わる技術 – 妥当な性能を達成していることを要求される – 例 : 話しことばで検索できる質問応答掲示板 • 要素技術「形態素解析」「全文検索」は使えて当然 • 要素技術開発の最初のゴール = 性能の達成(not 仕様の達成) – 世の中には、仕様が無いがゴールだけ明確な場合がある案件がある – 例 : • 研究(この世に無い技術を生む or 関連研究以上の性能を出す) • デザイン(アピール力があり、クライアントが納得する形を生む) • 仕様が無い案件 = 調査、分析、試作を繰り返す必要がある – 仕様がないので、妥当な設計の発見を繰り返す • 駄目な設計は将来の悲劇を生むので、最初は方向性だけ決めよう • 汎用性は、複数の固有の事例の共通部分から見出そう • 必要な技術の開発期間や依存関係を考慮して計画をたてよう 要素技術を4Stepで開発する例 • 0. 解決したい問題(テーマ)を決める • 1. 発見 – 問題解決に使える技術・理論を探して、発見する – 価値ある発見の後、試作して少量の問題を解く • 2. デモ – ブラウザからいじれる最小限のデモを作る • 適用先のデータを使い、試作者以外とも議論 • 使い方と使われ方のギャップを埋めて大きな失敗を防ぐ • 3. 判断 – 完成した時期に実用した際の有益度を判断する • 実用的か？ 応用しやすいか？ 伸びしろはあるか？ • 4. 開発 or 封印 – 有益度高 : 本気の開発を始める – 有益度低 : 捨てる、作り直る、テーマを変える Perl でプロトタイプを作る利点 • まったく、Perl は最高だぜ！と僕が感じるポイント – 柔軟な文法 • 作るべきモノがハッキリしない時期に最適 • 技術を考慮しないリクエストに素早く対処できる – 高い移植性 • 計算機クラスタごとにOSが違っても書き換えなくてOK – 環境に依存するモジュールは使いにくいけど – 再利用性 • コードを書いた時期より後にリリースされた Perl 5 で動く – 他の言語を見てるとバージョンアップしても動くってすごい – 数年前に試作したコードをそのまま利用出来る – 人 • 豊富な CPAN モジュールと格好良いコミュニティ – 友人や知人の作った実装を使えるのは、気持ち良い Perl だけで要素技術を開発しきれる？ • No !!! それは無理だ !!! • Perl だけではやりにくいことの例 – a. 複雑で高速な大規模データ処理をしたい • Perl はメモリの消費量多く、変数のデータ構造が冗長 • データを複雑 or 高速に処理するならC/C++から逃げられない – b. Perl で書かれていない有益な実装を使いたい • 例 : Hadoop, Luceneは Java 以外からはヘビーに使いにくい – c. 新しい計算機クラスタが必要になった • 自分で構築した方がコストが低い場合も多い • 他人に任せるなら、設定ミスを発見できる能力が必要 – d. この世になかった技術を形にしたい • 例えばたまたま、まだOSSになっていない技術が必要になった – Perl だけに詳しくても新しいものは作れない – コンピューターサイエンスを必要に応じて学ぶべき Perl から C/C++ への置き換え例 • 自然言語処理・検索などで使う技術 – 複雑で高速な大規模データ処理が必要 => いつかはC/C++化 • 要素技術開発の利益最大化 – 試作から最速で実用化 => 高精度化・高速化 => 整理整とん • とあるアプリケーションを全部 C++ で書き換えるまでのStep例 – Perl スクリプト 1 ファイルのデモを作成 – 設計を大雑把に考えて Perl モジュール化 – 実際のデータを使って不具合を発見し、修正する – パフォーマンス測定をする – ボトルネックな部分をC/C++化しつつ、Perl で新機能を足す • このあたりで実用化できることが多い – 徐々に C/C++ 率を上げつつ、XSを書く & まだ Perl からも呼ぶ – すべての Perl コードを C/C++ に置き換え + XS からのみ呼ぶ プロトタイプ開発と Perl のまとめ • 要素技術を開発するときは、いきなり全部作らない – 駄目設計の汎用ライブラリは悲劇を生む – 必要性を予測して、事前に調査・試作・検討 – 最初は汎用性を高めすぎないことも大切 • 試作は Perl でやっておくと良いかも – 経験上、一度書いたコードを長年使いまわせた – デモへの突然の注文を反映するコストが低かった • なんでも Perl で(単一言語で)やるのは最適でない – 開発速度とメンテナンス頻度のバランスをとろう – 複雑な処理は、後でC/C++で書きなおして高速化 Apporoとは Apporo の概要 • 開発の経緯 – 求める機能をもつ手軽なライブラリがない • 目標 – お手軽で高速な類似文字列検索を実現したい • どんな感じか – 準備 : 辞書を用意し、事前に indexing する – 入力 : 任意の文字列 – 出力 : 入力と文字列距離の近い辞書エントリ – Perl から利用できる(Perl で試作してたので) Apporo の技術的な情報 • 開発言語 C++（Perl 拡張を用意） • indexのデータ構造 – Suffix Array / [今後]転置index • SA の場合は任意の文字N-gramで検索できる • 検索に使えるクエリの情報 – クエリの(表層|[開発中]読み|[今後]ローマ字) • 候補をランキングするスコア – Bit Parallel Matching法による編集距離計算 Apporo の競合との比較 Apache Lucene SimString 検索indexの データ構造 転置index 転置index 検索速度 チューニング次第 爆速 Apporo Suffix Array (今後、転置index も) 実用的な速度 (今後さらに速く) indexファイルの量 Segmentの設定次 辞書エントリの最 第 大バイト長 * N 2 取得した候補の あり リランキング機能 なし あり 検索に使える クエリの情報 頑張り次第 表層 表層 / (開発中)読 み/(今後)ローマ字 開発言語 Java C++(Python, Ruby) C++(Perl, Python) 実装を選択する 妥当な理由 Luceneを使用(して 取得候補のリラン いる|する予定) キングが不要 それ以外なら Apporo を試して！ ソースコード(New BSDライセンス) http://code.google.com/p/apporo/ Apporo の 使いどころ Apporo の使いどころ(1/2) • 例1 : 検索結果ゼロ件の検索クエリに対処できる • 「人間なら分かるクエリ」は修正すべき 検索クエリの訂正は必須 • 今や訂正は、やって当たり前 • 特にモバイル向けでは必須 • 移動中の正確な入力は大変 ユーザー : （ですよね。） ユーザー : 「見つかりません」？？ 何を言ってるの(怒) • 顧客の入力に未対処 = それってバグと言えるのでは？ • 検索結果ゼロ件のクエリを集計して観察しよう • 観察に基づき類似文字列検索を適用し顧客のストレスを減らそう Apporo によるクエリ訂正 • 例1 : 誤りを含むクエリに近い正しいクエリを探す • Step1. 最初にクエリログを2種類に分けて集計する • a. 正しいクエリ : 検索結果を得られた • b. 誤りを含むクエリ : 検索結果を得られなかった • Step2. 検索結果を得られたクエリのリストをindexing • Step3. 試してみて、パラメタを調整する • 誤りを含むクエリのリストで性能をテスト • 例2 :誤りを含むクエリに近いタイトルを探す • Step1. 検索対象の文書からタイトルを抽出しリスト化 • Step2. Step1で得たリストをindexing • Step3. 試してみて、パラメタを調整する • 別途集計した誤りを含むクエリのリストでテスト Apporo の使いどころ(2/2) • 例2 : 辞書メンテナンスコストの軽減できる • 異表記を列挙せず類似文字列検索をする • 異表記を列挙するコストを新語登録に回せる • 事例 • a. 薬事法違反のテキストを探す • 辞書中に「たった1回でツルツル」があれば • 「たった1回でトゥルトゥル」も見つかる • b. 援助交際関連の発言を探す • 辞書中に「苺」があれば • 「いちご」「イチゴ」「一護」も見つかる • c. ビル名やランドマーク名を探す • 辞書中に「六本木ヒルズ森タワー」があれば • 「ヒルーズ」「六本木ひるず」も見つかる Apporo に関するまとめ • 「類似文字列検索」という要素技術がある – 「近似文字列照合」などでググってみよう – この技術で検索ヒット数ゼロ件を回避しよう • 類似文字列検索エンジン Apporo がある – 以下の条件を満たすなら利用を検討して損はない • Lucene(Solr)を使う必要がない or 使っているが苦手 • 検索クエリとの編集距離が近い順で結果を得たい • Apporo は今後「読み仮名やローマ字での検索」や「強力 な文字列正規化」を実装し、安定させ、高速化する Apporo の 使用方法の例 デモ(インストール) • tsubomi (Suffix Array ライブラリ)のインストール svn checkout http://tsubomi.googlecode.com/svn/trunk/ tsubomi cd tsubomi make; sudo make install • Apporo のインストール svn checkout http://apporo.googlecode.com/svn/trunk/ apporo cd apporo/src make; sudo make install • Apporo の Perl 拡張のインストール cd apporo/perl/Apporo perl Makefile.pl make; sudo make install デモ(index作成用のコマンド) • apporo_indexer コマンド – 以下を実行すれば検索用の索引ができる – UTF-8 文字列を含むファイルのindexing • apporo_indexer -i ./address.tsv -bt –u • apporo_indexer -i ./address.tsv –d – ASCII 文字列だけ含むファイルのindexing • apporo_indexer -i ./address.tsv –bt • apporo_indexer -i ./address.tsv –d デモ(index するファイル : yapc.txt) デモ(設定ファイル : demo.conf) ngram_length 2 is_pre false is_suf false is_utf8 true dist_threshold 0.0 index_path /path/to/your/file/which/already/indexed/yapc.txt dist_func dice entry_buf_len 1024 複雑そうだけど、 engine tsubomi 検索を効率よく行うには、 result_num 5 bucket_size 2000 一定量のパラメタが必要。 is_surface true is_kana false is_roman false 設定ファイルがあると、 is_mecab false APIを綺麗に作りやすい。 is_juman false is_kytea false アプリごとに書くと良い。 デモ(検索用の2種類のコマンド) • apporo コマンド – 設定ファイルのパスとクエリを引数で与える • apporo ./demo.conf “クエリ” • apporo_searcher コマンド – すべてのパラメタを必要に応じて指定する – UTF-8文字列のindexを検索するときは –u が必要 • apporo_searcher -i ./address.tsv –u ¥ -q クエリ –n 2 –d dice –t 0.6 –r 10 – ASCIIの時は-uを付けない。それ以外はUTF8と同じ • apporo_searcher -i ./address.tsv ¥ -q クエリ –n 2 –d dice –t 0.6 –r 10 デモ(yapc.txt を検索) • 文字index作成、行index作成、indexの確認、検索を実行 – indexしたのはYAPC::Asia TOKYO 2011 の発表タイトルリスト – 検索クエリは「Apporo」を「Aporo」と間違えている – 狙いどおり、Apporoでクエリに類似するエントリを発見できた デモ(Perl でApporoを使う : demo.pl) #!/usr/bin/env perl use use use use strict; warnings; utf8; YAML; use Apporo; my $config_path = $ARGV[0]; my $query = $ARGV[1]; my $app = Apporo->new($config_path); my @arr = $app->retrieve($query); print Dump \@arr; デモ(Perl から yapc.txt を検索) • 先程の設定ファイルをapporoコマンドと同様に利用 • demo.plの中では use Apporo; してる程度 • apporo_searcherのコマンドと同様の結果を得た • 結果は今のところ文字列の配列で返していますけど、 今後、安定性が増したらハッシュの配列にする予定です まとめ まとめ • 要素技術は、いきなり作らないで試作しよう – Perl は要素技術の試作に最適だと僕は思います – 試作したら他部署・職種の方からも意見をもらおう • 計画策定や機能の取捨選択は主担当者がやるしかない • 類似文字列を検索しない時代は終わった – だいぶ枯れた技術だから、実際に使ってみよう • 類似文字列検索が必要なときは Apporo を試してみよう – Apporo は Perl のおかげでスムーズに開発できました – 徐々に、便利に、安定させて、速くします • デモ失敗に関するApporo 由来の原因は解消しました ご清聴ありがとうございました @overlast でした。 http://code.google.com/p/apporo