Programming

텍스트 편집기의 데이터 구조? (feat. Gap Buffer, Piece Tree)

텍스트 편집기 구현에 주로 사용되는 자료구조들에 대한 간단한 정리

주재현

• 6 min read
텍스트 편집기의 데이터 구조? (feat. Gap Buffer, Piece Tree)
Photo by Kelly Sikkema / Unsplash

최근 이 내용을 보게 되었고
텍스트 편집기 데이터 구조에 대해 최대한 간단하게만 번역, 정리..?를 해봤다.

배열

배열은 가장 간단하지만 비효율적인 방법이다.

단점

  1. 전체 파일을 배열에 로드해야함.
    • 시간, 메모리 문제
  2. 삽입, 삭제 시 각 요소를 이동해야 함.

로프(Rope)

로프라고 불리는 이진 트리 구조

동작 과정

문자열은 계속 두 섹션으로 나뉘어진다.

leaf node 는 자신의 문자열 길이를 weight로 가지고
나미지 non-leaf node는 왼쪽 서브 트리의 문자열 길이를 가진다.

rope는 배열보다 효율적인데

  • Split
  • Concat
    이 두 연산을 가진다.

문자 삽입시 삽입하고 싶은 위치를 기준으로 문자열을 분할,
삽입된 문자열 앞뒤로 연결하는 방식으로 작동한다.

삭제는 삭제할 문자열 앞뒤로 분할하고 연결한다.

단점

  • 사용하기 헷갈리고 어려움.
  • 설명하기 어렵다.
  • 코드의 유지보수가 어려움
  • 아직 많은 메모리를 사용함

갭 버퍼(Gap buffer)

동일한 위치 근처에 클러스터링된 효율적인 삽입 및 삭제 작업을 허용 하는 동적 배열

Gap buffer는 Rope 보다 훨씬 간단하다.
Gap buffer는 구현이 매우 간단하고 Emacs가 사용하는 것으로 유명하다.

동작 과정

  • 배열에 저장된 문자 사이 간격을 만든다.
  • 포인터나 인덱스를 이용해 간격을 측정한다.
_는 Gap, (V)는 커서
[(V)_, _, _, _, _, _, _, _, _, _]

커서를 기준으로 연산을 수행함

새로운 문자열 삽입시

[(v)H, i, _, _, _, _, _, _, _, _]

이런식으로
이때 커서는 움직이지 않고 커서 기준으로 삽입했으므로 O(1)의 시간이 걸림

만약 커서를 뒤로 이동해 삭제, 삽입을 진행한다면

[H, (v)_, _, _, _, _, _, _, _, _]

커서를 이동한 만큼 O(N), 삽입 또는 삭제 에 O(1)이 소요된다.

단점

빠른 텍스트 편집기인 Emacs에서 사용하는 만큼 좋지만

  • 다중 커서 편집에 최적화되어 있지 않다.
  • undo/redo가 비효율적이다.

등이 단점으로 있다.

Piece Table

Piece Table은 텍스트 편집기에서 일반적으로 사용되는 데이터 구조다.

Traditional piece table

설명

  • 처음 원본 파일 전체에 대한 참조 생성
  • 삽입, 삭제는 원본 문서의 섹션 또는 삽입된 문자열을 가진 버퍼의 조합으로 대체한다.

일반적으로 원본 텍스트는 변경 불가능한 하나의 블럭에 저장된다.
이후 삽입되는 텍스트는 변경 불가능한 새 블록에 저장된다.

  • 이로 멀티 레벨, 무제한 되돌리기 구현이 쉬워짐

버퍼를 변경 불가능한 블럭으로 사용함

조각 테이블은 세 개의 열로 구성

  • 어떤 버퍼인지
  • 버퍼의 시작 인덱스
  • 버퍼의 길이

단점

  • Piece Table이 더 큰 배열에 저장되어 느려질 수 있음
  • 되돌리기는 결국 더 많은 공간을 차지하게 됨

Piece Tree

Vscode에서 Piece Table을 기반으로 발전시킨 자료구조이다.

해당 Vscode 블로그에서는 이를 아래와 같이 표현한다.

"Multiple buffer piece table with red-black tree, optimized for line model"
"라인 모델에 최적화된 RB tree를 사용하는 다중 버퍼 조각 테이블"

동작 과정

기존 Piece Table에서 추가된 내용들은

우선 기존 piece table의 간단한 데이터 구조는

class PieceTable {
  original: string; // original contents
  added: string; // user added contents
  nodes: Node[];
}

class Node {
  type: NodeType;
  start: number;
  length: number;
}

enum NodeType {
  Original,
  Added
}

빠른 조회를 위해 캐시 사용

기존 Piece Table의 노드에 lineStarts 를 넣어 줄바꿈이 몇개 있는지 파악

class PieceTable {
  original: string;
  added: string;
  nodes: Node[];
}

class Node {
  type: NodeType;
  start: number;
  length: number;
  lineStarts: number[];
}

enum NodeType {
  Original,
  Added
}

문자열 연결 함정을 피하자

piece table은 두개의 버퍼를 들고 있다

  • 원본
  • 수정용

근데 큰 파일을 받아오는 과정에서

이를

  • 버퍼 리스트
    로 대체
class PieceTable {
  buffers: string[];
  nodes: Node[];
}

class Node {
  bufferIndex: number;
  start: number; // start offset in buffers[bufferIndex]
  length: number;
  lineStarts: number[];
}

RB tree를 사용해 조회 성능 향상

위 방법을 이용해 대용량 파일을 받아오는데 성공
하지만 줄 바꿈 위치를 캐시해도 내용을 얻으려면 전체 탐색이 필요함

이진트리를 사용해 성능 향상

class PieceTable {
  buffers: string[];
  rootNode: Node;
}

class Node {
  bufferIndex: number;
  start: number;
  length: number;
  lineStarts: number[];

  left_subtree_length: number;
  left_subtree_lfcnt: number;
  left: Node;
  right: Node;
  parent: Node;
}

객체 할당 줄이기

  • 해당 버퍼에 대한 줄 바꿈 오프셋 가지기
    BufferPosition을 타입으로
    start, end를 추가로 가지게 한다.
class Buffer {
    value: string;
    lineStarts: number[];
}

class BufferPosition {
    index: number; // index in Buffer.lineStarts
    remainder: number;
}

class PieceTable {
    buffers: Buffer[];
    rootNode: Node;
}

class Node {
    bufferIndex: number;
    start: BufferPosition;
    end: BufferPosition;
    ...
}

조각 나무

결론

텍스트 편집기 구현에 주로 사용되는 데이터 타입들에 대해서 알아봤는데

확실히 Piece Tree나 Piece Table이 성능 면에서는 좋아보인다.

다만 가장 빠르다고 알려진 Emacs 와 같이 Gap Buffer도 사용하기 때문에
텍스트 편집기의 목적?에 따라 선택해 사용하면 될것 같다.

Rope도 변형해서 많이 사용된다고 한다.

참고자료