ピーステーブル

コンピューティングにおいて、ピーステーブルは、テキストエディタで編集中のテキスト文書を表すために通常使用されるデータ構造です。最初に、元のファイル全体への参照（または「スパン」）が作成され、これはまだ変更されていないファイルを表します。その後の挿入と削除により、スパンは、元の文書のセクションまたは挿入されたテキストを保持するバッファへの1つ、2つ、または3つの参照の組み合わせに置き換えられます。^[1]

通常、元のドキュメントのテキストは 1 つの不変ブロックに保持され、後続の各挿入のテキストは新しい不変ブロックに格納されます。削除されたテキストもピース テーブルに含まれているため、ギャップバッファーなどの代替データ構造よりもピース テーブルを使用した方が、マルチレベルまたは無制限の取り消しを実装しやすくなります。

このデータ構造はJ・ストロザー・ムーアによって発明されました。^[2]

この説明では、コンテンツを保持するための不変ブロックとして バッファを使用します。

ピーステーブルは3つの列で構成されています: ^[1]

• どのバッファ
• バッファ内の開始インデックス
• バッファ内の長さ

テーブルに加えて、編集を処理するために 2 つのバッファーが使用されます。

• 「オリジナル バッファ」: 元のテキスト ドキュメントへのバッファ。このバッファは読み取り専用です。
• 「バッファを追加」: 一時ファイルへのバッファ。このバッファは追加専用です。

定義: : 位置 iIndex(i)の文字を返す

i番目の文字を取得するには、ピース テーブル内の適切なエントリを読み取ります。

次のバッファとピース テーブルがあるとします。

i番目の文字にアクセスするには、ピース テーブル内の適切なエントリが検索されます。

たとえば、 の値を取得するにはIndex(15)、ピース テーブルの 3 番目のエントリを取得します。これは、3 番目のエントリがインデックス 11 から 16 までの文字を記述するためです (最初のエントリはインデックス 0 から 5 までの文字を記述し、次のエントリは 6 から 10 までの文字を記述します)。ピース テーブル エントリは、プログラムに、そのバッファーのインデックス 17 から始まる " add file " バッファー内の文字を検索するように指示します。そのエントリの相対インデックスは 15-11 = 4 であり、これがバッファー内のエントリの開始位置に追加されて、文字のインデックスが取得されます: 4+17 = 21。 の値は、Index(15)"add file" バッファーの 21 番目の文字、つまり文字 "o" です。

上記のバッファーとピース テーブルについては、次のテキストが表示されます。

Lorem ipsum dolor sit amet

テキストに文字を挿入するには、次の手順に従います。

• 「ファイル追加」バッファに文字を追加し、
• ピーステーブルのエントリを更新する（エントリを 2 つまたは 3 つに分割する）

単一文字の削除は、次の 2 つの条件のいずれかになります。

• 削除はピース エントリの先頭または末尾で行われ、その場合、ピース テーブル内の適切なエントリが変更されます。
• 削除がピースエントリの途中で行われた場合、エントリは分割され、後続エントリの 1 つが上記のように変更されます。

Bravo ^[1]、Abiword ^[3]、^{[4] [5]、}Atom ^[6]、Visual Studio Code ^[7]など、いくつかのテキストエディタは内部的にRAM内ピーステーブルを使用しています。

Microsoft Wordの一部のバージョンの「高速保存」機能は、ディスク上のファイル形式にピーステーブルを使用します。^[2]

Oberonシステムのテキストファイルのディスク上の表現では、トランスクルージョンと同様に、1つの文書の断片が他の文書に格納されているテキストを指すことを可能にするピースチェーン技術が使用されています。 ^[8]

• ロープ（コンピュータサイエンス）
• ギャップバッファは、テキストエディタでよく使用されるデータ構造で、同じ場所の近くに集められた効率的な挿入および削除操作を可能にします。
• Enfilade、Model-T Enfilade は、ツリーベース実装のピース テーブルです。