豪鬼メモ

一瞬千撃

英文コーパスの簡易インデックス作成

英文の単元語コーパスや英文を含む多言語コーパスを高速に検索するための簡易的な索引を作るプログラムを書いてみた。辞書に収録した語句の例文を表示するための利用を念頭に置いている。貧弱なノートPCでも大きなコーパスを扱うための工夫をいくつかしたので、メモしておく。


単言語コーパスや多言語コーパスは世の中に数多く公開されている。特定の語句を含む例文を探すのにとても便利だ。100万文くらいの規模ならば、grepにかけるだけで1秒以内に検索できるから、特別な索引を作る必要がない場合も多い。しかし、共起頻度を計算するなどの機械的な処理を行うとなると、grepのような逐次探索で該当文を探すのでは遅すぎる。一回の探索が0.1秒で終わるにしても100万回やれば10万秒になり、1日では終わらなくなってしまう。

いわゆる検索エンジンのプログラムも多く公開されているので、それらを利用するのもよい。ただ、今回は辞書の収録語に絞ることで、非常に小さな索引を作り、かつ高速に検索できるように最適化した。索引は我らがTkrzw形式で保存するようにした。

田中コーパスを入力例として索引を作ったものをここにアップロードしておくので、ちょっと遊んでみていただきたい。TkrzwがインストールしてあるLinuxMacWindowsマシンであればコマンドを実行するだけで遊べる。田中コーパスパブリックドメインの日英対訳コーパスであり、およそ15万対が収録されている。素人の学生が翻訳したから質が良くないとかいう評もあるらしいけども、見た感じ結構ちゃんとしていると思う。

索引の検索は二段階で行う。まず、適当なフレーズを指定して、それを含む英文のIDの一覧を取得する。次に、そのIDを指定して、実際の英文とそれに対応する和文を取得する。例えば、「get away」を含む英文を3つ見たいなら、以下の操作を行う。

$ tkrzw_dbm_util get tanaka-index.tkh "get away"
851,7721,13460,15660,45300,47723,52437,57910,58707,69814,81290,86468,87883,
88907,91870,95422,105830,105910,106933,121103,132258,136411

$ tkrzw_dbm_util get tanaka-index.tkh "[851]"
A molester is truly the enemy of women. I'll never let them get away with it.
痴漢は本当に女の敵。絶対に許さないです。
$ tkrzw_dbm_util get tanaka-index.tkh "[7721]"
I urged him to get away and cool down.
僕は彼に身を引いて事態が落ち着くのを待つように勧めた。
$ tkrzw_dbm_util get tanaka-index.tkh "[13460]"
She wanted to get away from everyday life.
彼女は日常生活から逃げ出したかった。

フレーズから文IDのリストを得るための索引と、文IDに対応する文を得るための本文データベースを同じファイルで扱いたかったので、文IDのキーは "[XXX]" と四角カッコで囲む仕様にした。フレーズは小文字に正規化しているが、屈折を原形に戻したり、その他のステミング処理はしていない。なので、「Japan」は「japan」として探すべきだが、「be composed of」に当てはまるパターンが知りたいような時は、「be composed of」「is composed of」「was composed of」などと何回かに分けて探さなければならないこともある。

コーパスの元のTSVファイルが14MBくらいなのだが、索引と本文データベースを合わせたファイルが24MBにしかならないというのがポイントだ。しかも構築作業もこのコマンド一発動かせばできて、10年くらい前に買った私のノートPC上でも数分で完了する。索引を小さく維持するのが要点だ。田中コーパスの15万文くらいの規模であればもっと富豪的な実装にしてもよいのだけれど、100万文とか1000万文のコーパスにも対応することを考えると、より貧民的な、メモリとCPUをけちったアルゴリズムにして、スケーラビリティを高めておきたい。

工夫その1。複数語のフレーズでの検索に対応するために、文中に現れるN-gramの単語の組み合わせを拾いつつも、事前に与えたパターンに一致するもの以外は捨てる。例えば、「Water is composed of hydrogen and oxygen.」という文から3-gramまでのパターンを抽出すると、「water」「water is」「water is composed」「is」「is composed」「is composed of」「composed」「composed of」などなどが得られる。それらを予め辞書から抽出したリストと照合すると、「water」「is」「composed」「of」「oxygen」「hydrogen」という1-gramのパターンと、「is composed of」が残る。これでデータ量が半分以下になる。なお、辞書から与えたリストにはステミング処理をかけておき、例えば「is composed of」は「be compose of」としてメモリに保持する。照合する際にも候補となるパターンに同じステミング処理をかける。このステミング処理はNLTKというライブラリを使ってやっていて、それが結構遅い。というか、その時間が実行時間のほとんどを締めていたりもする。ただ、入力量に対して線形に遅いだけなので、とりあえずは我慢する。

