Текстовый редактор: структуры данных

  • Эта публикация - перевод статьи. Ее автор - Avery Laird. Оригинал доступен по ссылке ниже:

Первый шаг в создании текстового редактора - реализация основного API. Если вам интересно, почему я хочу это сделать, прочтите оригинальную статью здесь.

Я исследовал несколько типов данных, стараясь быть агностиком языка. Мне хотелось, чтобы мое решение не подвергалось влиянию какого-либо конкретного языка. Вначале я должен был удостовериться, что существует «лучший способ», основанный исключительно на операциях. Конечно, «лучший способ» существует в редких случаях. Тем не менее, в случае манипулирования текста и хранения есть некоторые четкие «худшие» и «лучшие способы».

Худший путь

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

К слову, это не челендж. Только не пытайтесь найти худшие способы манипулирования текстом.

Хороший путь

Другой вариант - двоичная древовидная структура, называемая веревкой. Перейдите к следующему разделу, если бинарные деревья - не ваше.

Если вы не знакомы с бинарными деревьями, используйте эту информацию как отправную точку.

В принципе, строка разделяется на разделы и сохраняется в листьях. Вес каждого листа - длина сегмента струны. Вес каждого нелистового узла - это общая длина строк в левом поддереве. Например, на диаграмме ниже узел представляет собой лист со струнным отрезком     6 символов. Следовательно, он имеет вес 6, как и его родительский узел. Однако у узла В - вес 9, поскольку узлы Е и F вместе имеют длину 9.

Источник: Википедия, https://en.wikipedia.org/wiki/Rope_(data_structure)

Этот метод намного эффективнее массива. Канат имеет две основные операции Split и Concat (конкатенацию). Split разбивает одну строку на две строки по заданному индексу и Concat объединяет две строки в одну. Вы можете предварительно вставить или удалить одну из двух основных операций. Чтобы вставлять символы, вы можете разделить строку один раз (там, где вы хотите вставить содержимое) и дважды объединить ее (по обе стороны от вставленного содержимого). Удаления работают аналогично, разбивая строку дважды и конкатенируя снова, не включая удаленный контент.

Имеется большой недостаток. Использование веревки довольно запутанно и сложно. Трудно объяснить даже абстрактно. Разработка изломов в реальной жизни кажется кошмаром. Более того, он все еще использует много места. Пока это не лучший вариант.

Лучший способ

Gap Buffer гораздо проще, чем веревка. Идея такова: операции с текстом часто локализованы. Большую часть времени мы не прыгаем по всему документу. Таким образом, мы создаем «пробел» между символами, хранящимися в массиве. Мы отслеживаем, насколько велика разница, используя указатели или индексы массивов. Рассмотрим два случая (с помощью указателей):

вставка
Разрыв - это определенный размер начала. Мы копируем по вставленному контенту, и если он превышает размер пробела, мы расширяем пробел.
делеция
Мы смещаем указатели на пробел, чтобы включить удаленный контент.

В этом есть большой смысл. Некоторые из нас страдают от тех же проблем, что и массив; при определенных обстоятельствах, если мы уйдем слишком далеко от разрыва, каждый элемент массива должен быть перемещен. Однако, скорее всего, это редкое явление для среднего пользователя. Вполне возможно, что скорость, получаемая при большинстве операций, перевешивает неэффективность некоторых краевых случаев. Фактически, редактор, который я пишу в Emacs, использует буфер пробелов, и это, вероятно, самый быстрый редактор, который я когда-либо использовал. Этот факт сам по себе является довольно убедительным аргументом в пользу использования буфера разрыва. Но если я начинаю с нуля, я хочу, чтобы каждый аспект программного обеспечения был лучшим вариантом. И, может быть, есть лучший способ.

(Наи)Лучший способ

Пару месяцев назад мой папа попросил меня помочь с проблемой. Он переводил одну из своих книг в уценку, и была проблема со сносками. В уценке сноски автоматически не присваивают себе значение; они должны быть помечены как числом, так и некоторым текстом, например: [^1] или [^footnote]. Определение такое же, с двоеточием в конце.

Он использовал pandoc для преобразования документа, но каждая сноска имела формат [^#]. Моя работа заключалась в том, чтобы сценарий заменил каждый # на число, начиная с 1.

Легко, правда?

Я просмотрел документ и заменил все вхождения шаблона на увеличивающееся целое число. И он выплюнул мусор.

Зачем? Потому что я сделал действительно очевидную ошибку. Счетчик не всегда занимает столько же места. Сценарий продолжал переписывать контент, и смещение увеличивалось, и больше заметок было заменено. Есть простое исправление: отслеживайте занятое пространство и добавьте в свою текущую позицию в документе. Я сделал это одно простое изменение, и все сработало отлично.  В то время, не зная этого, я использовал Таблицу.

Страница Википедии для Piece Table составляет всего 8 строк. Еще более важно отметить, что Microsoft Word относится к тем редакторам, которые используют таблицы. Тем не менее, таблица является очень многообещающей структурой. Более того, в его концепции Word был молниеносным, с бесконечным повторением / отменой, как объясняется в этой интересной статье разработчика Microsoft. Если у вас есть время, прочтите.

В 1998 году Чарльз Кроули написал статью, в которой анализируются плюсы и минусы различных структур данных, используемых в текстовых редакторах. Его исследование включает в себя буферы разломов, массивы и веревки. Он пришел к выводу, что - с точки зрения скорости, простоты и структуры - таблица кусков была ведущим методом. С моей точки зрения, таблицы также являются самым элегантным решением.

Нам нужны два буфера: исходный файл (только для чтения) и новый файл, который будет содержать весь наш добавленный текст (только для добавления). Наконец, у нас есть таблица с тремя столбцами: файл, начало, длина. Это файл для использования (оригинал или новый), где текстовый сегмент начинается в каждом файле (предварительная редактирование) и длина сегмента. Вот пример:

Original File: A_large_span_of_text   (underscores denote spaces)
New File:      English_

File           Start         Length
-----------------------------------
Original           0              2
Original           8              8
New                0              8
Original          16              4

Sequence: A_span_of_English_text

Имейте в виду, что индекс Start не относится к предыдущим изменениям. Это то, что обрабатывается во время выполнения, добавляя длину каждого предыдущего редактирования (например, то, что я сделал, чтобы исправить мой сценарий сносок). Поскольку длина уже включена в таблицу, это тривиальный шаг.

Мне нравится это решение, потому что:

  1. Это элегантно. Запись только минимального количества информации.
  2. Это просто. Мы выполняем только необходимые операции, нам не нужно повторно балансировать или пересекать двоичное дерево.
  3. Это быстро. Это решение имеет потенциал скорости. Есть несколько дополнительных соображений, которые необходимо учесть, которые подробно объясняются здесь.

Метод стоп-таблиц, безусловно, имеет свои сложности, и существуют различные варианты реализации. Это, безусловно, сложная задача. Я посмотрю, как далеко доберусь. Другая статья будет сопровождаться моими попытками реализовать метод таблицы.