N-gram

2013年に読んだ本が188冊でした。ハードカバー以外の本は全て裁断してスキャナでPDF化する所謂、自炊をしています。
来年の目標のひとつはOCR化して全文検索エンジンでこれらをIndexingしてキーワードで全文検索できるようにすること。

D社が開発している世界最速の非破壊ブックスキャナだけど、高速カメラによる判定と歪んだ画像の補正はできる気がするけど一枚一枚を高速でメクる制御とその精度がとても大変そう。

ちなみにiOS7のメモ帳は全文検索できて便利! UIは前の方が好きだけど。

Apache Solrとは何か

説明不要かもしれないですがApacheSolrは全文検索エンジンです。
2006年にCNETからApacheに寄贈しOSSとして公開されています。GoogleのようなWEB検索以外の検索ニーズ(企業サイト内検索など)で使われています。SolrはJavaで書かれており、WebAPIとJaveAPIで操作できます。
検索はSolrをデプロイしたサーバに対して、HTTPリクエストを行うだけです。

他の全文検索エンジンとしては、ElasticsearchやGroongaがあります。

検索の基礎

全文検索方式

UNIXコマンドのgrepやsqlのlike検索のようにファイルから検索対象となる文字列を探し出す方式です。
わかりやすい方式ですが検索対象の増加に伴って検索速度が低下します。

転置索引方式(inverted index)

ドキュメントに対して、ドキュメントIDを与えドキュメントを単語に分割します。

doc_A : 私は猫を飼う
doc_B : 彼は犬を飼う

このドキュメントを単語を抽出して出現回数をまとめると以下になります。


{
    "doc_A": [
        {
            "私": 1,
            "は": 1,
            "猫": 1,
            "を": 1,
            "飼う": 1
        }
    ],
    "doc_B": [
        {
            "彼": 1,
            "は": 1,
            "犬": 1,
            "を": 1,
            "飼う": 1
        }
    ]
}

次に単語をKeyにドキュメントIDのリストがvalueになるように辞書を作ります。つまり、どの単語がどのドキュメントに含まれるかに置き換えます。（転置）


{
    "私": [
        {
            "doc_A": 1,
            "doc_B": 0
        }
    ],
    "彼": [
        {
            "doc_A": 0,
            "doc_B": 1
        }
    ],
    "飼う": [
        {
            "doc_A": 1,
            "doc_B": 1
        }
    ],
    ...
}

特徴としてAND検索に強く高速ですがindexを作る時間がかかってしまいます。

ドキュメントIDとドキュメントの位置情報はポスティングリスト(posting list)で管理します。

検索クエリから探す時は、クエリをtokenに分割して作成した辞書からtokenを検索します。
tokenに対応するposting listを取得し、それから該当するドキュメントを探します。
上記例の場合、”私”を検索クエリだとするとdoc_Aというドキュメントが検索結果になります。

全てのtokenを含むドキュメントIDを探索して,見つかった場合に関連度をスコア化します。

上の２つの方式の関係はfindとlocateの関係に近いですね。

検索結果の評価指標

・適合率(precision)は検索結果の文書のうち、検索クエリに適合している文書の割合です。
・再現率(recall)は検索クエリに適合している文書のうち、検索結果に含まれる当該文書の割合です。

総合的な指標であるF1スコアは以下で計算されます。

$\begin{eqnarray*} F = 2\cdot\frac{precision\cdot recall}{precision+recall} \end{eqnarray*}$

単語分割

indexを作る過程で,日本語の文章から単語(token)を抽出することが必要です。
手法として辞書ベースの形態素解析、機械方式のN-gramがあります。

データの収集/整形

検索する前に索引(index)を作りますが,まずはデータの収集について。
データは文書だけに絞ってもHTMLやJSON,PDF等あらゆるフォーマットで来る事が想定されます。
そのデータに対して文書部分を抽出して正規化する事は、検索漏れを防ぐためにも重要です。正規化の重要性はクエリについても同様です。

形態素解析

言語で意味を持つ最小単位の単語である形態素に分割します。
一般的に隠れマルコフモデルや条件付き確率などの機械学習の手法を用います。
特徴として正解に固い言葉を用いる話言葉に対して精度が落ちます。
例えば、新聞やWikipediaを学習に用いるとTwitterに対する解析が上手くいかなくなります。
また、辞書ベースのため高速ですが検索漏れが起きる可能性があります。(再現率が低い)
ただし、N-gramの欠点である東京都で検索を行ったときに京都が見つかってしまう事はありません。

単語を機械的に部分文字列に分割します。1文字の場合uni-gram、2文字の場合bi-gramと言います。
N-gram索引は単語単位でうまく区切れない場合に有効で例えばゲノム解析などで利用されています。
あらゆる部分文字列を検索できること保証をしますが計算コストは高くなります。
またtoken数が増えやすく、東京都で検索を行ったときに京都が見つかってしまう事があります。(適合率が低い)

関連技術として字句解析のFlex、構文解析のBisonが有名で主要ブラウザのパーサでも使われています。

クエリとレスポンス

SolrのQueryParserはLuceneとdismaxがあります。dismaxは制限がありますがLuceneより複雑なクエリを簡単に記述できます。
HTTPリクエストを受けたSearchHandlerがSearchComponetという処理単位で検索を行っていきます。
Searcherがインデックスを調べ、結果をリストをResponseWriterに返します。

SearchHandler

検索や更新などの処理を行うためのsolrconfig.xmlに書かれています。

ResponseWriter

ResponseWriterはTypeが選択できXMLやJSON,CSVが使えます。
またPython,Ruby,PHP各種スクリプト言語のシリアライズされた形式で受け取ることもできます。

facet機能

facetは英語で物事の一面という意味があります。検索対象には様々な属性情報があります。
例えば本を検索するときに、iOSという検索結果からObjective-cでさらに絞り込みたいときにfacet機能ではObjective-c(8)と表示されます。
これはiOSでObjective-cに関する本が8件あるという意味を持ちます。

Solrを動かしてみる

公式はlucene.apache.orgです。


$ cd /usr/local/src
$ apt-get install openjdk-6-jdk
$ wget  https://ftp.kddilabs.jp/infosystems/apache/lucene/solr/4.6.0/solr-4.6.0.tgz
$ tar xzf solr-4.6.0.tgz
$ cd solr-4.6.0/example
$ java -jar start.jar

デフォルトで8983Portなので、以下にアクセスします。


https://localhost:8983/solr/#/

オンライン学習にも共通していると思いますが、常に最新にindexを保ち検索可能な状態とする動的なインデックス構築 (Online index construction)において検索処理結果の低下をある程度は許容する必要があります。

タグ: N-gram

【N-gram】全文検索エンジン Apache Solrを使ってみた