ブラウザで自然言語処理 - JavaScriptの形態素解析器kuromoji.jsを作った

概要

簡単に使える Pure JavaScript の形態素解析器 kuromoji.js を書きました。今回は、簡単に kuromoji.js を紹介したあと、セットアップ方法を解説します。ついでにロードマップ的なものも晒してみます。みんなでブラウザ NLP しよう！

kuromoji.js とは

言わずと知れた Java の形態素解析器 Kuromoji を JavaScript に移植したものです。
kuromoji.js の GitHub リポジトリ

と言っても、機械的に Java から JavaScript に置き換えたものではないため、API も違いますし、メソッド名やその内部も大幅に異なります。そもそも自分が形態素解析について勉強するために書き始めたため機械的なトランスレートに興味がなかったこと、また言語ごとに使いやすい API は異なると考えていることが理由です。

Node.js ではもちろん、ブラウザでも動作します。ブラウザで形態素解析することのメリットについては、あんちべさんのブログが参考になります。
RakutenMAによる形態素解析入門 - あんちべ！

ただ、内部で TypedArray を使用しているため、IE8/9では、そのままでは動作しないと思います。TypedArray の polyfill を使えば動くかもしれません。

npm や bower といったパッケージマネージャを使って、リポジトリからサーバや開発環境に簡単にインストールすることができます。

ライセンスは Apache-2.0 です。現在の kuromoji.js は、MeCab に付属している IPADIC という辞書を使っています。

Kuromoji の開発元は Atilika という会社です（現在はソースコードは Apache Software Foundation に寄贈されています）。ちなみに、kuromoji.js は Kuromoji の公式な JavaScript ポーティングとなったので、そのうち Atilika のページからリンクが張られるはずです。

形態素解析ってなに？

「百聞は一見に如かず」ということで、以下の kuromoji.js のデモサイトにアクセスしてみてください。17MB くらいある辞書がダウンロードされるので、太い回線で試してください。
kuromoji.js のデモサイト

「すもももももももものうち」という文が、形態素解析された結果が表示されたでしょうか？

形態素解析とは要するに、上記の「辞書」に基づいて、単語的なもの（形態素）に分解し、品詞や読み、基本形などを付与する処理のことです。

身近な例でいうと、Google などの検索エンジンをはじめ、Siri などの音声認識や、IME（かな漢字変換）でも同様の技術が使われています。他にも、テキストマイニングや、ニュース記事のレコメンド（SmartNews が有名ですね！）などへの応用もあります。形態素解析は、日本語を日本語としてコンピュータで扱うときに必須とも言える、非常に重要な基礎技術です。

　なお、「形態素」という言葉の定義は、立場によって異なるので、注意が必要です。品詞体系によっても異なるので、同じ形態素解析器でも辞書（IPADIC とか Unidic とか）を変えると挙動が違ってきます。

使い方

上記のデモサイトと同じデモサーバを、各自のローカルマシンで起動する手順を説明します。

これにより、kuromoji.js を使った Web アプリの開発環境をさくっとセットアップすることができます。

ブラウザで使うために kuromoji.js のパッケージを落としてくるには bower install kuromoji （node.js で使う場合は npm install kuromoji）を実行するだけなのですが、ローカルで Web サーバを立てたりするのが意外と面倒くさいです。

そこで、gulp と gulp-webserver という便利ツールを使います。これらを組み合わせることで、複雑な手順なしで Web サーバを構築することができます。

あとは、demo/ の下の HTML や JS などを自由に書き換えることで、kuromoji.js を使った Web アプリケーションのフロントエンドを自由に開発できます（デモページではフレームワークとして Vue.js を採用していますが、お好きなものをお使いください）。また、デフォルトでページの自動更新 (livereload) が有効になるように設定されていますので、HTML や JS ファイルを修正する際のデバッグがとても楽です。ぜひ試してみてください。

インストール
まず、Node.js と Git をインストールしておいてください。Windows 環境では Chocolatey、Mac なら Homebrew を使うのが便利でしょう。

次に npm で、gulp と bower をグローバルインストールします（いずれも、すでに入っていたら不要です）。

$ npm install -g gulp
$ npm install -g bower

依存パッケージのインストール
作業ディレクトリに移動したら、git clone して、そのプロジェクトルートで npm install コマンドを実行します。すると、package.json の内容に従って、kuromoji.js の依存パッケージがダウンロード・インストールされます。以下に手順を示します。

$ git clone https://github.com/takuyaa/kuromoji.js.git
$ cd kuromoji.js
$ npm install

デモサーバで必要になる、bower の依存パッケージをインストールします。パッケージ（kuromoji.js 含む）は、 demo/bower_components/ 以下にインストールされます。

$ cd demo
$ bower install

デモサーバの起動
gulp-webserver を起動します。プロジェクトルートに移動して、gulp の webserver タスク（後述）を実行すると、8000 番ポートで Web サーバが立ち上がります（ポート番号を変更したい場合は kuromoji.js のプロジェクトルートにある gulpfile.js を編集してください）。

$ cd ..
$ gulp webserver

これで準備完了です。http://localhost:8000/tokenize.html http://localhost:8000/demo/tokenize.html にアクセスしてみてください。形態素解析のデモが表示されたでしょうか。
（ただ FireFox だと JS でエラーが出るので、 Chrome か Safari で試してください…すみません…）

demo/ の下のファイルを編集すると、ブラウザの画面が自動的にリロードされるはずです。Have fun!

タスク実行（ビルド・テスト等）

先ほどから何回か出てきた Gulp とは、いわゆるタスクランナーというものです。さっきは webserver タスクを実行しましたが、 kuromoji.js には他にも様々なタスクが定義されています。

