テキストエディタで使われがちなデータ構造 Piece Table の概要と実装


テキストエディタのデータ構造

テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。

多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。


Gap method

Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)をGap部分で吸収する構造です。

長いデータであっても、途中部分への追加はGap部分に対して行うことで、バッファ内のデータの移動(コピー)が発生しないようにするものです。

カーソルの移動に合わせてデータの移動を行う必要がありますが、多くの場合良好な性能を示し、またメモリ使用量も妥当なものとなるため、多く採用されているデータ構造だと思います。


Piece Table method

Piece Table は、元のファイルは読み取り専用とし、書き込みは別のバッファに対して行い、バッファ位置を Piece Table として管理する方法です。

VS Code では、1.21 リリースで、Piece table を改良した Piece tree と呼んでいるデータ構造が使われるようになりました。こちら Text Buffer Reimplementation で詳細を確認できます。

以降では、Piece Table のデータ構造について見ていき、簡単な実装例を紹介しようと思います。


Piece Table の構造

先程の説明の通り、read-only のバッファと、append-only のバッファを考えます。

Piece Table では、参照先のバッファと開始・終了のインデックスを保持します。

例えば、「span of 」という文字を8の位置に挿入したとします。すると、Piece Table は元の Piece を分割して、間に append-only のバッファへの参照を追加して以下のようになります。

続けて、「 large」を削除したとすると、最初のPieceを分割して以下のようになります。

現在のテキストは、Piece Table をたどって「a span of text」のようになります。

編集を続けると、Piece Table が肥大化することがありますが、元のファイルが大きい場合でも、read-only のためキャッシュとして扱えるなどの利点もあります。


Piece Table の実装

簡単なJava実装例を見てみましょう。

最初に read-only バッファと、append-only バッファのインターフェースを作ります。

public interface Buffer {
    int length();
    CharSequence subSequence(int start, int end);
    char charAt(int index);
}
public interface AppendBuffer extends Buffer {
    void append(CharSequence cs);
}

charAt で char を返していますが、Unicode 4.0 対応のJava5以降ではサロゲートペアの場合1文字を char では表現できない点に注意してください。

このバッファは、単純に StringBuffer で実装したり、RandomAccessFile を使い、メモリに読み込むことなく操作したりすることができます(ここでは省略します)。


Piece は以下のように分割処理を持たせて定義しておきましょう。

private record Piece(Buffer target, int index, int length) {

    public Pair<Piece> split(int offset) {
        return new Pair<>(
                new Piece(target, index, offset),
                new Piece(target, index + offset, length - offset));
    }

    public int end() { return index + length;  }
}

PieceTable は以下のような実装になります。

public class PieceTable {

    private final List<Piece> pieces;
    private final AppendBuffer buffer;

    private PieceTable(Buffer readBuffer) {
        this.pieces = new ArrayList<>();
        this.pieces.add(new Piece(readBuffer, 0, readBuffer.length()));
        this.buffer = AppendBuffer.of();
    }

    public static PieceTable of(CharSequence cs) {
        return new PieceTable(Buffer.of(cs));
    }
}


Piece Table のメソッド

PieceTable には、対象 Piece の場所を探す location() メソッドを定義しておきましょう。

    private record Location(int pieceIndex, int offset) {}

    private Location location(int pos) {
        var offset = 0;
        for (var i = 0; i < pieces.size(); i++) {
            var piece = pieces.get(i);
            offset += piece.length;
            if (pos < offset) {
                return new Location(i, piece.length - (offset - pos));
            }
            if (pos == offset) {
                return new Location(i + 1, 0);
            }
        }
        return new Location(pieces.size(), 0);
    }

これで、テキストのインデックス位置となる Piece の場所を得ることができます。


テキストの追加処理は以下のようになります。

    public void insert(int pos, CharSequence cs) {
        var newPiece = new Piece(buffer, buffer.length(), cs.length());
        buffer.append(cs);
        var loc = location(pos);
        if (loc.offset == 0) {
            pieces.add(loc.pieceIndex, newPiece);
        } else {
            var piece = pieces.get(loc.pieceIndex);
            var pair = piece.split(loc.offset);
            pieces.remove(piece);
            add(loc.pieceIndex, pair.right, newPiece, pair.left);
        }
    }

    private void add(int index, Piece... add) {
        if (Objects.isNull(add) || add.length == 0) {
            return;
        }
        Arrays.asList(add).forEach(e -> pieces.add(index, e));
    }

必要に応じて Piece を分割し、テキスト自体の追加はappend-only バッファに行います。

同様にテキストの削除処理です。

    public void delete(int pos, int len) {
        if (len <= 0) {
            return;
        }
        List<Piece> deleting = new ArrayList<>();
        var loc = location(pos);
        var del = -loc.offset;
        for (var i = loc.pieceIndex; i < pieces.size(); i++) {
            var piece = pieces.get(i);
            del += piece.length;
            deleting.add(piece);
            if (del >= len) {
                break;
            }
        }
        pieces.removeAll(deleting);
        if (del > len) {
            var edge = deleting.get(deleting.size() - 1);
            add(loc.pieceIndex, edge.split(edge.length - (del - len)).right);
        }
        if (loc.offset != 0) {
            var edge = deleting.get(0);
            add(loc.pieceIndex, edge.split(loc.offset).left);
        }
    }

Piece を削除し、Piece を跨ぐ場合には分割します。このときバッファには何の処理も行いません。


まとめ

テキストエディタのデータ構造で採用されることが多い Piece Table について紹介し、その実装例を示しました。

詳細は以下を参照してください。

github.com

実装例はあくまでも例示のためのものですが、コンパクトに実装できることが理解いただけるのではないかと思います。