ハッシュを使った現在の実装、高速化の見通しはどうなっているのか？

現在の実装↓

データ：
{
本体文字列の連結リスト
単語1〜4gramの出現頻度を保持するハッシュ
}
for(;;) {

1) 連結した場合の記述長変化分が最小の候補を求める：
{
foreach [ 連結候補 <- 単語 2-gramのすべての種類 ] {
1.1) 連結した場合の記述長変化分の計算：
{
連結候補 AB の連結される出現に関連する変化分（定数個）
AB の連結されない出現に関連する変化分（定数個）
foreach [ その他の単語 <- A,B 以外の単語すべて ] {
その他の単語の出現に関連する変化分
}
}
}
}
1.2) 最小の候補の記述長変化が正なら、手続き全体を終了
2) 連結による本体文字列（連結リストとして表現されている）の更新：
{
foreach (大きさ2の窓で本体文字列を走査して単語 2-gramの出現を調べる) {
2単語が連結対象なら、つなげる
}
}
3) 頻度情報の更新
{
foreach (大きさ4の窓で本体文字列を走査して単語 2-gramの出現を調べる) {
1,2,3,4-gram の出現頻度を数える
}
}
}

1) は大雑把に見て単語 2-gram の種類数 x 単語 1-gram の種類数に比例する計算時間。（だいたい、単語1-gramの種類数の３乗ともいえる）
2), 3) は本体文字列の長さに比例。

本体文字列を長くしていったときに、
単語 1-gram の種類数の3乗は（連結による新単語を考慮しても）本体文字列の長さよりは鈍い増加になると思われる。
（語彙数は延べ語数よりも増加が遅い）

が、いまのところ、本体文字列は小さめでやっているので、
1) の方が 2), 3) よりも大きくなっている。

本体文字列を大きくした場合、1) の計算時間は 2) よりも小さくなるはずだが、絶対量に減る訳ではないので、とりあえず 1) に関する高速化を行う。
（なお、Suffix Tree, Suffix Vector を用いた高速化は、2), 3) の部分の高速化）

まず、データとして、
単語 2-gram をキーとし、それを連結した場合のコーパス長変化分を値としてもつハッシュを用意する。
このハッシュを連結に際して更新の必要な部分のみ、更新していく。

ループの最後に、

4) コーパス長変化分の更新
foreach [ 連結候補 <- 連結により記述長に影響を受ける2-gram ] {
4.1) 連結した場合のコーパス長変化分の再計算：
...
}

を加え、

foreach [ 連結候補 <- 単語 2-gramのすべての種類 ] {
1.1) 連結した場合の記述長変化分の計算：
...
}

を、

foreach [ 連結候補 <- 単語 2-gramのすべての種類 ] {
1.1) 連結した場合の辞書長変化分の再計算：
... ~~~~
}

にする。

「影響を受ける2-gram」は、連結される出現に付近２単語以内に現れる単語を少なくとも１つ含む 2-gram。
これは 2) か 3) の走査のときに同時に調べておける。

これにより 1) は単語 1-gram の種類数に比例する計算時間で済み、
4) も、影響を受ける候補の数がだいたい連結される 2-gram の出現頻度 x 単語 1-gram の種類数程度なので、
連結の頻度 x 単語 1-gram の種類数の2乗程度になる。

影響を受ける2-gram は全2-gramに含まれるので、コーパス長計算回数の絶対数は、確実に減る。

計算時間の改善の見通しとしては、よくて、10分の1に抑えられる、くらいか？

結局、1.1)、4.1) が定数時間でできなくなったということが痛い。
定式化をいまいちど見直して、

あと、他の高速化ポイントとしては、
3) の頻度情報の更新は全部操作しなくてもできる、というところがある。

2) に関しては、任意の2-gramから、その全ての出現を引けるハッシュを持っておけば、
全部走査しなくてもできるが…