Википедия

Строп (структура данных)

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

Простой строп для представления строки «Hello_my_name_is_Simon»

Описание править

Строп представляет собой двоичное дерево, где каждый лист (узел без потомков) содержит строку (подстроку текста) и длину (вес), а каждый нелистовой узел дерева содержит длину листьев своего левого дочернего поддерева. Узел с двумя детьми разбивает целую строку на две части, где первую часть хранит левое поддерево, вторую — правое, вес самого узла равен длине первой части. Для основных операций полагается, что строки не изменяются в неразрушающем случае, допуская копирование-при-записи. Листовые узлы обычно реализуются как строки постоянной длины с счётчиком ссылок, когда он обнуляется память высвобождается. Могут также использоваться продвинутые способы сборки мусора.

Операции править

В следующих определениях N — длина стропа.

Вставка править

Определение: Insert(i, S’): вставляет строку S’ начиная с позиции i в строку s, получая новую строку C1, …, Ci, S', Ci + 1, …, Cm.
Сложность: O(log N).

Эту операцию можно выполнить с помощью Split() и двух операций Concat().

Обращение править

 
Рисунок 2.1: Пример обращения к стропу.
Определение: Index(i): возвращает символ в позиции i
Сложность: O(log N)

Для просмотра i-го символа, мы начинаем рекурсивный поиск начиная с корня: 

function index(RopeNode node, integer i)
  if node.weight <= i and exists(node.right) then
    return index(node.right, i - node.weight)
  end
  
  if exists(node.left) then
    return index(node.left, i)
  end
  
  return node.string[i]
end

Например посмотрим на Рисунок 2.1, чтобы найти символ на позиции i=10, мы начиная с корня(A), имеем что его вес 22 больше 10, поэтому спускаемся влево(B). Здесь имеем, что 9 меньше 10, вычитаем 9 из 10 (получая i=1) и переходим к правому дочернему узлу(D). Имеем 6 больше 1 и переходим к левому ребёнку(G). Здесь 2 больше 1 спускаемся влево(J). И наконец 2 больше 1, но так как это листовой узел, то детей у него нет и мы просто обращаемся по индексу 1, хранящейся в узле строки «na» (то есть «a»), что и будет ответом.

Сцепка править

 
Рисунок 2.2: Сцепка двух дочерних строп в один.
Определение: Concat(S1, S2): Сцепляет два стропа, S1 и S2, в один целый.
Сложность: O(1) (или O(log N) при вычислении веса корня)

Сцепка выполняется путём создания нового корня с дочерними узлами левый = S1 и правый = S2, за постоянное время. Вес родительского узла устанавливается равным длине левого ребёнка S1, что может занять O(log N), если дерево сбалансировано.

Большинство строповых операций требуют сбалансированность дерева, после сцепки может потребоваться балансировка дерева.

Разбиение править

 
Рисунок 2.3: Разбивка стропа.
Определение: Split (i, S): разбивает строку S на две новые S1 и S2, где S1 = C1, …, Ci и S2 = Ci + 1, …, Cm.
Сложность: O(log N)

Возможны два случая:

  1. Точка разбиения находится в конце строки(то есть после последнего символа листового узла)
  2. Точка разбиения находится в середине строки.

Второй случай сводится к первому путём разбивки строки в точке разбиение и создания двух новых листовых узлов, затем созданием для них нового, родительского к ним узла.

Например, для разбивки 22-символьного стропа с Рисунка 2.3 на две компоненты длины 11, запрашиваем 12-й символ, чтобы определить узел K на нижнем уровне. Удаляем ссылку между K и G. Переходим к родителю G и вычитаем вес K из веса D. Восходим вверх по дереву и удаляем все правые ссылки на поддеревья содержащие символы после 11-го символа, вычитая вес K из их родительских узлов (в нашем случае только D и A). Наконец выстраиваем недавно осиротевшие узлы K и H, созданием для них нового родителя P с весом равного длине левого дочернего узла K.

Большинство строповых операций требуют сбалансированность дерева, после разбивки может потребоваться балансировка дерева..

Удаление править

Определение: Delete(i, j): удалить подстроку Ci, …, Ci + j − 1, из s и создать новую строку C1, …, Ci − 1, Ci + j, …, Cm.
Сложность: O(log N).

Может быть выполнено двумя Split() и одним Concat(). Для начала строп делим на три, отделёнными i-ым и i+j-ым символами соответственно, удаляемая строка будет выделена в отдельный(средний) узел. Затем сцепляем другие два узла.

Запрос править

Определение: Report(i, j): отдаёт строку Ci, …, Ci + j − 1.
Сложность: O(j + log N)

Для запроса строки Ci, …, Ci + j − 1, находим узел u, содержащий Ci с weight(u) >= j, а затем посещаем T начиная с узла u. Выводим Ci, …, Ci + j − 1 посещая по порядку T начиная с узла u.

Сравнение с плотными массивами править

Производительность
Операция Строп Массив
Обращение[1] O(log n) O(1)
Разбивка[1] O(log n) O(1)
Сцепка (деструкт) O(log n) без балансировки / O(n) худший случай O(n)
Сцепка (недеструкт) O(n) O(n)
Посимвольный проход[1] O(n) O(n)
Вставка[2] O(log n) без балансировки / O(n) худший случай O(n)
Добавление[2] O(log n) без балансировки / O(n) худший случай O(1) амортизированная, O(n) без балансировки
Удаление O(log n) O(n)
Запрос O(j + log n) O(j)
Создание O(n) O(n)

Достоинства:

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

Недостатки:

  • Больше общее используемое пространство, которое нужно только при выполнении операций (для хранения родительских узлов). Нужно искать компромисс между тем, сколько лишней памяти будем хранить и тем насколько длинными могут быть подстроки в узлах. Строки в примерах выше очевидно были слишком короткими. Избыточная сложность всегда будет O(n), но постоянную можно уменьшать.
  • Возросшее время на работу с дополнительной памятью
  • Возросшая сложность кода; вероятнее появление ошибок

В данной таблице сравниваются алгоритмические свойства реализаций строк и строп, а не их сырая скорость. Строки на массивах менее накладны так, что например сцепка и разбивка будут значительно быстрее для малых строк. Тем не менее при использовании массивов для длинных строк, временная сложность и затраты памяти будут уже неприемлемо большими(так как сильно возрастёт количество копирований). Напротив производительность не зависит от длины данных. К тому же сложность по памяти в обоих представлениях оценивается O(n). Подводя итог — стропы предпочтительнее, когда строки очень длинные и они часто меняются.

Также править

  • Cedar[en] программная среда, которая использовала стропы «почти с самого их появления»[1]
  • Модель T анфилада[en], похожая структура данных из ранних 70-х.
  • Буферное окно, структура данных, используемая в текстовых редакторах, позволяющая выполнять эффективно вставку и удаление над близко расположенными данными.
  • Кусочная таблица[en], ещё одна структура данных, используемая в редакторах текста.

Примечания править

  1. ↑ 1 2 3 4 5 Boehm, Hans-J; Atkinson, Russ; Plass, Michael (December 1995). "Ropes: an Alternative to Strings" (PDF). Software—Practice & Experience. New York, NY, USA: John Wiley & Sons, Inc. 25 (12): 1315—1330. doi:10.1002/spe.4380251203. Архивировано из оригинала 8 марта 2020.
  2. ↑ 1 2 Rope Implementation Overview. www.sgi.com. Дата обращения: 1 марта 2017. Архивировано 19 декабря 2017 года.

Ссылки править

Источник — https://ru.wikipedia.org/w/index.php?title=Строп_(структура_данных)&oldid=124723609