Стол поштучный
В вычислительной технике таблица фрагментов представляет собой структуру данных , обычно используемую для представления текстового документа , редактируемого в текстовом редакторе . Первоначально создается ссылка (или «диапазон») на весь исходный файл, который представляет собой еще не измененный файл. Последующие вставки и удаления заменяют диапазон комбинациями одной, двух или трех ссылок на разделы исходного документа или на буфер, содержащий вставленный текст. [1]
Обычно текст исходного документа хранится в одном неизменяемом блоке, а текст каждой последующей вставки сохраняется в новых неизменяемых блоках. многоуровневой или неограниченной отмены Поскольку даже удаленный текст по-прежнему включен в таблицу фрагментов, это упрощает реализацию с помощью таблицы фрагментов, чем с помощью альтернативных структур данных, таких как буфер пробелов .
Эту структуру данных придумал Дж. Стротер Мур . [2]
Описание
[ редактировать ]В этом описании мы используем буфер в качестве неизменяемого блока для хранения содержимого.
Таблица деталей состоит из трех столбцов: [1]
- Какой буфер
- Начальный индекс в буфере
- Длина в буфере
Помимо таблицы, для обработки правок используются два буфера:
- « Исходный буфер »: буфер исходного текстового документа. Этот буфер доступен только для чтения.
- « Добавить буфер »: Буфер во временный файл. Этот буфер предназначен только для добавления.
Операции
[ редактировать ]Индекс
[ редактировать ]Определение:
Index(i): вернуть символ в позицию i
Чтобы получить i -й символ, считывается соответствующая запись в таблице фрагментов.
Пример
[ редактировать ]Учитывая следующие буферы и таблицу частей:
| Буфер | Содержание |
|---|---|
| Исходный файл | ipsum sit amet
|
| Добавить файл | Lorem deletedtext dolor
|
| Который | Начальный индекс | Длина |
|---|---|---|
| Добавлять | 0 | 6 |
| Оригинал | 0 | 5 |
| Добавлять | 17 | 6 |
| Оригинал | 5 | 9 |
Чтобы получить доступ к i -му символу, ищется соответствующая запись в таблице частей.
Например, чтобы получить значение Index(15), извлекается третья запись таблицы деталей. Это связано с тем, что третья запись описывает символы с индексом от 11 до 16 (первая запись описывает символы с индексом от 0 до 5, следующая — с индексом от 6 до 10). Запись в таблице частей предписывает программе искать символы в буфере « добавить файл », начиная с индекса 17 в этом буфере. Относительный индекс в этой записи равен 15-11 = 4, который добавляется к начальной позиции записи в буфере для получения индекса буквы: 4+17 = 21. Значение Index(15) — это 21-й символ буфера «добавить файл», который представляет собой символ «о».
Для буферов и таблицы деталей, приведенных выше, показан следующий текст:
Lorem ipsum dolor sit amet
Вставлять
[ редактировать ]Вставка символов в текст состоит из:
- Добавление символов в буфер «добавить файл» и
- Обновление записи в таблице штук (разбиение записи на две или три)
Удалить
[ редактировать ]Удаление одного символа может быть одним из двух возможных условий:
- Удаление происходит в начале или конце записи шт.; в этом случае соответствующая запись в таблице шт. изменяется.
- Удаление происходит в середине фрагмента записи; в этом случае запись разделяется, а затем одна из последующих записей изменяется, как указано выше.
Использование
[ редактировать ]Некоторые текстовые редакторы используют внутреннюю таблицу фрагментов в оперативной памяти, включая Bravo , [1] Абиворд , [3] [4] [5] Атом [6] и код Visual Studio . [7]
Функция «быстрого сохранения» в некоторых версиях Microsoft Word использует таблицу фрагментов для формата файла на диске. [2]
Представление текстовых файлов на диске в системе Оберон использует метод цепочки фрагментов , который позволяет частям одного документа указывать на текст, хранящийся в каком-то другом документе, аналогично включению . [8]
См. также
[ редактировать ]- Веревка (информатика)
- Буфер пробела — структура данных, обычно используемая в текстовых редакторах, которая позволяет эффективно выполнять операции вставки и удаления, сгруппированные в одном и том же месте.
- Enfilade , Model-T Enfilade — это таблица деталей с древовидной реализацией.
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б с Кроули, Чарльз (10 июня 1998 г.). «Структуры данных для текстовых последовательностей - 6.4 Метод таблицы частей» (PDF) . www.cs.unm.edu . Архивировано (PDF) из оригинала 23 февраля 2018 года . Проверено 26 июля 2021 г.
- ↑ Перейти обратно: Перейти обратно: а б Дэвид Лу. «Что было сделано с помощью Таблицы фигур?» . ( обсуждение )
- ^ «Разработка AbiWord: фон таблицы частей» .
- ^ Джеймс Браун. «Цепочки частей: проектирование и реализация текстового редактора Win32» .
- ^ Хоакин Куэнка Абела. «Улучшение таблицы частей AbiWord» .
- ^ натансобо (12 октября 2017 г.). «Новая реализация буфера Atom, дружественная к параллелизму» . Блог Атома . Проверено 26 июля 2021 г.
- ^ "Примечания к выпуску VS Code 1.21 ( исходный код )"
- ^ Никлаус Вирт, Юрг Гуткнехт. «Проект Оберон: разработка операционной системы и компилятора». Архивировано 12 апреля 2013 г. на Wayback Machine . 2005. п. 90.