----------------------------------------------------------------
  次の論文の抄訳である. Brentは, かの有名なBrent.
    R. P. Brent, A Linear Algorithm for Data Compression,
    The Australian Computer Journal, Vol. 19, No. 2, May 1987.

  一部 \TeX\ の記法を使った. $  $ で囲んだ部分は数式用イタリック
フォントになる. \ldots は点々々 (...) を表す. a_j とか a_{j+1}
とかは, それぞれ j, j+1 が下つき添字であることを表す. 上つき添字
は a^2 のように表す. \delta はδである.
----------------------------------------------------------------
  2パスからなる. 1パス目はスライド辞書, 2パス目はハフマンである.

  1パス目:

  入力バッファには長さ $n$ の文字列 $s_1 \ldots s_n$ が入っており,
$s_1 \ldots s_j$ の処理が終わった状態であるとする. ハッシュ表 $H$
を使う. ハッシュ用のキーは $s_k \ldots s_{k+m-1}$ の形の文字列で,
これを対 $(k, m)$ の形で表す. はじめは $H$ は空, $j = 0$ である.

  バッファの中から $s_{j+1} s_{j+2} \ldots$ に一致する最大長の
文字列を見つけるには次のようにする.

    m = 2;  m' = 0;
    do {
        H から s_{j+1}...s_{j+m} を探す;
        if (見つかった) match = TRUE
        else            match = FALSE;
        if (match) {
            H 中の一致した項目の (位置, 長さ) を (k, m) とする;
            /* 現在までの最善の一致を保存する */
            k' = k;  m' = m;
            H の一致項目の表現を (j+1, m) で置き換える; % k = j+1 の意? %
            if (k + m <= n)
                s_k...s_{k+m} を H に登録する (現在の一致項目に上書き);
            m++;
        } else
            s_{j+1}...s_{j+m} を H に登録する;
    } while (match && j + m <= n);
    /* j + m > n ならすべての入力を処理したことになる. */
    if (m' >= 2) {
        output(j - k', m');
        if (j + m' < n) {
            /* 最大一致文字列の部分列を H に登録 */
            for (j' = j + m'; j' >= j + 2; j--) {
                H から s_{j'}...s_{j+m'+1} を探す;
                if (見つかった)
                    /* その表現を (k'', m'') とすると */
                    表現を (j', m'') で置き換える;
                else
                    s_{j'}...s_{j+m'+1} を H に登録する;
            }
        }
        j += m';
    } else {
        output(s_{j+1});
        j++;
    }

  これを $j < n$ である間続ける.

  ハッシュ関数については, 上のアルゴリズムの前半では $h(s_{j+1}s_{j+2})$,
$h(s_{j+1}s_{j+2}s_{j+3})$, \ldots, $h(s_{j+1}s_{j+2}s_{j+m})$ という
具合に文字列を後ろから延ばしていきながらハッシュ関数を計算しなければ
ならない. これを効率よく行うためには, 文字列を単に256進数と見て, その
値を適当な奇数で割った余りをハッシュ値として使えばよい. こうすれば

\[  h(Ks) = 256h(K) + s \bmod p  \]  %%% 注: \bmod は2項演算の mod のこと %%%

という漸化式で計算できる. アルゴリズムの後半では逆に文字列を前から
延ばしながらハッシュ関数を求めなければならないが, これも同様な漸化式
で求められる.

  $s_1 \ldots s_j$ を処理した段階で, $H$ にはたかだか $2j$ 個の項目
が登録される.

  実際には上のアルゴリズムのバッファは環状にする (スライド辞書).
その大きさを $B$, 最大一致長を $M$ とすると, $O(B + M)$ の程度の
スペースでできる. ハッシュ表の項目が古くなってスライド辞書から
外れてしまってもすぐに削除する必要はない. 検索時に, もし古くなった
項目を検索してしまったら, その都度削除すればよい. それでも項目が
足りなくなったら, ガーベジ・コレクションをする.

  最大一致長 $M < 256$, スライド辞書サイズ $B < 2^{18}$ (つまり256K)
として, 1パス目の出力は9ビット単位で行う. 文字をそのまま送り出す
ときは, 8ビットの先頭に0をつけて9ビットにして送り出す. 一致長 $m$,
一致位置 $\delta$ を送り出すには, 一致位置は9ビットごとに $\delta_1$,
$\delta_2$ と分けて, 9ビットの3個分 $(256+m, \delta_1, \delta_2)$
の形で送り出す. この9ビットのアルファベットに対して, 2パス目で
静的ハフマン法でさらに圧縮する. 1パス目で頻度を計数しておき, 2パス目
に入る前にそれを 0 以上 255 以下に規格化し, これも一緒に出力しなけれ
ばならない.  %%% このあたりはわれわれの方法の方が良い! %%%

  さらに, 一致長 $m = 2$ または3, あるいは一致位置のオフセット
$\delta$ が小さい値なら別のエンコード法を用いるなどの改善ができる.
また, $\delta$ を $delta_1$, $\delta_2$ に分ける方法も最適化できる.

  このアルゴリズム SLH %%% 何の略なんだろう? %%%
を8MHz 80286のCOMPAQで, Turbo Pascal でコーディングし, 非常に良い
パフォーマンスを得た. スライド辞書サイズ $B$ は17000程度としたが,
4000程度でも圧縮比が数％悪くなる程度である.