feature image

2018年11月18日 | ブログ記事

Piece Table 【アドベントカレンダー2018 25日目】

この記事は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法の仕組みを図で見ていきましょう。
AdC2018-1
Piece Table法は上の図のように文字列を保持する2つのバッファ(Original File, Add File)とPiece TableというPieceというデータが入っている配列を用います。Original Fileは編集中のファイルのもともとの文字列が入っていて読み込み専用、Add Fileは挿入された文字を保持するバッファで書き足し専用です。PieceというのがPiece Table法の肝で、どちらのバッファの文字列を指すか、その文字列がバッファのどこから始まるのか、その文字列の長さはいくつかという3つの情報で、文字列を間接的に表現しています。このような構造では次のような特徴があります。

Piece Table法の動作例

このような仕組み・特徴を持つPiece Table法について、今度は文字列の消去や挿入の時にPiece Tableがどのような挙動をするのかを図で見ていきましょう。ここでは、初期の文字列を"Hello, world!"とし、それを次のように編集した時の例について考えてみます。

  1. "world"を消去("Hello, !")
  2. "traP"をカンマの後に挿入("Hello, traP!")

"Hello, world!"

AdC2018-2
まず初期状態の時のPiece Tableの状態についてみていきましょう。初期状態ではPiece Tableは上の図のようになっています。初期状態なので、Original Fileを指すPieceが一個だけある状況です。何も挿入していないのでAdd Fileが空で、Piece Table全体としても元の内容と同じです。

"Hello, !"

AdC2018-3
次に"world"を削除した後のPiece Tableの状態は上のようになります。Piece Tableでの削除の実装は、基本的にはPieceを削除すればいいのですが、削除したい範囲があるPieceの内側にあった場合はPieceを分割することで実現します。上の例では"Hello, "を指すPieceと"!"を指すPieceの2つに分かれていますね。

"Hello, traP!"

AdC2018-4
最後に"traP"を挿入した後のPiece Tableの状態です。Piece Tableでの挿入は、PieceとPieceの間に新しいPieceを挿入し、Add Fileに挿入した文字列を書き足すことで実現します。また削除と同様、挿入したい箇所があるPieceの示す範囲の内部にあった場合は、そのPieceを分割します。

Piece Tableがどのように動作するかイメージをつかめたでしょうか?

実装してみた

せっかくだからPiece Tableを実装してみようと思ったので、HaskellでPiece Tableを書きました。書いたコードはGithubに上がっています。Haskellを勉強中なので、コメントやアドバイスなどありましたらよろしくお願いします!!

終わりに

いかがでしたでしょうか?テキストエディタ用のデータ構造なんて面白いですよね。僕はアルゴリズムやデータ構造についてあまり詳しくないですが、いろいろ勉強してどんどん強くなっていきたいなと思います。

明日はreflecさん、mastech16さんの記事です。お楽しみに!!

参考文献

wasabi icon
この記事を書いた人
wasabi

東京工業大学 18 情報工学系所属. Haskell, React, Rust勉強中です.

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】 feature image
2018年11月3日
ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】
Azon icon Azon
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2018年12月23日
LogicProXでのサラウンド設定,オーケストラ用テンプレ作成,その他の小ネタ
SolunaEureka icon SolunaEureka
2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya icon eiya
2018年11月30日
Flutterでスマホアプリを作ってみ(た | よう)【アドベントカレンダー2018 37日目】
Fourmsushi icon Fourmsushi
2018年12月23日
線形解読法
nari icon nari
記事一覧 タグ一覧 Google アナリティクスについて