テキストエディタ用行管理情報の局所的更新手法

Nobuhide Tsuda

03-Nov-2011

背景

• シーケンス（１次元的に並んだ）データを管理するデータ構造としては、「配列」「双方向リスト」の２つが一般的である。
• これらは相補的な特徴を持つ。
• すなわち、配列は、ランダムアクセスが O(1) であるが、挿入・削除といった編集処理が O(N) である。
• 双方向リストは、編集処理は O(1) であるが、ランダムアクセスは O(N) である。
• 一般的に許容出来るのは O(log N) までであり、配列・双方向リストともに、シーケンスデータ用データ構造としては問題がある。

• テキストエディタは文字のシーケンスデータを取り扱うものであり、ランダムアクセスと編集処理が高速である必要がある。
• テキストエディタのデータ構造として、「配列」または「双方向リスト」をそのまま用いるのは、上記の点で好ましくない。

• ひとつの解決方法として、改行で区切られる１行を動的配列で管理し、行を双方向リストで管理するというものがある。

      ┌───┐
      │      │
      │  ┌─┴─┐      ┌────────┐
      │  │      │──→│行テキストデータ│
      │  └─┬─┘      └────────┘
      │      │
      │  ┌─┴─┐      ┌────────┐
      │  │      │──→│行テキストデータ│
      │  └─┬─┘      └────────┘
      │      │
      │  ┌─┴─┐      ┌────────┐
      │  │      │──→│行テキストデータ│
      │  └─┬─┘      └────────┘
      ：      ：
      ：      ：
      │  ┌─┴─┐      ┌────────┐
      │  │      │──→│行テキストデータ│
      │  └─┬─┘      └────────┘
      │      │
      └───┘
  

• この方法は、各行が極端に長くなければ、編集処理はほぼ O(1) となる。
• 「Software Tools」 （訳本） で紹介され、また、初期の vi のデータ構造であり、この方法を採用したテキストエディタはかなり多いらしい。
• ViVi version 1.x もこのデータ構造を（改良したものを）採用している。
• 欠点としては、行長が極端に大きい行があると、編集処理は O(N) になり、パフォーマンスが極端に落ちる。
• また、行のランダムアクセスは出来ない（ViVi 1.x では行番号キャッシュ法により対応している）。
• ラインエディタであれば、行のランダムアクセスの高速性は必要性は無いのだが、GUI エディタで垂直スクロールを行うと、 ランダムアクセスに近い状態となり、行数がかなり多い場合は応答性が悪くなるという問題がある。
• さらに、行テキストのために std::string などの既存のクラスを用いると、行数が極端に多い場合、 小領域メモリが大量に作られ、バッファオブジェクトを解放するのにかなりの時間を要する（数10秒を要することもある）。

• もうひとつの解決方法として「ギャップ バッファ」というものがある。
• ギャップバッファとは、動的な配列で、編集箇所を境にテキストデータをバッファの先頭と末尾に詰めたものである。

  

• 編集箇所が局所的な場合、編集処理は O(1) となる。そして、テキストエディタの編集箇所は充分に局所化されている。
• ちなみに、初期の Emacs は、このギャップバッファを採用している。
• ギャップバッファはパフォーマンスが驚くほど良いのだが、行に関する情報を持っていないので、別途行情報の管理が必要となる。
  何故なら、通常のテキストエディタはテキストを行単位で表示するからだ。

• ギャップバッファの行管理をする最も単純な方法は、各行の先頭位置を動的配列で管理するものである。
• この方法では、行番号からバッファ内位置の変換は O(1)、バッファ内位置から行番号への変換は O(log L) で済む（L は行数）。
• 行数が増減した場合の処理は、行数を L とすれば、O(L) なのだが、配列ではなくギャップバッファと同様の方式にすれば、O(1) となる。
• 問題は、編集によりテキストが増減した場合で、編集行以降のバッファ内位置を修正する必要があり、その処理は O(L) となってしまう。
  

• 編集時の行情報更新処理を高速化するための方法として、各行の先頭位置を配列で持つのではなく、各行の長さを配列で持つ方法がある。
• この方法であれば、編集時の行情報更新処理は O(1) となる。
• しかしながら、行番号からバッファ内位置の変換、およびその逆の変換は O(L) となり、許容出来るものではない。
  
• キャッシュを利用することで、変換位置が局所化されていれば、処理時間を O(1) にすることができる （ViVi 5.0 で採用）。
• しかし、行数が極端に多い場合に、垂直スクロールを行うと、若干反応が遅くなる気がする。

• ギャップバッファ類を使用せず、行テキストへのポインタ・行長を行情報として保持する方法もある。
• これは、編集処理が行われなければ問題がないのだが、編集処理が行われるとメモリの断片化を引き起こすので、 いろいろやっかいである。

提案手法

• 前節で述べた問題を解決するために、行情報配列にバッファ内位置を保持し、 編集が行われた場合は、最後の編集行以降のバッファ内位置を更新せず、差分値を保持する、という手法を提案する。
  

  ※ この手法がオリジナルかどうかは調査していない。単純な方法なので、たぶん誰かが既に考えて実装してると推測される。

• たとえば、"12\n34\n56\n78\n" というテキストがあった場合、行情報は [0, 3, 6, 9, 12] [0, 0]と表現される。
• 最初の [0. 3, 6, 9, 12] が実際の配列内の値である。
• 行数は4行しかないのに値が５つあるのは、行長の計算を単純化するためである。
  行情報配列を lines[] とすれば、ix (0..*) 番目の行の長さは lines[ix + 1] - lines[ix] で簡単に計算できる。
  逆に言えば、最初の値は常に「0」なので、これも冗長と言えば冗長だが、行長計算を単純化するために残している。
  一種の番人である。
