Data Structure for Text Sequences

January 29, 2022

テキストエディタのためのデータ構造として、array, gap, list, line pointers, fixed size buffers, piece tablesを評価する。 とくに、Piece tablesを評価し詳しく解説する。 Piece tableはテキストを2つのバッファに記録する。 2つのバッファはfile buffer, add bufferで、file bufferは初期状態のテキストを保存し、add bufferは新たに挿入される文字列を保存する追記のみのバッファである。 名前のpieceはバッファ内の連続する部分文字列を意味する。 そして、pieceへのポインタのシーケンスがpiece tableである。 ポインタは、どちらのバッファか、参照する部分文字列の開始位置、長さの3つの情報からなる。

はじめは、ポインタがひとつしかなく、ポインタはfile bufferの全体を参照する。 削除は、ポインタを2つにわける。 ひとつは、先頭から削除された文字列より前までを参照する。 もうひとつは、削除された文字列の次の文字からファイルの最後までを参照する。 ただし、削除された文字列がファイルの先頭や最後であれば、一方のポインタはいらず、1つのポインタですむ。

挿入は、ポインタを3つにわける。 挿入された文字列をadd bufferに保存する。 はじめのpieceは、挿入された文字列の前の文字列を参照する。 2つめのpieceは、add bufferに保存された文字列を参照する。 3つめのpieceは、挿入された文字列の後の文字列を参照する。 先頭や最後に文字列を挿入したときは、削除とおなじである。

file bufferに変更はなく、add bufferは追記のみなので、キャッシュやundoを実装しやすい。 bufferをメモリ上にもたなければ、メモリ量は、テキストサイズではなく編集作業量による。 そのため、大きなテキストを効率的に処理できる。

論文をこちらからダウンロードできます。