ギャップバッファ

コンピュータサイエンスにおけるギャップバッファーとは、同じ場所の近くに集められた効率的な挿入および削除操作を可能にする動的配列です。ギャップ バッファーは、テキスト エディターで特によく使用されます。テキストへのほとんどの変更は、カーソルの現在の場所またはその近くで発生します。テキストは、2 つの連続したセグメントに分かれた大きなバッファーに格納され、その間に新しいテキストを挿入するためのギャップがあります。カーソルを移動すると、ギャップの片側からもう一方の側にテキストがコピーされます (テキストを変更する次の操作までコピーが遅延されることがあります)。挿入では、最初のセグメントの末尾に新しいテキストが追加され、削除ではそのテキストが削除されます。

ギャップ バッファ内のテキストは 2 つの文字列として表され、リンク リストなどのより洗練されたデータ構造に比べて、余分なスペースをほとんど必要とせず、検索や表示が非常に高速です。ただし、テキスト内の異なる場所での操作やギャップを埋める操作 (新しいギャップの作成が必要) では、テキストの大部分をコピーする必要がある場合があり、これは特に大きなファイルでは非効率的です。ギャップ バッファの使用は、このような再コピーはほとんど発生しないため、そのコストはより一般的な安価な操作で償却できるという仮定に基づいています。このため、ギャップ バッファは、 Emacs ^[1]などのテキスト エディタで使用するロープのよりシンプルな代替手段となります。^[2]

以下は、バッファ ギャップの操作例です。ギャップは、角括弧の間の空白で表されます。この表現は少し誤解を招きやすいものです。一般的な実装では、ギャップのエンドポイントはポインタまたは配列インデックスを使用して追跡され、ギャップの内容は無視されます。これにより、たとえば、バッファ内のテキストを変更せずにポインタを調整することで削除を行うことができます。

初期状態:

これが出口だ。

ユーザーが新しいテキストを挿入します:

これが世界が始まった方法です。

ユーザーはカーソルを「started」の前に移動します。システムは「started」を最初のバッファから 2 番目のバッファに移動します。

これが世界[ ]の始まり方です。

ユーザーがギャップを埋めるテキストを追加すると、システムが新しいギャップを作成します。

これが、私たちが知っている世界が始まった方法です。

• 動的配列、ギャップが常に末尾にあるギャップバッファの特殊なケース
• ジッパー（データ構造）。概念的にはギャップ バッファの一般化です。
• リンクリスト
• 循環バッファ
• ロープ（コンピュータサイエンス）
• ピーステーブル- Bravo と Microsoft Word で使用されるデータ構造

• Cでの実装
• .NET/C# での概要と実装
• 簡単な概要とサンプル C++ コード
• .NET/C# での巡回ソートギャップ バッファの実装
• 初期のエディタでのギャップ バッファの使用。(最初に書かれたのは 1969 年から 1971 年の間)
• emacs ギャップ バッファ情報 (Emacs ギャップ バッファ リファレンス)
• Flexichain: 編集可能なシーケンスとそのギャップバッファの実装
• テキスト対決: ギャップ バッファー vs ロープ