WikiDer > Штучный стол

Piece table

А штучный стол это структура данных обычно используется для представления серии правки на Текстовый документ. Создается начальная ссылка (или "диапазон") на весь исходный файл, а последующие вставки и удаления создаются как комбинации одной, двух или трех ссылок на разделы исходного документа или диапазонов, связанных с более ранними. вставки.[1]

Обычно текст исходного документа хранится в одном неизменный block, а текст каждой последующей вставки сохраняется в новых неизменяемых блоках. Поскольку даже удаленный текст по-прежнему включается в таблицу элементов, это делает многоуровневым или неограниченным отменить проще реализовать с таблицей элементов, чем с альтернативными структурами данных, такими как буфер промежутка.

Эта структура данных была изобретена Дж. Стротер Мур.[2]

Описание

Для этого описания мы используем буфер как неизменяемый блок для хранения содержимого.

Штучная таблица состоит из трех столбцов:[1]

  • Какой буфер
  • Начальный индекс в буфере
  • Длина в буфере

Помимо таблицы, для обработки правок используются два буфера:

  • "Исходный буфер": Буфер исходного текстового документа. Этот буфер доступен только для чтения.
  • "Добавить буфер": Буфер временного файла. Этот буфер предназначен только для добавления.

Операции

Индекс

Определение: Индекс (i): вернуть символ в позиции я

Чтобы получить я-й символ, считывается соответствующая запись в таблице штук.

Пример

Учитывая следующие буферы и таблицу штук:

БуферСодержание
Исходный файлipsum sit amet
Добавить файлLorem удален текст dolor
Штучный стол
КоторыйНачальный индексДлина
Добавлять06
Оригинал06
Добавлять185
Оригинал69

Чтобы получить доступ к я-го символа ищется соответствующая запись в таблице штук.

Например, чтобы получить значение Индекс (15), извлекается третья запись таблицы штук. Это связано с тем, что третья запись описывает символы от 12 до 16 (первая запись описывает символы от 0 до 5, следующая - от 6 до 11). Запись в таблице штук указывает программе искать символы в "добавить файл"буфер, начиная с индекса 18 в этом буфере. Относительный индекс в этой записи 15-12 = 3, который добавляется к начальной позиции записи в буфере, чтобы получить индекс буквы: 3 + 18 = 21. Значение Индекс (15) это 21-й символ буфера «добавить файл», то есть символ «о».

Для приведенных выше буферов и таблицы элементов показан следующий текст:

Lorem ipsum dolor sit amet

Вставлять

Вставка символов в текст состоит из:

  • Добавление символов в буфер «добавить файл» и
  • Обновление записи в таблице штук (разбиение записи на две или три)

Удалить

Удаление включает только изменение соответствующей записи в таблице штук.

использование

Несколько текстовые редакторы использовать внутреннюю таблицу частей в ОЗУ, включая Браво,[1] Abiword,[3][4][5] Атом[6] и Код Visual Studio.[7]

Функция «быстрого сохранения» в некоторых версиях Microsoft Word использует таблицу элементов для формата файла на диске.[2]

Представление текстовых файлов на диске в Система Оберон использует цепочка метод, который позволяет частям одного документа указывать на текст, хранящийся в другом документе, аналогично включение.[8]

Смотрите также

Рекомендации

  1. ^ а б c Кроули, Чарльз (1998-06-10). «Структуры данных для текстовых последовательностей - 6.4 Метод таблицы элементов» (PDF). Архивировано из оригинал (PDF) на 2018-02-23. Цитировать журнал требует | журнал = (помощь)
  2. ^ а б Дэвид Лу."Что было сделано с использованием Таблицы предметов?".(обсуждение)
  3. ^ «Разработка AbiWord: фон таблицы элементов».
  4. ^ Джеймс Браун. "Цепочки компонентов: разработка и реализация текстового редактора Win32".
  5. ^ Хоакин Куэнка Абела.«Улучшение таблицы пьес AbiWord».
  6. ^ «Новая реализация буфера Atom с поддержкой параллелизма»
  7. ^ "Примечания к выпуску VS Code 1.21 (исходный код)
  8. ^ Никлаус Вирт, Юрг Гуткнехт.«Проект Оберон: Дизайн операционной системы и компилятора» В архиве 2013-04-12 в Wayback Machine.2005.p. 90.