• clean (dist/ の下をきれいにする)
• build (ソースから browserify したファイルを dist/browser/ の下に置く(ブラウザ版)。またはコピーして dist/node/ の下に置く(Node.js 版))
• watch (ソースの変更監視。変更されたら lint, build, jsdoc タスクを実行)
• clean-dict (dist/dict/ の下をきれいにする)
• build-dict (CSV の辞書ファイルからバイナリ辞書を構築する)
• test (mocha でテストを実行する)
• coverage (coverage/ 以下に Istanbul でカバレッジ計測した結果を出力する)
• lint (jshint でコードの静的チェックを行う)
• webserver (デモサーバを立ち上げる（上述）)
• jsdoc (jsdoc/ 以下に JSDoc を出力する)

例えば、scripts/dict/ 以下にある、辞書のCSVファイルを編集したあと、

$ gulp build-dict

を実行することで、kuromoji.js で使用される、各種バイナリ辞書がビルドできます。後述しますが、ユーザ辞書機能がまだありません。単語を辞書に追加する際には、CSV のシステム辞書に単語生成コストや文脈IDなどと共に行を追加して、丸ごとビルドしなおす必要があります（環境にもよりますが 1 分程度でしょうか）。

なお、 gulpfile.js のベストプラクティスがあまりよく分かってないので、本当はストリームとか使って、もっと効率的に書けると思います（誰か教えてください…）。

今後サポートしていきたい機能

• ユーザ辞書
• Search モード
• NAIST-jdic, Unidic のサポート
• 辞書サイズの低減
• N-best 解の出力
• kuromoji-server（形態素解析 Microservice）
• Stream サポート

