トリプル配列法

トリプル配列法とは、文字列の全件検索用のロジックである。

なお、全件検索とは、「文字列に出現する（あらゆる位置から始まる）部分文字列についてのすべてを辞書引きする」ことをいう。
全件検索用の辞書引きロジックとしては「ダブル配列用」のほうが有名であり、ネット検索ではこちらの方がヒットしやすい。実際には、トリプル配列法はダブル配列法よりも古くからあったが、メモリ容量が少なかったためにダブル配列法が考案されたと考えられる。

概要

データ構造としては、

1. 次項補参照ポインタ→（絶対参照でも相対参照でもよい）
2. ←参照元ポインタ（絶対参照でも相対参照でもよい。一バイトで済む）
3. データポインタ（ポインタでもハンドルでもよいが、null は「データがない」ことを示すのに使いたいので避けたほうがいい）

となっている。
アルゴリズムとしては、

1. まず、文字列をバイト列に変換する。
2. 当該文字句切りまで辞書引きが終わっているとして、次の 1 バイトのコードが n であったときに、インデクスが n だけ先の配列要素の参照元ポインタが、当該要素を指しているなら、その先に検索すべきデータがあるということになる。
3. その要素のデータポインタが null でなければ、そこにデータがある。

ということになる。
このとき、可変長文字列のデータは 256 分木になっているわけだが、文字列長が長くなるに従って要素の並びはスケスケになるため、その部分に他の要素を突っこむことによって記憶領域が節約できる。
欠点としては、データの追加・削除が厄介になること、スペースファクターを向上させようとするとうまく填まる場所を探す手間があること、したがって辞書データの作製に手間がかかることなどがある。

実装

やってみると、意外にコンパクトである。データポインタ部分は SRAM あたりに任せておけばよいので、キー文字列と実体としてのデータとの関係性が保たれていればよい。