連結対象を選ぶことと、連結をコーパス全体に適用すること

2単語の連結を基本操作としてえらび、
各ステップで連結を貪欲に行うことを選んだ時点で、
計算すべきことが 2 つできた。

連結の適用：
もっとも簡単なのは、コーパス全体を大きさ２の窓で走査して、連結を適用するもの。
ただし、コーパス全体がセグメントを要素とする連結リストでないと、効率的でない。

すべての 2-gram の出現位置を計算しておくと、
連結の適用自体は出現回数分のオーダーの時間となる。
出現位置の初回の計算はしょうがないからやるけれど、
次からは、変化分、追加分だけを更新する。
まず、連結された 2-gram のエントリは消す。
連結の適用とともに、連結されたセグメントの前後 A,B のどちらかを共有する 2-gram xA, By に関して、
もはや（ここでは）存在しない2-gram xA ,By の出現位置情報を削除する。
そして、xAB, ABy のエントリに（エントリがなければ作って）出現位置情報を追加する。
追加と削除の効率性から考えると、2-gram の出現位置のデータ構造は、
2-gram --> 位置 -> 定数
の2段階のハッシュがよさそう。

Suffix Tree を使う場合、出現するすべての部分文字列の出現位置は、
部分文字列の長さ分、木をたどった位置の部分木を深さ優先探索して葉を訪問していけば分かる。
問題は連結に関して木を更新すること。
これについて、色々考えた結果[2005-11-22-1]、Suffix Vector で表現するとよさそう。
ハッシュほど効率はよくないかもしれないが、我慢する。
あるいは、単語深さ 2 のノードに、出現位置情報をキャッシュしておくという方法もある。
（木の中に、上述の出現位置のハッシュを持たせておくようなもの）
この情報は、木の更新とは別に更新する。
Suffix Tree の利点は、任意の n-gram の頻度をノードに保持しておけること。

連結対象として選ぶこと：
えらばれるのは、
その連結をコーパス全体に適用したら、コーパス全体のエントロピーがもっとも小さくなるような連結。
連結によるエントロピーの変化分は、最初は全候補について計算する。
ステップを移る（１つの連結が全体に適用される）ときに、
ある連結に関するエントロピーの変化分は、変わらないこともある（２つの連結がたがいに近くに現れない場合）
変わるのは、適用された連結を構成するセグメントのどちらかが含まれているような連結と、
（以下略）
変わる連結は、連結の適用と同時に、集合として記録しておく。

エントロピー差分が変化する場合というのは、式中の一定の数の項に変化が起きる場合と、
式の項の数自体に（大幅な）変化が起きる場合とがある。

前者は差分評価により、式全体の再計算なしに更新できる。
後者の場合は、いまのところ、再計算することにしているが、
よく考えると差分評価が可能かもしれない。

いずれにしても、エントロピー差分の式にはすくなくとも 4-gram までの頻度情報が必要になる。
ただ、ぜんぶの組合せが必要という訳ではなく、
1-gram, 2-gram についてはすべて、
3-gram については、ABA, ABB, AAB の形のもの、
4-gram については、ABAB の形のものが必要。
単語2-gram の数のオーダーの領域量で抑えられる。
が、領域量に関しては Suffix Tree の方が有利と思われる。

更新のあと、エントロピー変化分最小の候補をえらぶには、
エントロピー変化分の順で 2-gram を順序づけするヒープを作っておき、
なくなった 2-gram の削除、追加・変更された 2-gram の追加を行い、
そのあとでの最小要素を選べばいい。

ということで、ハッシュを用いた場合でも、Suffix Tree を用いた場合でも、
対象データの大きさに直接には依存しない計算時間、領域で実現が可能なはず。