工夫その2。辞書にあるパターンだけに絞ったとしても、「the」「a」「is」「of」などの頻出語の索引はやたら大きくなってしまう。「the」を含む例文を8万個とか見たいというユースケースはそんなに多くないのだから、一般的な例文検索につかうのなら、全部持っておく必要はない。ということで、予め決めた数(100文)を超えた時には、貯水池サンプリングを行うようにした。つまり、新規要素を加える際に、保持する数をC、該当が入力された回数をOとすると、I = randint(0, O+1)を計算して、IがCより小さかった場合に、そのIの添字の既存要素と新規要素を入れ替える。これによって、個々の索引の長さが異なりパターン数の定数倍に制限され、異なりパターン数は事前のリストで制限されるので、空間計算量がO(1)になる。索引に関してはどこまでもスケールするから、ノートPCで1億文を処理しても大丈夫だ。採用サンプル数はメモリ容量と相談して任意に決められる。手抜きバンザイ。

工夫その3。やたら長い文があると、その長い文からのパターンがサンプリングに生き残って検索に該当する確率が上がってしまう。文から採用されるパターンの中での重複排除は行うとして、それでも採用されるパターン数が多くなって、索引全体を汚すことになる。長い文は例文としては不向きで価値が低いにもかかわらず、採用される確率が高いというのはもどかしい。そこで、各文から採用するパターンの数に上限(50個)を設けることにした。その拾ったパターンが上限数を超えた場合、各パターンの出現頻度を計算し、それが低いものを優先的に採用することとした。基本的には3-gramや2-gramは頻度が低くなるので採用され、まだ余裕があれば、1-gramの中で頻度が低いものを採用する。結果として、長い文からは「is」とか「the」とかは取られないかもしれない。「get carried away」とか「impressionist」とかの稀な語はほぼ確実に拾う。

工夫その4。これは効果はそんなに大きくないが、記号をまたぐフレーズを禁止してパターン数を削減した。例えば「His saying, "Good bye" was surreal.」とかいう文を処理するとして、「his saying good」「saying good」「good bye was」「bye was」「bye was surreal」は記号をまたぐので、辞書リストと照合する前に却下される。こうすることで、カンマ区切りや引用符越しなどでたまたま隣あった語が偶然にも熟語と同じパターンになるような事態が避けられる。

工夫その5。スケーラビリティとは関係ないのだが、入力として任意のTSVファイルを取れるようにした。タブで区切った第2フィールドの英文のみを索引の対象とし、第2フィールド以降は特に何の処理もせず本文データベースにそのまま収録される。これによって、英語の単元語コーパスの索引にも使えるし、日英や日中などの多言語コーパスの索引にも使える。トークナイズとステミングの実装を注入すれば索引対象が英語以外の言語の場合にも対応できそうだが、今はやっていない。

実はもう少し最適化の余地はあるが、メンテナンス性を考えて採用しなかった。索引の文IDの列は、値が低い数値の列なので、ソートしてから差分列に変換した上でイライアス符号で圧縮するとかなり小さくできる(話は逸れるが、UTF-8とイライアス符号って考え方が似ている)。また、文のデータをデータベース内で保存しているが、それをやめて、元のTSVファイルのデータを参照した方がいいかもしれない。行の先頭のオフセットを索引に記録しておけばいいのだ。とはいえ、今の実装の方が既存のコマンドラインツールを使って目視でデータを確認できるし、ファイルが一つの方が管理しやすいし、各種運用ツールの実装もデータベースファイルを使っている方が遥かに楽だ。

まとめ。そんなこんなで、任意の英文コーパスや英文対訳コーパスの検索システムが簡単に構築できるようになった。これを具体的にどう使うかはあんまり詰めていないのだが、辞書の語義に例文をつけたり、語義の並び替えをしたり、訳語の並び替えをしたりといったことに使えそうだ。これだけ切り出して例文検索システムとかにしてもいいんだけど、それだったら普通の検索システムを使えばいい話なので、やはり機械的な処理に使うのが向いているだろう。