テキスト処理入門：Pythonで高速な辞書を作ろう（その4）

ダブル配列のPythonによる実装（その３）

ここまで、ダブル配列の作成の話がメインでした。
お読みいただいた方なら検索についても、ある程度はイメージが浮かぶのではないでしょうか。
作成の話がまだちょっと難しいという方は、もう一度「ダブル配列の作成」を読みながら、
手を動かしてダブル配列の表を記入してみてください。

ここでインクリメンタルサーチについて書いておきます。
説明用の６単語では「どんちゃん」を検索中、頭から２文字目の「どん」まで来た時に葉ノードが見つかります。
Pyrthonのdictのような連想配列では、「どんちゃん」と「どん」は別々の検索なのですが、
ダブル配列を含むTrie木では、検索キーと前方一致する部分文字列との一致も同時に拾うことができます。
Trie木の最大の強みです。

文があり、その中から見出し語と一致する文字列を全て探すような処理を考えた時、
もしdictで同じような辞書検索を作るとしたら、その文の全ての文字位置から始まる
全ての長さの部分文字列を作成して、それぞれdictに問い合わせる必要がありますね。
長い文になればなるほど大変そうです。
一方、Trie木で検索する場合はどうでしょうか。
その文の各文字位置だけを与えれば済んでしまいます。
その位置から始まる色々な長さの文字列をわざわざ検索キーとして作成する必要がありません。
また、Trie木の中で遷移できなくなれば、すぐに処理を抜けるので、
dictの時のように長くて無駄なキーが検索に使われることすらありません。
そして、一回の処理を抜けた時、そこまでの部分文字列で辞書と一致する見出し語が全て得られます。

さて、ダブル配列を利用するプログラムは、それを作成したプログラムとは無関係に書いてみようと思います。
こういう時、jupyter-notebookなら下のセルに移動するだけなので楽です。

ダブル配列を作成するプログラムには、様々な量（変数）が登場しました。
しかし、ダブル配列を利用する際に必要なのは、
あるノード位置におけるbaseとcheckの値だけです。
値を得るためにbaseやcheckの配列をわざわざ用意する必要すらありません。
ファイルを読み込み、そのバイナリに直接アクセスしましょう。

利用のプログラムでは、クラスを作ります。class DArrayのメソッドは４つです。

メソッド：__init__
辞書の３つのファイルを読み込んでそのままメンバとして保持します。
ただし文字=>文字IDの対応は、c2codeという名前のdictで持っておきます。

メソッド：base
ノード位置からそのbase成分を返すgetterのようなメソッドです。

メソッド：check
ノード位置からそのcheck成分を返すgetterのようなメソッドです。

メソッド：search_gen
ダブル配列の検索も、その作成の時とノードの遷移の様子は全く同じです。
違うのは、ノードの新たな作成がなく、遷移できない時はそのまま検索を終える点です。
ある意味、ダブル配列の作成より単純なアルゴリズムになります。
このメソッドは、その方が簡単に書けるのでgeneratorにしてあります。
呼び出す時は、listに変換したり、for文のinのところに書いたりします。

メソッドの入力は、インクリメンタル検索を行う検索キー（例えば丸ごと１文）
および、文字IDの一覧です。また、擬似コード風の文章で書いてみます。

DArrayクラスのプログラムは以下のようになります。かなり短いです。

［コード例４］

ダブル配列のPythonによる実装（その４）

では、上のDArrayクラスを実際に使ってみましょう。
長めのWikipediaの記事から、Wikipediaの見出し語の文字列がどれぐらいヒットするか検索してみたいと思います。
Wikipediaはスクレイピング禁止ですので、手っ取り早く
ブラウザで記事一覧からどれか記事を開いてコピペして、テキストファイルとして保存しましょう。

「長いページ（Wikipedia）」
 https://ja.wikipedia.org/wiki/特別:長いページ

私は「ヨーロッパにおける政教分離の歴史」を選びchurch.txtとして保存しました。
500KB弱ぐらいの、１記事としては結構長いテキストです。

記事の検索は、以下の３段階の処理になります。
(1)ファイルの行を読み、
(2)その行の文字列から各文字位置を先頭とする部分文字列を作り、
(3)それぞれの部分文字列についてインクリメンタル検索をする。