• [0, 0] は編集行・差分値である。差分値が「0」の場合、編集行は意味を持たないので何であってもよい。
• 2行目（"34\n"の行）に改行以外の文字を3文字挿入すると、行情報は [0, 3, 6, 9, 12] [1, 3] となる。
• 変化したのは、編集行・差分値のみである。
• 内部データは [0, 3, 6, 9, 12] のままであるが、２行目が編集行なので、３行目以上の行の位置を計算する場合は、 差分の「3」を加える。従って、外部から見た場合は [0, 3, 9, 12, 15] となる。
• さらに３行目に改行以外の文字を１文字挿入すると、[0, 3, 9, 9, 12] [2, 4] となる。
• 今回は配列の３行目の値が「6」から「9」に変化している。
• このように、直前の編集行と今回の編集行が異なる場合は、行番号の差分だけの配列要素の更新が必要となる。
• しかし、テキストエディタの場合、編集箇所は局所化されているという原理があるので、この処理はほぼ O(1) となる。
• 本手法により、行番号からバッファ内位置の変換処理を O(1)、逆の変換を O(log L) に保ったまま、 編集時の処理を O(1) にすることが出来る。

実装

• 内部的な行情報を、動的配列 lines[] : size_t で管理する。
• lines[] の要素数は実際の行数 + 1 とし、各行の先頭文字のバッファ内位置（size_t）を保持する。
• lines[] の最後の要素は、バッファサイズを値として保持する。
• 最終編集行は editLine : size_t で表す（0 オリジン）。初期値は任意。
• 最終編集行以降の差分は diff : diffptr_t で表す。初期値は 0 である。
• ix (0..*) 番目の行の位置は、以下の計算式で与えられる。

  　　　　lines[ix] + (ix > editLine ? diff : 0)

• ix (0 オリジン) 行が d だけ変化した場合の、行情報更新処理アルゴリズムは以下のように記述できる。

   1: void update(size_t ix, diffptr_t d)
   2: {
   3:     if( !diff ) {     //  差分が 0 の場合
   4:         editLine = ix;
   5:     } else if( ix < editLine ) {        //  編集行以前を編集した場合
   6:         while( editLine > ix ) {
   7:             lines[editLine--] -= diff;
   8:         }
   9:     } else if( ix > editLine ) {        //  編集行以降を編集した場合
  10:         do {
  11:             lines[++editLine] += diff;
  12:         } while( ix > editLine );
  13:     }
  14:     diff += d;
  15: }
  

パフォーマンス計測

• テキストエディタ用バッファの総合的なパフォーマンス評価としては、全置換処理に要する時間を計測するのが最もよい。
• 何故なら、全置換処理は、テキストエディタにとって最も頻繁にコールされる、バッファ内テキストのシーケンシャルアクセス、 削除、置換処理を含んでいるからである。
• 比較のために、提案手法による実装、gap_vector<uchar>, gap_vector<std::string> の３つについて計測する。
• 比較対象は undo/redo 機能を持たないので提案手法によるものも undo/redo 機能を実装しないもので比較する。

• ("abc1234567" * 10 + "\n") * 10万行（合計：1.01*10^7バイト）に対して削除などの処理を行い、処理に要した時間を計測した。
• 削除：3文字削除し、7文字進める。改行はスキップ。100万箇所、300万バイトを削除
• 挿入：2文字削除し、10文字進める。改行はスキップ。100万箇所、200万バイトを削除
• 置換：3文字を5文字に置換し、7文字進める。改行はスキップ。100万箇所、300万バイトを削除・500万バイトを挿入
• 検索・置換："123" を検索し、"xyzzz" に置換。100万箇所、300万バイトを削除・500万バイトを挿入
• ※ 計測環境：Core i5 670 @3.47GHz 3.46GHz、4GB RAM, VC9, Win7 x64
• 計測結果は下表のとおり（単位：秒）：

  	提案手法	gap_vector<char>	gap_vector<string>
  削除	0.106	0.023	0.108
  挿入	0.109	0.092	0.335
  置換	0.160	0.101	0.322
  検索＆置換	0.250	0.185	0.346

• 提案手法は gap_vector<char> を内包しているので、（提案手法）-（gap_vector<char>）が行管理処理に費やしている時間となる。
• gap_vector<string> は削除とそれ以外で約3倍もの処理時間差がある。これはバッファ領域を再アロケート＆コピーを行っているためである。

考察・結論

• 本手法は非常にシンプルである。
• 既に差分情報がある場合、直前の編集行とは異なる行を編集した場合は、その間の内部行情報配列要素を更新する必要があるが、 テキストエディタでは編集箇所は局所化されているという特性があるためん、ほとんどの場合更新が必要な要素数は少なく、 処理時間はほぼ O(1) となる。

• バッファの先頭付近が編集され、ついでバッファの末尾付近が編集された場合は、行情報のほとんどの要素が更新される。
  これは一見問題のようだが、そのような場合は、ギャップベクタでデータの大量移動が行われており、 そちらの処理時間の方が支配的になる。
• 元々の前提である「編集操作は局所的である」が崩れた状況であるので、処理時間を要するのは当然であり、問題視しない。
• 末尾付近（末尾から数百行程度？）での編集の場合、その行以降の行情報を直接更新しても、 処理時間は無視できる程度であるから、その場合は編集行・差分値を更新しない、という改良も考えられる。