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

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

以上の説明をそのままPythonのプログラムにします。
（ここから読み始めて内容が気になる方は、戻って軽く目を通してください）
先に方針や注意点を書いておきます。

「局面ごとに処理する」
ダブル配列の作成は、全体の処理を「あるノードから次のノードへの遷移」という
局面の処理に分解することが出来ます。
それを全ての局面について行うわけです。
１つの局面の処理には、どのような入力が必要か考えてみると、

「見出し語と前方一致する任意の文字列（空文字列と見出し語自身も含む）について、
次に来る１文字（語末含む）の集合」がまず必要です。
部分文字列は文字IDのtuple、次に来る文字は文字IDのsetで表現して、dictに格納します。
本記事では「分岐データベース」と呼んでおきます。

もう１つは、その局面での遷移元のノード位置です。
つまり、先頭から部分文字列の終わりまで遷移した時のノードの位置です。
これも、部分文字列の文字IDのtupleをキー、そこまで遷移した時のノード位置を値として、
dict（defaultdict）に格納します。本記事では「遷移元データベース」と呼んでおきます。

分岐データベースは、前もって作成しておくことにしましょう。
遷移元データベースの項目は、ダブル配列を作成しながら追加して行きます。
また、項目に該当する局面の計算が終わったら、もう使わないので削除します。

「利点と注意点」
さて「局面ごとに処理し、全ての局面について繰り返す」ような計算方式には２つの利点があります。
１つは「再帰を使わなくて良いこと」です。
再帰を使うと楽に実装できる気がしますが、深くなり過ぎないように気を使ったりなど、
実行時まで考えると大変な面もあります。
一方、再帰を使わずにループで書こうとすると、一般にはアルゴリズムが複雑になります。
今回もループで書こうとしていますが、既に処理を局面に分解してあるので、
あとは局面の数だけ単純ループするだけなので楽です。

利点のもう１つは、幅優先とか深さ優先とかの計算の順序が、プログラムの設計と無関係になることです。
入力データ（分岐データベースの項目）の取り出し順序を変えればどちらにも対応できますし、
どちらでもない方式でも計算可能です。（今回は深さ優先です）

良いことづくめですが、注意点もあります。それは「ある遷移を計算する時には、
その１つ前の遷移の計算が既に終わっていなくてはならない」ことです。
遷移元データベースに、その局面での遷移元のノード位置が必要だからです。
分岐データベースを準備する際に、留意することにします。

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

プログラムを書いて行きます。まずは、入力データ（見出し語リスト）を準備しましょう。
見出し語は、これまでの説明でおなじみの「でん」「どこ」…の6語でも良いのですが、
せっかくなので、最初に書いた通り、Wikipedia日本語版のタイトルリストを使います。
ほぼ全ての文字が、それだけでタイトルに含まれてしまうので、２文字以上の見出しを使います。
本記事の執筆時点（2018.10）では180万個ぐらいです。申し分ない量ですね。
これをwords.txtとして保存し直しておきます。見出し語の単語IDは行番号にします。
（実際の辞典でしたら、語義データのレコード番号などになることでしょう）
処理を載せます。タイトルのダウンロードはリンクを示しますので手作業でどうぞ。

［コード例２］

では、ダブル配列の作成に必要な関数を書いて行きます。

関数：get_branch_db
まず、分岐データベースを準備する関数です。説明が繰り返しになりますが、
「先頭からの部分文字列」=>「その次の１文字」をdictに登録します。
文字にIDを振る処理もついでにやっておきます。あと、上の注意点で説明した順序を満たすようにしましょう。
ところで、この処理にはdefaultdict を使って、なおかつキーの登録順を維持するようにしたいのですが、
Pythonのバージョンや実装によっては、この動作は保証されません。
そのようなdictを新しくクラスとして作っても良いのですが、今は単純で素朴な解決策として、
キーの配列をdictとは別に作成することにします。

関数：get_base_s
位置sから遷移する際のbase[s]を求める関数を作ります。
分岐する文字の文字IDの配列のそれぞれの要素から、最小の文字IDを引いたオフセットの配列を作ります。
オフセットの配列の各要素が未使用領域のなるべく左に来るような位置を求めます。
そこから逆算すればbase[s]が求まります。

関数：update_slot_start
上とも関連しますが、遷移先を決めるために空きを探す際、毎回ルートから探していては、
ノード数が増えるとどんどん遅くなってしまいます。
ダブル配列の空き位置は、左から埋まって行く（はずな）ので、空き位置の左端を探す関数を作り、
適宜呼び出しましょう。

関数：make_darray
ダブル配列（base, check）の作成関数です。関数の入力は分岐データベースです。
アルゴリズムを擬似コード風の文章で書いてみます。

関数：save_darray
作成が終わったダブル配列をファイルに書き出します。
とりあえず配列の１要素あたり、3バイト取っておきます。
（本来はこのような決め打ちは良くないので計算しましょう！）
バイナリの扱いはpackやunpackを使わなくても便利関数があるのでそれに任せます。
あと、文字と文字IDの対応表は、文字列の形でテキストファイルに出力します。

最後に、以上の処理の呼び出しをmain関数にまとめます。
では、そのコードです。

［コード例３］と［出力例３］

無事にdarray.{base,check,code}の３つのファイルが出力されたでしょうか。
およそ770万個のノードが作成されました。
CPUがCore i7 でメモリが8GBなら、１～２分の処理になるはずです。
さて、次に仕上げとしてこのダブル配列を使った検索を考えましょう。

1234コード