検索メソッドをgeneratorで書いたので、こちらでも各段階をgeneratorにしてみましょう。
多段generatorは、結果を変数にして次々と渡すだけです。
渡した時点では、実際の計算は行われません（遅延評価）

上流のgeneratorで、２個の変数をまとめてtupleの形で流すとします。
その一部を下流のgeneratorの中で使うにはどうしたら良いでしょうか。
もし、下流のgeneratorの中で、

としてしまうと、まず上流のgeneratorを何回も呼び出した時の全結果が配列に展開されます。
（恐ろしいですね！）
そして次に、その配列を２要素のtupleに渡そうとするため、要素数のエラーになります。

では、どうすればうまく行くかと言うと、下流のgeneratorの中でいったんforループを作り、
その中で受けるようにすれば良いです：

以上、実際にプログラムを見ていただいた方が早いかもしれません。

［コード例５］と［結果例５］

記事中に辞書との文字列の一致が、およそ8万5千回ありました。
メモリ使用は64MB程度、Core i7で2秒程度でした。
同じことを連想配列のdictでやると、20秒程度でした。
dict版では、ハンデとしてwords.txtからdictを作成するのに要する時間は除外しました。
元々、Trie木は高速なアルゴリズムなのですが、中でもダブル配列は爆速ですね。
（↑本記事のまとめはこの１行）

最後に少しだけ考察

このプログラムの改善課題について考えます。
「システムに組み込むなら、もっとエラーチェックが必要ではないか」
という話もありますが、そちらの方面は今は置いておきます。

「C++で書き直す」
「文字単位ではなくUTF8のバイト単位で扱い文字コード値をそのまま使う」
どちらも難しくないので、興味のある方は是非試してみていただきたいです。

「Patricia木にする」
Patricia木（radix trie / compact prefix tree）というのは、Trie木の工夫の１つです。
本記事の説明および実装では、遷移が分岐しない場合の葉ノードを圧縮しました。

Patricia木では、葉ノードに関わらず、分岐がなく一本道になるようなノードを全て圧縮します。
説明のために使った6単語の世界だと、例えば「で→ん→語末」の遷移には分岐がなく一本道なので１つにまとめられます。
そうすると、必要なノードは9個になります。是非数えてみてください。

Patricia木は、Trie木を圧縮する方法として、昔から大変良く使われています。
おそらくですが、ダブル配列でも一般的な方法だと思われます。
ただし、ダブル配列をPatricia木にすると大きく変わる点があります。
それは、一本道をまとめた結果、「全てのノードが複数の遷移先を持つ」ということです。
ということは、ダブル配列の空き領域をきれいに左から埋めて行くのが困難になるということに他なりません。

ダブル配列の作成の際、複数の局面を並列に処理することは出来ず、
必ず１ステップずつシリアルに処理しなければならないので、仮に充填問題として解くと、時間が掛かりすぎることでしょう。
一方、ノードを作る度に空き領域を毎回毎回左端のルートの位置から探していては、だんだん処理が遅くなります。
そんなわけで「ある程度まで空きが詰まって来たら、その領域ではそれ以上はがんばらない」というのが
現実的な手法のようです。ある領域の空きが全て埋まらなくても、何らかのタイミングや条件で、
遷移先候補を探し始める左端の位置を、右にずらして行くわけです。

実は、本記事のプログラムの作成にあたっては、ダブル配列の成長にともなって
空き領域がどうなるかについて、調べながら作業を進めました。
その結果、処理中に分岐のない遷移が大量に発生するため、
それらのノードがどんどん空きを左から埋めてくれることが分かりました。
結果として、ダブル配列の作成も順調で速いです。
「分岐する遷移がほとんどを占める場合」など、タスク（または入力データ）によっては、
本記事の空き位置の更新方法では問題が生じる可能性もあります。

以上の経緯があり、本記事中ではPatricia木を扱いませんでした。
もしまた機会があれば取り上げてみたいと思います。

以上、Pythonで辞書引きプログラムを作ってみました。お読みいただきありがとうございました。

※本記事中のプログラムは自由にアレンジしてご使用ください。
ただし、それにより生じた不利益に対する責任は負いかねます。

1234コード