この記事はtraP Advent Calender 2018 25日目の記事です。
こんにちは18のwasabiです。今日はPiece Tableについてです。
Piece Tableって何ぞや？
この世にはテキストファイルの内容を編集するためにテキストエディタというソフトウェアがあります。Windowsのメモ帳やSublime Text,Vim,Emacsなどがそれです。そんなテキストエディタでは、ファイルを編集する際に、ファイルの内容をバッファというものに読み出しそのバッファに対して編集を行います。テキストエディタでは文字列を効率的に保持・編集出来なければならないため、バッファには普通の文字の配列でなく、それ用のいい感じなデータ構造が用いられています。そのうちの一つがPiece Tableというデータ構造を用いたもので、この論文で"The piece table method"として紹介されています。VScodeでもそれをもとにしたものが使われているらしいです。
Piece Table法の仕組みと特徴
それではさっそくPiece Table法の仕組みを図で見ていきましょう。
Piece Table法は上の図のように文字列を保持する2つのバッファ(Original File, Add File)とPiece TableというPieceというデータが入っている配列を用います。Original Fileは編集中のファイルのもともとの文字列が入っていて読み込み専用、Add Fileは挿入された文字を保持するバッファで書き足し専用です。PieceというのがPiece Table法の肝で、どちらのバッファの文字列を指すか、その文字列がバッファのどこから始まるのか、その文字列の長さはいくつかという3つの情報で、文字列を間接的に表現しています。このような構造では次のような特徴があります。
- Original Fileは読み取り専用、つまり変更されることがないので、キャッシュの実装に有利になる。
- ファイルから内容を読んでPiece Tableを作るとき、Pieceは内容のサイズだけを知ることができればいいので、ファイルの事前処理がいらず高速な初期化を達成できる。
- コピーをするときに文字列ではなくPieceの情報を保持しておけばよく、ペーストはPiece TableにそのPieceを挿入すればよい。
Piece Table法の動作例
このような仕組み・特徴を持つPiece Table法について、今度は文字列の消去や挿入の時にPiece Tableがどのような挙動をするのかを図で見ていきましょう。ここでは、初期の文字列を"Hello, world!"とし、それを次のように編集した時の例について考えてみます。
- "world"を消去("Hello, !")
- "traP"をカンマの後に挿入("Hello, traP!")
"Hello, world!"
まず初期状態の時のPiece Tableの状態についてみていきましょう。初期状態ではPiece Tableは上の図のようになっています。初期状態なので、Original Fileを指すPieceが一個だけある状況です。何も挿入していないのでAdd Fileが空で、Piece Table全体としても元の内容と同じです。
"Hello, !"
次に"world"を削除した後のPiece Tableの状態は上のようになります。Piece Tableでの削除の実装は、基本的にはPieceを削除すればいいのですが、削除したい範囲があるPieceの内側にあった場合はPieceを分割することで実現します。上の例では"Hello, "を指すPieceと"!"を指すPieceの2つに分かれていますね。
"Hello, traP!"
最後に"traP"を挿入した後のPiece Tableの状態です。Piece Tableでの挿入は、PieceとPieceの間に新しいPieceを挿入し、Add Fileに挿入した文字列を書き足すことで実現します。また削除と同様、挿入したい箇所があるPieceの示す範囲の内部にあった場合は、そのPieceを分割します。
Piece Tableがどのように動作するかイメージをつかめたでしょうか？
実装してみた
せっかくだからPiece Tableを実装してみようと思ったので、HaskellでPiece Tableを書きました。書いたコードはGithubに上がっています。Haskellを勉強中なので、コメントやアドバイスなどありましたらよろしくお願いします！！
終わりに
いかがでしたでしょうか？テキストエディタ用のデータ構造なんて面白いですよね。僕はアルゴリズムやデータ構造についてあまり詳しくないですが、いろいろ勉強してどんどん強くなっていきたいなと思います。
明日はreflecさん、mastech16さんの記事です。お楽しみに！!