ユーザ辞書とは、ユーザが自由に定義できる単語辞書のことです。基本的には、Kuromoji 形式のユーザ辞書がそのまま読み込めるようにするつもりですが、せっかく JavaScript なので、JSON 形式でも与えられるようにしたいと考えています（@johtani さんのアイデア）。
学習コーパスを追加することによる、再学習機能の要望も頂いていますが…まず CRF を JavaScript で実装しないといけなかったりして、相当大変そうです（パーセプトロンを JS で実装してみた感じからすると、不可能ではないと思いますが…）。ちなみに、同様のことを実現するには、MeCab で辞書を再学習させ、学習済み CSV を scripts/input/ に置いて、上述の gulp build-dict でバイナリ辞書をビルドすれば可能だと思います。誰か試してブログ書いてくれないかなー(ﾁﾗｯﾁﾗｯ

Search モードは、Kuromoji (Java) を特徴づける機能で、出力される形態素を、より小さくなるようにするモードです。形態素列が、より短い単語列になるように、ラティス上の接続コストを調整します。たとえば、検索エンジンで形態素解析器を利用する際、Recall を上げるためにトークンを細かくするというチューニングがしばしば行われます。そういった場合に有用となるモードです。なお、Kuromoji (Java) には、Search モードの機能に加えて、未知語を Uni-gram （1文字ずつ）に分解する Extended モードもあります。

NAIST-jdic, Unidic のサポートは、辞書に IPADIC 以外の選択肢を与えるものです。それぞれ特性があるので、用途によって使い分けます。Unidic は細かい形態素に分かれやすいという特徴があるので、検索エンジンのトークナイザ用途に向いているという話もあります（その分、転置インデックスのポスティングリストは長くなるので遅くなりますが）。

辞書サイズの低減に関しては、用途によっては不要な Feature を削った辞書、というのをサポートすることで、辞書サイズを多少減らせます。品詞、文脈ID、生起コストなどは削れないのですが、それ以降の読み・基本形などは、分かち書きだけしたいような場合には不要です。5MB以下まで小さくできれば、ほとんどのブラウザで許可なしでキャッシュできるので、2回目以降は辞書をダウンロードせずにすみます。また、見出し語を格納している辞書(base.dat, check.dat)についても、現在は Double-Array Trie というトライ木の一種を使っていますが、Minimal Acyclic Subsequential Transducer という FST の一種を使うことで、サイズを 1/10 くらいにできるという報告を聞いています。FST の実装については、Go で FST を書いた @ikawaha さんのエントリが参考になります。実装手法も面白いので、ぜひ fst.js を実装してみたいと思っています。
Go - Luceneで使われてるFSTを実装してみた（正規表現マッチ：VMアプローチへの招待） - Qiita

N-best 解の出力というのは、上位 N （任意の自然数）の形態素列の候補を順番に出力することです。kuromoji.js を使って IME を実装する際に必要になってくる機能です。様々なブラウザ上で（端末へのインストールなしで）高精度な日本語 IME が使えるようになる日が来るかもしれません。実装上は、Viterbi の前向きアルゴリズムのときに N 個までの候補を残すようにする、ビーム幅 N の Beam search をするだけです。当然、ビーム幅を増やしただけメモリをたくさん消費します。MeCab にはありますが、Kuromoji (Java) にはない機能です。

kuromoji-server と書いたのは、kuromoji.js を REST API でラップし、Web サーバ化するものです。これにより、形態素解析 Microservice （機能ごとに Web サーバを立てて HTTP 等で通信させ、全体を疎結合にするアーキテクチャ）なサーバを簡単に立ち上げられるようになります。kuromoji.js とは別の GitHub リポジトリになると思います。ただ、Kuromoji (Java) にも同様の kuromoji-server がありますし、Go で書かれた形態素解析器 Kagome には、Web サーバ機能が初めから組み込まれていますので、kuromoji.js で後述の Stream がサポートされるまでは、あまり存在意義がないかもしれません。

Stream サポートは、読んで字の通りで、kuromoji.js に対して文字列の代わりに Stream を与えることで、形態素の Stream を出力するための API を提供するものです。例えば、上記の kuromoji-server に対して、Twitter のストリームを流し込むと、形態素のストリームが出てくるので、それを Spark などの機械学習フレームワークに流し込む、といったユースケースが考えられます。ただ、内部的にかなり手を入れないといけないし、Node.js 側でもブラウザ側でも API がまだ stable ではないため、少し様子見かな…

あとは、高速化できるところが結構あるので何とかしたいです。。doublearray.js を作るときに、サロゲートペアの処理が嫌で（JavaScript の文字コードは UTF-16）、辞書は UTF-8 で保存するようにしてしまったんですが、そのために lookup のたび 1 バイトずつ見て UTF-8 から UTF-16 に変換する処理が走ってます。初めから UTF-16 で辞書を作っておけば、この変換は無くせます（日本語の場合、UTF-16 の方が辞書サイズも小さくなりますし）。他にも、無駄に parseInt してるようなところとかあって、そこも無くせそうな気がしています。

リファクタ的な観点では、async の代わりに Promise にするとか、オレオレ ByteBuffer をやめて ByteBuffer.js 使うとか、全体を ES6 で書き直して 6to5 でトランスパイルするとか、power-assert 使うとかもしていきたいのですが、かなり先になってしまいそうです（コントリビュートは大歓迎！）

リリース後の反応

kuromoji.js を GitHub リポジトリに公開した後、Twitter でツイートしただけなのに、どこから見つけてきたのか、2週間後くらいに MOONGIFT に取り上げられて（記事の内容については色々言いたいことがありますが…）、はてブでホットエントリに入ったらしく、「なんか kuromoji.js とかいう JavaScript の形態素解析器ができたらしい」みたいな話になっていることを Twitter や知人経由で知りました。
MOONGIFT に記事が上がった当日には、実際に何人かのエンジニアの方々が kuromoji.js を試していたようです。
その翌日、TypeScript から簡単に使えるように型定義ファイルが書かれ、それが DefinitelyTyped に登録されました。
https://github.com/borisyankov/DefinitelyTyped/pull/3377
さらに、それと並行して、 kuromoji.js を使った構文解析器が書かれました。
自然言語処理 - kuromoji.js使って構文解析した - Qiita
OSS のスピードすごい。

おわりに

形態素解析は、様々な自然言語処理にとって、必須とも言える基礎技術です。kuromoji.js だけで何か凄いことができるわけではありませんが、ブラウザ上で、より高度な自然言語処理をするときの足がかりとなってくれるはずです。

自然言語処理によって Web はもっとインテリジェントにできる、と自分は信じています。

kuromoji.js は、すごく簡単に使える OSS なので、これをきっかけに「自然言語処理って楽しい！」ってなってくれたら幸いです。

みなさんの手で、新しい Web を作っていってください。

Thanks to

• Christian Moen (Atilika Inc.)
• Gaute Lambertsen (Atilika Inc.)

who developed Kuromoji. They also advise me on some license issues and how to debug the morphological analyzer software.

• @ikawaha さん
• @taniokah さん

Go 言語で書かれた形態素解析器 Kagome の開発者である @ikawaha さんには、ダブルアレイの実装や、形態素解析器の細かい仕様（未知語処理とか）などについて、一緒に議論をしていただきました（教えられることの方が多かったけど）。Kagome と kuromoji.js は開発時期がほぼ同時だったこともあり、モチベーション的にも助けられました。ありがとうございました。
@taniokah さんは、自分の元上司であり、形態素解析をはじめとする自然言語処理のほか、情報検索、機械学習についても多くのことを学びました。発想の柔軟さにも驚かされることが多く、とても勉強になりました。「Kuromoji って JS で実装できんじゃね？」って言い出したのも確か @taniokah さんだったと記憶しています。今は別々の環境になってしまいましたが、今後ともよろしくお願いいたします。

IIR 2章まとめ

首都大学東京自然言語処理研究室（小町研）で行われたウェブマイニング勉強会（別名 IIR 勉強会）第2回の参加メモです。

今回の範囲は、2章の Term Vocabulary and Postings Lists です。

発表スライド：

• Term Vocabulary and Postings Lists (IIR Ch. 2) (PDF)
• Term Vocabulary and Postings Lists (IIR Ch. 2) (PowerPoint)

以下、ページ番号は上記 PDF 形式のスライドのものです。

参考：

• スタンフォード大学の講義ページ
• IIR Ch. 2 (PDF)

Document ingestion (p.1)

Recall the basic indexing pipeline

前回の復習。文書をインデキシングするステップは、大きく分けると以下の 3 段階。

1. Tokenizer でトークンの並び (Token stream) に
2. Linguistic modules でトークンを変換 (Modified tokens に)（正規化、見出し語化など）
3. Indexer で転置インデックスに

Parsing a document

文書のフォーマット、言語、文字コードを認識する必要がある。

これは、機械学習の問題として扱うこともできる（後ほどの章で出てくる）。

だが、実際にはヒューリスティックに行われることが多い。

Complications: Format/language

1つの文書に複数の言語、複数のフォーマットが含まれることもある。

例：フランス語のメールにドイツ語のファイルが添付されていたり、英文が引用されていたり

これらの機能をもつ、商用またはオープンソースのライブラリがある

（商用だとベイシスの Rosetta、オープンソースだと Apache Tika とかが有名かな）

Complications: What is a document?

文書をどの粒度で扱えばよいか？

なにをもって文書（”documents”）とするか？

• ファイル
• メール（複数の添付ファイルがあったり）
• 複数のファイル（HTMLにPPTやLaTeXが含まれていたり）

Tokens (p.6)

Tokenization

トークンに分割する処理。以下はトークナイズの例。

入力：

• “Friends, Romans and Countrymen”

出力：

• Friends
• Romans
• Countrymen

これらのトークンは、まだインデックスのエントリーの候補（後続の処理で変化しうる）。

では、どのようなトークンを出力するのがよいだろうか？

• Finland’s capital (sを含めるか？アポストロフィーを含めるか？)
• Hewlett-Packard (分けて2つのトークンにするか？くっつけて1つのトークンにするか？小文字にするか？)
• San Francisco (単一のトークンとして扱うか？ 2つに分けるか？)

Numbers

以下のような文字列を、どんなトークンにすればよいか？

• 3/20/91 (日付表現)
• Mar. 12, 1991 (日付表現)
• 20/3/91 (日付表現)
• 55 B.C.
• B-52
• 324a3df234cb23e (PGP key: 16進数)
• (800) 234-2333（住所？電話番号？）

昔の検索システムは、数値を含むようなトークンをインデキシングしなかった（posting が長くなりすぎるのが理由？）。

だが、Webで何かのエラーコードを調べるときなどには、非常に有用である。

「メタデータ」として、（ボディとは別のフィールドに）インデキシングされることもある。例えば、「作成日時」や「フォーマット」など。

Tokenization: language issues

トークナイズには、言語固有の問題もある。

フランス語

• L’ensemble (1つにするか2つにするか？)

ドイツ語

複合名詞の例

• Lebensversicherungsgesellschaftsangestellter (これは分けた方がいいよね)

（‘life insurance company employee’という意味）

ドイツ語ではcompound splitter moduleが有効 (パフォーマンスが 15% 上がる)

（小町さん曰く）コレクションのサイズによっても適切なトークナイズはかわってくる。データが増えてきたら、分けない方がprecision上がる。Google はたぶん両方やってる？

中国語

中国語と日本語はスペース区切りがない（複数のトークナイズの候補がありうる）。

• 莎拉波娃现在居住在美国东南部的佛罗里达。

日本語

日本語は、ひらがな、カタカナ、ローマ字、漢字を含む（日付や量の表現も複数ある）。

クエリを全てひらがなで書くこともできてしまう。

• フォーチュン500社は情報不足のため時間あた$500K(約6,000万円)

（なんか日本語変だけど…）

アラビア語・ヘブライ語

アラビア語やヘブライ語では右から左に書かれる。ただし、数字は左から右に読む。

Unicode での表現では、surface presentation は複雑に見えるが、保存されている形式は単純になっている（その他の言語と同じ並び）。

Terms - The things indexed in an IR system (p.13)

Stop words

よく出てくる単語 (a, and, to, be など) を省く処理（頻出 30 単語で全体の30%以下を占める）。

ただし、ストップワードの処理はトレンドではない。なぜなら、

• インデックスの圧縮で、サイズの問題は軽減できる（5.3 で扱う）
• クエリ最適化の手法 (7章で扱う) で、ストップワードの単語の処理時間もそれほど気にならない
• フレーズにすることで役に立つ例
  
  • ”King of Denmark”
  • “Let it be”, “To be or not to be”
  • “flights to London” (「関係」を表す単語。”to” に意味が含まれているので残すべき)

Normalization to terms

単語の正規化の処理。

ピリオドやハイフンを取ったりして、単語を「正規化」する。

• ピリオド：U.S.A. を USA に
• ハイフン：anti-discriminatory を antidiscriminatory に

正規化された単語は、「辞書」のエントリーになる。

Normalization: other languages

• アクサン：”résumé” を “resume” に

• ウムラウト：”Tübingen” を “Tuebingen” に

• 複数の日付の表現：7月30日 と 7/30

トークナイズと正規化の問題は、言語判定と密接に関わってくる。

例えば、以下の文の MIT はマサチューセッツ工科大学か、ドイツ語の “mit” か？

• Morgen will ich in MIT

正規化において最も大事なのは、ユーザの書くクエリに合わせること。

Case folding

基本的には、全て小文字にするが、以下のような例外もある。

• General Motors
• Fed vs. fed
• SAIL vs. sail
• C.A.T. (Googleでは2011年までCaterpillar Inc.の意味にならなかった)

ただし、ユーザはよく小文字で入力しちゃうので、全て小文字にするのが一番良かったりする。

Normalization to terms

もう一つの方法は、ユーザの入力をクエリ展開すること。この展開は非対称的になる。

• 入力：window, 検索語：window, windows
• 入力：windows, 検索語：Windows, windows, window
• 入力：Windows, 検索語：Windows

この方法は、より強力ではあるが、パフォーマンスは下がる。

Thesauri and soundex

3章と9章で詳しく扱う。

シノニム（類義語）とホモニム（同音異義語）

• car = automobile
• color = colour

インデックスを作るときに正規化してしまう方法と、クエリ展開でやる方法がある。

スペル訂正

発音に注目して正規化する、Soundex という方法がある。

Stemming and Lemmatization (p.21)

Lemmatization

見出し語化。

• am, are, is → be
• car, cars, car’s, cars’ → car

Lemma というのは、辞書の見出し語の形を意味している。

（辞書を使う、言語処理的な方法）

Stemming

語幹を取り出す処理。

• automate(s), automatic, automation → automat

（ヒューリスティックな方法で、言語に依存する）

Porter’s algorithm

英語で最もよく使われているステミングアルゴリズム。

ふつう、5段階の処理がある（それぞれ順番に処理する）。

末尾（接尾辞）が最長一致するルールを適用して変換を行う。

• sses → ss
• ies → i
• ational → ate
• tional → tion

末尾の “EMENT” は、その前に2文字以上あれば削る。

• replacement → replac
• cement → cement

Other stemmers

その他のステミングアルゴリズム。

• Lovins stemmer (1発で処理できる)
• Paice/Husk stemmer
• Snowball
• 形態素解析してlemmatization（そこまで大きな効果はない、らしい）

Language-specificity

以上の方法は、言語依存だし、アプリケーション依存でもある。

オープンソースで公開されているものを使うのがよい。

Does stemming help?

• 英語：Recallは上がるが、Precisionが下がることも
• スペイン語、ドイツ語、フィンランド語では有用

Faster postings merges: Skip pointers/Skip lists

Recall basic merge

posting のマージアルゴリズムの復習（図を参照）。

このアルゴリズムの計算量は O(m+n) → もっと効率的にできないか？

Augment postings with skip pointers (at indexing time)

posting の中の docId に、スキップポインタを持たせる（図を参照）。

Query processing with skip pointers

上の posting が 41、下の posting が 11 を見ている瞬間を考える（図を参照）。

スキップポインタの場所を見ているとき、スキップ先(31)を見て、それと比較する。

41 と 31 を比較すると、31 の方が小さいので、下の posting は 31 までスキップできる。

Where do we place skips?

このスキップポインタの方法には、トレードオフがある。

スキップポインタを多くする（スキップの幅を小さくする）：

• スキップポインタの比較回数が多くなる
• メモリ量もくう

スキップポインタを少なくする（スキップの幅を大きくする）：

• スキップの成功回数が少なくなる

Placing skips

√L (Lは posting の長さ) をスキップポインタの間隔とする方法 (Moffat and Zobel 1996)

インデックスが静的っぽいなら簡単。

動的なインデックスでは、 L が変化し続けるので難しい。

また、この方法は、単語の分布を無視している（静的に構築する場合で、単語の分布が分かっていれば、ある程度 L を予測できるかもしれない）。

全部オンメモリで処理するのでなければ、この方法は確実に有効である(Bahle+ 2002)。

なぜなら、メモリ上で posting をマージするコストより、posting を読み出す IO のコストの方が高いため。

Introduction to Information Retrieval (IIR) 1章まとめ

首都大学東京自然言語処理研究室（小町研）で行われたウェブマイニング勉強会第1回に参加してきました。

今回の範囲は、1章のBoolean Retrievalで、発表者は小町さんでした。

発表スライドはこちらです：

• Boolean Retrieval (IIR Ch. 1) [PDF]
• Boolean Retrieval (IIR Ch. 1) [PowerPoint]

参考：

• スタンフォード大学の授業ページ

以下、ページ番号は上記PDF形式のスライドのものです。

遅刻したのでスライド 8ページ目から（以下、ページ番号は上記スライドのもの）。

Term-document incidence matrices (p.8)

Unstructured data in 1620

非構造化データから検索を行うのが難しいという話。

たくさんのシェイクスピアの作品から、”Brutus AND Caesar but NOT Calpurnia”の条件を満たす作品（BrutusとCaesarを両方含み、Calpurniaを含まない作品）を探すことを考える。

一つの方法は、grep を使うことだが、これは正解ではない。

• NOT のような複雑な条件での検索ができない
• テキストのサイズが大きくなると遅い
• ある単語 (countrymen) の近くに出現する単語 (Romans) を探すことも現実的ではない
• スコアによるランキングができない

Term-document incidence matrices

単語 (term) を行、文書 (document) を列とする行列を考える（p.10の図参照）。

単語がその文書に出現するときは要素を 1、それ以外は 0 とする（一般的にはほとんど 0 になるので、非常にスパースな行列になる）。

すると、各単語ごとに 0/1 を要素とするベクトルを得る。

“Brutus” と “Caesar” と “Calpurnia” が全て出てくる文書（作品）を探すには、これらに対応する 3つのベクトルに対して、ビット演算の AND をとればよい。

• 110100 AND
• 110111 AND
• 101111 =
• 100100

よって以下が答えだと分かった（そうですか）。

• Antony and Cleopatra, Act III, Scene ii
• Hamlet, Act III, Scene ii

Bigger collections

文書数が 1 億とかになるとけっこうつらい。

行列のサイズを M x N とすると、

• N = 1 million documents
• 1000 words
• 6 bytes/word
• 6GB of data
• M = 500K distinct terms

よって 1 億 x 50 万の行列になる。無理。

もっとよい表現はないか？

The Inverted Index (p.15)

Inverted Index

各単語 t に対して、t を含む文書のリスト（posting list と呼ぶ）を格納する（p.17 の図参照）。

それぞれの文書は、docID というシリアル番号で区別する。

可変の posting list は、データ構造の双方向リスト (Linked List) で実装できる。

posting list は docID の昇順でソートしておく（理由は posting のマージの節で説明）。

Inverted index construction

1. トークナイズ (文字列を単語に分割)
2. 正規化 (例： U.S.A. を USA に)
3. ステミング（例： authorize と authorization を同一視）
4. ストップワードの処理（例：the, a, to, of を捨てる）

ちなみに、Google はステミングやストップワードの処理はやってない。Python の NLTK （ツールキット）にストップワードの一覧が入っているので参照するとよい（小町さん談）。

Indexer steps

2 つの文書をインデキシングする様子を見る。

トークンの列を、(Modified token, Document ID) のペアの並びにする。

単語をソート（辞書順、docID順）

1つの文書に同じ単語が現れているペア同士はマージ

単語は Dictionary に、docID は Posting に分割する（辞書には、単語頻度の情報も付加する。Query optimizationのところで説明）

Query processing with an inverted index (p.24)

Query processing: AND

インデックスはできたが、どうやってクエリを処理するか？

まず、単語を辞書でひき（2分探索でできる）、それぞれに対応する posting を取得する。

次に、2 つの posting をマージする（文書集合どうしの intersection）

The merge

マージのアルゴリズムについて（p.28 の疑似コード参照）。

2 つのリストの先頭を見て、異なっていたら docID が小さい方のリストの次の要素を見る。

docID が同じだったら、結果に追加する。

2 つのリストのサイズをそれぞれ x, y とすると、O(x + y) で計算できる。

前提：docID のリストがソートされていること

The Boolean Retrieval Model & Extended Boolean Models (p.29)

ブーリアンモデル（Boolean retrieval model）は、AND, OR, NOT を組み合わせたブーリアンクエリで問い合わせを行うことができるもの。

IR システムの最も基本的なモデル。

ブーリアンモデルは最近までずっと使われていた。電子メールや図書館の検索、少し前の Spotlight も。

例： WestLaw （法律の検索システム）

http://www.westlaw.com/

同義語（シノニム）の展開も含め、ユーザがクエリを組み立てていた。

Query optimization

AND クエリの処理を思い出すと、長い posting には、そのサイズに比例した時間がかかる(O(x + y))。

AND が複数ある場合、クエリをどの順番で処理するかによって処理時間が大きく変わる。

例（p.36参照）：(Calpurnia AND Brutus) AND Caesar

More general optimization

例：(madding OR crowd) AND (ignoble OR strife)

まず、全ての単語の posting を取得する。

次に、それぞれの OR クエリを処理した結果を推定する。

この推定値には、それぞれの posting のサイズ、つまり単語頻度を足したものとする（最悪の場合を考えている）。

この推定値が小さいものから順に AND クエリを処理する。

Exercise

以下のクエリは、どの順番で処理すればよいだろうか？

(tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)

（p.38の単語とその頻度のテーブルを参照）

Phrase queries and positional indexes (p.41)

Phrase queries

“stanford university” というフレーズ（単語の順序を考慮したもの）で検索したい。

“I went to university at Stanford” という内容の文書はヒットしてほしくない。

A first attempt: Biword indexes

最も単純なのは、2 単語を 1 つの単語と見なす方法。

3単語以上のフレーズクエリで false positive が防げない。

また、インデックスサイズも大きい。

Solution 2: Positional indexes

posting に、docID に加えて各文書での位置情報を付加する。

<term, number of docs containing term;
doc1: position1, position2 ... ;
doc2: position1, position2 ... ;
etc.>

false positive のないフレーズクエリが可能。

ただし、インデックスサイズは大きくなる。

Proximity queries

単語どうしの近さを指定して絞り込める。

例：LIMIT! /3 STATUTE /3 FEDERAL /2 TORT

（/k は、 k 単語以内という意味を表す）

効率的に Proximity queries を処理する方法については、IIR の Fig 2.12 を参照。

Structured vs. Unstructured Data (p.54)

IR vs. databases: Structured vs unstructured data

構造化データ（DB）: 数値の範囲検索など
非構造化データ：キーワード、概念（コンセプト）での検索

Semi-structured data

半構造化データ。

タイトルや箇条書きの部分など、文書の中の構造（場所）を指定して検索できる。

例：タイトルに “data”、箇条書きに “search” と書かれている文書を検索

例：タイトルに “Object Oriented Programming” 、著者が “stro*rup”（* はワイルドカードの演算子）

Lucene/SolrにおけるDeep paging問題

以前から興味があった、LuceneとSolrでのDeep paging関連のチケットを整理してみました。
調べてみたら、分散検索(Distributed Searchの機能)ではおろか、単体のSolrでもちゃんとサポートされてなかったっていう。

---

Deep paging問題とは

Deep paging問題の概要については、以下のブログエントリが参考になる。

Deep paging problem | Solr Enterprise Search

例えば、以下のようなSolrクエリを想像してみよう。

q=*:*&sort=price+asc&rows=100&start=50000

このクエリは、Luceneインデックスに対して50,001件目から50,100件目までの100件の結果を取得しようとしている。
しかし、SolrはLuceneインデックスから50,100件のドキュメントを読み込んで最後の100件を返すという動作をする。

このやり方は（予想される通り）非常に効率が悪く、Deep pagingなクエリに対して応答時間は以下のようになる：

Query	Average response time (ms)
q=*:*&sort=price+asc&rows=100&start=0	146
q=*:*&sort=price+asc&rows=100&start=999900	3184

2つ目のクエリでは100万件のドキュメントをインデックスから読み込むことになる。

Googleではこの問題に対して、91ページ目（このページによると75ページ目）以降は見せないというアプローチを取っている。
もちろん問題は解決しておらず回避しているだけだが、Web検索というシチュエーションでは問題になる場面は少ないのかもしれない。

フィルタによるDeep paging問題の解決方法

このエントリでは、フィルタによる解決方法を示している。
検索結果の対象となる文書群をあらかじめファセットで絞り込んでおくことで、Deep pagingの影響を抑え込むというアプローチ。
ただし、この方法には問題もある。
理想的には、フィルタをかけた後の文書数が、rowsで指定した数（上の例では100件）になっているのが望ましい。
しかし実際には、クエリを実行するまで検索結果の件数は分からない。
この問題を解決するために、2つのクエリを使う。
1つ目のクエリは、rows=0そしてstart=0を指定する。このクエリの結果でヒットした件数がわかる。
2つ目のクエリで、「自分で」ページングを行う。startパラメータは、前もって計算しておく必要がある。
（おそらく実際には、startパラメータを計算するため、例えばクエリq=*:*&rows=0&fq=price:[0+TO+9000]のヒット数が必要になる）

この方法でテストしてみると、応答時間は以下のようになる：

Query	Average response time (ms)
q=*:*&sort=price+asc&rows=100&start=0&fq=price:[0+TO+1000]	128
q=*:*&rows=0&fq=price:[9000+TO+10000] q=*:*&sort=price+asc&rows=100&start=100037&fq=price:[9000+TO+10000]	422

LuceneにおけるDeep Paging問題の解決方法

IndexSearcher.searchAfter()メソッドが実装される

[#LUCENE-2215] paging collector

このチケットでLuceneにIndexSearcher.searchAfter()メソッドがサポートされた。
（正確には、[#LUCENE-2127] Improved large result handlingでAaronさんによってこのアイデアが提唱された）
Lucene 3.5.0でFixされている。
CHANGES.txtには以下のように書かれている：

* LUCENE-2215: Added IndexSearcher.searchAfter which returns results after a specified ScoreDoc (e.g. last document on the previous page) to support deep paging use cases. (Aaron McCurry, Grant Ingersoll, Robert Muir)

詳細は、このパッチを書いたAaron McCurryさんのブログポストを参照：
http://www.nearinfinity.com/blogs/aaron_mccurry/making_lucene_hit_results_pagi.html

Paging Hit Collector (TopDocsCollector)というのを作ったらしい。ユーザが検索した結果の次のページをメモリ上のPriorityQueueにキャッシュしておいて、実際に次のページが要求されたらそれを渡す仕組みっぽい（違ってたらごめんなさい）。

IndexSearcher.searchAfter()メソッドでscore以外のソート順のサポート

[#LUCENE-3514] deep paging with Sort

searchAfter()ではスコア以外のソート順がサポートされていなかった。
コンパレータを実装して、ソートの際にもdeep pagingが可能になった。

Lucene 4.0.0-ALPHA

* LUCENE-3514: Added IndexSearcher.searchAfter when Sort is used, returning results after a specified FieldDoc for deep paging.  (Mike McCandless)

* LUCENE-3514: IndexSearcher.setDefaultFieldSortScoring was removed and replaced with per-search control via new expert search methods that take two booleans indicating whether hit scores and max score should be computed.  (Mike McCandless)

ただし、function queryを使ったソーティングでsearchAfter()がうまく働かないバグがあり、LUCENE-4504で解決されている。Lucene 4.1.0でFixしたようだ。

[#LUCENE-4504] Empty results from IndexSearcher.searchAfter() when sorting by FunctionValues

* LUCENE-4504: Fix broken sort comparator in ValueSource.getSortField, used when sorting by a function query.  (Tom Shally via Robert Muir)

SolrでのDeep Paging問題の取り扱い

CommonQueryParameters - Solr Wiki

[#SOLR-1726] Deep Paging and Large Results Improvements

Grantさんは、LuceneのIndexSearcher.searchAfter()メソッドを使った解決をしようとパッチ SOLR-1726.patch を書き、Trunkにコミットされた。
https://issues.apache.org/jira/secure/attachment/12512422/SOLR-1726.patch

しかし、YonikさんがSOLR-1726で以下のような問題を指摘している：

1. Luceneが内部的に使用しているdocidを使っていること
2. the optimization doesn't work if the docset is also requested (i.e. if facet=true) since it's only added in one place.
3. maxScoreがNaNを返すことがある
4. when using pageDoc, the results get incorrectly cached as a non-paged query (and hence other requests that use the same query will be incorrect)
5. when using pageDoc, any previous cached queries will be incorrectly used and hence incorrect results will be returned
6. NullPointerExceptionが簡単に起こりうる

以上より、deep-pagedでない場合の検索結果にも悪影響を及ぼす可能性があるため、Yonikさんがこのパッチの機能をTrunkのコードで利用できないように修正した。

例えば、Solrへのリクエストをパースするクラス、org.apache.solr.search.QParserでは、pagingパラメータをパースするためにgetPaging()メソッドが上記パッチ SOLR-1726.patch で追加されているが、Trunkのコードでは以下のようにコメントアウトされている。

  /**
   * use common params to look up pageScore and pageDoc in global params
   * @return the ScoreDoc
   */
  public ScoreDoc getPaging() throws SyntaxError
  {
    return null;

    /*** This is not ready for prime-time... see SOLR-1726

    String pageScoreS = null;
    String pageDocS = null;

    pageScoreS = params.get(CommonParams.PAGESCORE);
    pageDocS = params.get(CommonParams.PAGEDOC);

    if (pageScoreS == null || pageDocS == null)
      return null;

    int pageDoc = pageDocS != null ? Integer.parseInt(pageDocS) : -1;
    float pageScore = pageScoreS != null ? new Float(pageScoreS) : -1;
    if(pageDoc != -1 && pageScore != -1){
      return new ScoreDoc(pageDoc, pageScore);
    }
    else {
      return null;
    }

    ***/
  }

CHANGES.txtからもSOLR-1726に関する以下の記述は削除された：

* SOLR-1726: Added deep paging support to search (sort by score only) which should use less memory when paging deeply into results by keeping the priority queue small. (Manojkumar Rangasamy Kannadasan, gsingers)

結局、このチケットのステータスは Reopend になったまま。
誰かこの記事を見た優秀な方、解決してください;)

---

関係あるかどうか分からないけど。。

[#SOLR-2092] Use a native priority queue to order facet results

facet.limit（facet.offsetの間違い？）が大きいとき、ordからtermを引くのにコストがかかっているという予想。
このパッチでは、ファセットをBoundedTreeSetから優先度付きキュー(新たに追加されたorg.apache.solr.util.LongPriorityQueueクラス)で管理するように変更したようだ。使用メモリも少なくてすむとのこと。

Yonikさんが実験したところ、facet.offsetが10万の場合、10倍近く速くなったようだ。

アルゴリズムイントロダクション2章まとめ(1) 2.1まで

アルゴリズムイントロダクション第3版、2章のまとめです。
長くなりそうなので 2.1 までを先に記事にします。

自分が重要だと思った部分、興味のある部分に絞っていますが、省いた部分は教科書の該当ページを示しています。
基本的には教科書からの抜粋・引用が多いですが、理解した範囲で、自分の言葉を使って一部書き換えています。

---

2. さあ、始めよう

この章では、挿入ソートとマージソートを題材に、アルゴリズムの実行時間の解析方法を学ぶ。

具体的には、以下のテーマを扱う。
・ループ不変式を用いたアルゴリズムの正当性の証明
・疑似コードの定義
・RAM計算モデル
・入力サイズ
・マージソートを題材にした分割統治アルゴリズムの解析

2.1. 挿入ソート

この節では、ソーティング問題を解くアルゴリズムである挿入ソートを紹介する。
・ソーティング問題の定式化
・挿入ソートの疑似コード
・挿入ソートのループ不変式
・ループ不変式を用いた挿入ソートの正当性の証明
・疑似コードの定義

まず、ソーティング問題(sorting problem)を定式化する。

入力：n 個の数の列<a1, a2, ..., an>
出力：a1' <= a2' <= ... <= an' である入力列の置換 <a1', a2', ..., an'>

挿入ソートは、トランプで手札をソートする時のことを思い浮かべると理解しやすい(教科書p.14)。

挿入ソートに対する疑似コード INSERTION-SORT を示す。
INSERTION-SORT は、長さ n の配列 A[1..n] を引数として取る（疑似コード中では n を A.length で表現している）。
このアルゴリズムは、入力された数列を「その場でソート」する。すなわち、Aを記憶する以外に必要な記憶領域は、高々定数でしかない（必要な記憶領域が n に依存しない）。

INSERTION-SORT(A)

for j = 2 to A.length
    key = A[j]
    // A[j] をソート済みの列 A[1..j-1]に挿入する
    i = j - 1
    while i > 0 かつ A[i] > key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

ループ不変式と挿入ソートの正当性

今まさにソートしようとしている要素をキー(key)と呼ぶ。
配列のj番目にあるキーを挿入しようとしているとき、1番目からj-1番目までにあった A[1..j-1] はすでにソートされている。この性質をループ不変式(loop invariant)として定式化する。

挿入ソートのループ不変式：

第1~8行のfor文の各繰り返し開始されるときには、部分配列 A[1..j-1] には開始時点で A[1..j-1]に格納されていた要素がソートされた状態で格納されている。

アルゴリズムの正当性を容易に証明するためにループ不変式を利用する。
ループ不変式に対して３つの性質を示す必要がある：

初期条件：ループの実行開始直前ではループ不変式は真である
ループ内条件：ループの何回目かの繰り返しの直前でループ不変式が真ならば、次の繰り返しの直前でも真である。
終了条件：ループが停止したとき、アルゴリズムの正当性の証明に繋がる有力な性質が不変式から得られる。

最初の２つの性質が成立するならば、すべての繰り返しの直前でループ不変式は真である。
このやり方は、数学的帰納法と似ている。
ただし、３つ目の停止性を用いた証明方法が、普通の数学的帰納法との大きな相違点である。
多くの場合、ループ不変式を、ループを停止に導いた条件と一緒に用いる。

挿入ソートについてこれらの性質が成立しており、このアルゴリズムが正当であることを証明しよう。

初期条件：j=2のとき、部分配列は A[1] のみから構成され、これは元々 A[1] に格納されていた要素である。よって、明らかにソート済みであるから、最初の繰り返しの直前においてループ不変式は真である。

ループ内条件：for分の本体が行っているのは、A[j]（キー）を入れるべき場所が見つかるまで、A[j-1], A[j-2], A[j-3],... を1つずつ右に移し(4~7行)、空いた場所にその値（キー）を挿入する(8行)ことである。これにより、部分配列 A[1..j] は元々 A[1..j] に格納されていた要素から構成されており、かつソート済みである。for分の次の繰り返し時にはjに1が加えられ、ループ不変式が維持される。
厳密には、while文(5~7行)に対するループ不変式を記述し、それが実際にループ不変式であることを証明する必要がある。ここでは形式的な取り扱いを追求せず、上記の簡単な解析を信頼し、ループ不変式が外側のループに対して成立していることが証明できたと考えることにする。

終了条件：for文が停止するのは条件 j > A.length = n を満たすときである。ループの各繰り返しでは、jを1だけ増加させるから、停止時に j = n + 1 が成立する。このとき、部分配列 A[1..n]には、開始時に A[1..n] に格納されていた要素が、ソートされて格納されている。部分配列 A[1..n] が入力された配列全体であることに注意すると、配列全体がソート済みであると結論できる。

以上より、アルゴリズムは正当である。

疑似コードに関する約束

教科書p.p.16-18を参照

アルゴリズムイントロダクション1章まとめ

1.1 アルゴリズム

アルゴリズムとは何か？

入力から出力を生成する、計算手続き（入力を出力に変換する計算ステップの系列）。
アルゴリズムは、計算問題を解くための道具と見なせる。
すべての計算問題のインスタンス（具体例）に対して常に停止し、その出力が正しいとき、アルゴリズムは正当である(correctness of an algorithm)という。

アルゴリズムで解くことができる問題

・DNA解析（15章の動的計画法）
・経路探索（24章）、情報検索（11章、32章）
・公開鍵暗号とディジタル署名（31章で扱う数論的アルゴリズムと整数論）
・限られた資源での利益最大化（29章で扱う線形計画法）

本書で扱う具体的な問題

・道路地図上の最短経路の発見（24章）
・2つの記号列の最長共通部分列（15章）
・トポロジカルソート（22章）
・凸包（33章）

データ構造

データ構造(data structure)は、アクセスと更新を容易にする目的のために、データを蓄積し組織化する方法である。どのデータ構造もすべての目的に対して満足に働くことはない。したがって、いくつかのデータ構造についてその長所と限界を理解することが重要である。

アルゴリズムの設計と解析

公表されたアルゴリズムで解決できない問題を解く場合に、自分自身でアルゴリズムを開発し、正当性を証明し、効率を解析する必要がある。本書では、それらの具体的な問題と技法を取り上げる。

計算困難な問題

34章で、NP完全問題について解説する。

並列性

27章（総合版の範囲？）でマルチスレッドアルゴリズムのためのモデルを紹介する。

1.2 科学技術としてのアルゴリズム

計算機の速度もメモリの量も無限ではない。有限の資源を賢く使うために、効率の良いアルゴリズムが役に立つ。

効率

2章で2つのソーティングアルゴリズムを比較する。
挿入ソート：計算時間がn^2に比例する
マージソート：nlgnに比例する
挿入ソートを、何十倍も効率よく実装し、1000倍も速いマシンで実行したとしても、1000万個の値のソートになるとマージソートより10倍以上遅くなる、という例をここでは紹介している。問題のサイズ（ここでは要素数）が大きくなると、差はさらに開く。

アルゴリズムと他の科学技術

上で見たように、システム全体の効率は、アルゴリズムの効率に大きく左右される。つまり、ハードウェアの製造技術のような先端技術と同様に、アルゴリズムは科学技術(technology)である。
ハードウェア設計、GUIの設計、ネットワーク上でのルート選択、コンパイラ、インタプリタ、アセンブラ等、これら全てにアルゴリズムは用いられている。

アルゴリズムに関する知識と技術をしっかりと身につけていることが真の技能をもったプログラマを未熟なプログラマから区別する特徴の1つである。現代の計算技術を用いると、アルゴリズムを知らなくてもいくつかの仕事を達成できる。しかし、アルゴリズムの優れた知識があれば、はるかに多くの仕事が達成できる。

ブログ。