- http://ned.rubyforge.org/doc/crowley98data.ps.gz
- 他に面白いリンクがここに一杯ある。 http://ned.rubyforge.org/
結論
テキストエディタのデータ構造としては、piece table method が一番良い。
感想
今更テキストエディタを自分で作りたいという変わった人は読んだ方が良いです。この論文では、テキストをメモリやディスクでどのように保持するかという問題を、挿入、削除、位置特定の速度という観点から調べています。
- 位置特定とは、文を前から数えてどの位置にどの文字があるか調べるという問題ですが、ある位置を調べた後、次に調べたくなるのは前回調べた位置のすぐそばである可能性が高いという前提に立っています。
- 表示、例えばテキスト回り込みやプロポーショナルフォントの問題には触れていません。
- UTF-8 のような可変長エンコーディングについては触れていません。
用語
- buffer : 作業用メモリ又はディスク
- span : 物理的に並んだ文字列。
- descriptor : buffer 上の文字の位置を示すポインタ。
- sequence : 文字又は descriptor が並んだもの
データ構造 (5 章)
ここは自分用メモに書いてるだけなので、興味がある人は論文の図を見る事をお勧めします。
一つの sequence だけ使う構造
- array method : ちょっと大きめの buffer を取って、その中に文全体を入れます。挿入や削除の際は、編集位置以下のメモリをざっくり移動します。位置特定は一番速いですが、編集は滅茶苦茶遅いです。
- gap method : ちょっと大き目の buffer を取って、その中に文全体を入れます。挿入の際は、編集位置以降をざっくり buffer の後ろの方にずらして隙間を作ります。一旦隙間が出来ると、隙間が埋まるまで文字を挿入出来ます。削除の際は、削除部分を隙間にします。編集は同じ位置で行われる事が多いので、大変効率的です。一つの文に対して隙間は一つだけです。
- linked list method : 文を文字のリンクリストで表現します。挿入と削除は一番早いです。
二段 sequence を使う構造
- line span method : 一行ごとに一つの span を作成し、行ごとの descriptor を集めて文全体の sequence を作ります。編集ごとに新しいメモリを確保して、更新のあった行を保存し、descriptor を変更します。
- fixed size buffers : 行の代わりに都合の良い固定長 span を作成します。span 内の編集は array method や gap method を使い、溢れたり短くなると span の数を調整します。
- piece method : 最初一つの span から始まって、編集単位ごとに新しい span を追記して行きます。descriptor には、span の位置と文字数が記録されています。挿入は span を二つに割って、挿入文字列と後ろの文字列を足して新しい span を作ります。前の文字列は挿入点まで descriptor の文字数を小さくします。削除も同じようにします。出来た隙間は特に再利用せずに、無限 UNDO 用にとっておきます。
