Rope — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
м (Отсыпал запятых, пофиксил немного орфографии)
 
(не показано 8 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
'''Rope''' (рус. ''веревка'') {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
 
'''Rope''' (рус. ''веревка'') {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
  
Заведем [[Дерево поиска, наивная реализация|двоичное дерево поиска]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} сама строка.
+
Иногда при использовании строк нам нужны следующие свойства:
 +
*Операции, которые часто используются на строках, должны быть более эффективными. Например: конкатенация, взятие подстроки.
 +
*Также эти операции должны эффективно работать и с длинными строками. Не должно быть прямой зависимости от длины строк.
 +
*Персистентность. Иногда необходимо при изменении строки сохранить ее состояние перед изменением и вернуться к нему, если необходимо.
 +
 
 +
В данном случае Rope удовлетворяет всем этим свойствам.
 +
 
 +
==Описание структуры==
 +
Для хранения Rope создадим структуру, похожую на [[Декартово дерево по неявному ключу|декартово дерево по неявному ключу]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} самой строки. Используя информацию в промежуточных вершинах, можно получать символы строки по индексу, как будет показано ниже. Также заметим, что для отметки листа не обязательно хранить дополнительную информацию: все внутренние вершины имеют ровно двух детей, а листы {{---}} ни одного. Поэтому для проверки вершины на то, что она является листом, достаточно проверить, есть ли у неё дети.
  
 
==Merge==
 
==Merge==
Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
+
Когда приходит запрос на конкатенацию с другой строкой, мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
 
Пример результата конкатенации двух строк:
 
Пример результата конкатенации двух строк:
  
Строка 15: Строка 23:
 
===Время работы===
 
===Время работы===
  
Асимптотика выполнения операции конкатенации двух строк очевидно <tex>O(1)</tex>.
+
Асимптотика выполнения операции конкатенации двух строк, очевидно, <tex>O(1)</tex>.
  
 
==Получение символа по индексу==
 
==Получение символа по индексу==
  
Чтобы получить символ по некоторому индексу <tex>i</tex>, будем спускаться по дереву из корня, используя веса записанные вершинах чтобы определить в какое поддерево пойти из текущей вершины. Алгоритм выглядит следующим образом:
+
Чтобы получить символ по некоторому индексу <tex>i</tex>, будем спускаться по дереву из корня, используя веса, записанные в вершинах, чтобы определить, в какое поддерево пойти из текущей вершины. Алгоритм выглядит следующим образом:
  
 
* Текущая вершина {{---}} не лист, тогда возможно два варианта:
 
* Текущая вершина {{---}} не лист, тогда возможно два варианта:
 
** Вес левого поддерева больше либо равен <tex>i</tex>, тогда идем в левое поддерево.
 
** Вес левого поддерева больше либо равен <tex>i</tex>, тогда идем в левое поддерево.
 
** Иначе идем в правое поддерево и ищем там <tex>i - w</tex> символ, где <tex>w</tex> вес левого поддерева.
 
** Иначе идем в правое поддерево и ищем там <tex>i - w</tex> символ, где <tex>w</tex> вес левого поддерева.
* Текущая вершина {{---}} лист, тогда в этом листе хранится ответ, необходимо взять символ с соответствующим номером у строки которая там хранится.
+
* Текущая вершина {{---}} лист, тогда в этом листе хранится ответ; необходимо взять символ с соответствующим номером у строки, которая там хранится.
  
 
===Псевдокод===
 
===Псевдокод===
  '''char''' get('''int''' i,Node node):
+
  '''char''' get('''int''' i, Node node):
 
     '''if''' node.left <tex>\ne \varnothing</tex>
 
     '''if''' node.left <tex>\ne \varnothing</tex>
 
         '''if''' node.left.w >= i
 
         '''if''' node.left.w >= i
Строка 38: Строка 46:
 
===Время работы===
 
===Время работы===
  
Асимптотика выполнения одного такого запроса очевидно <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
+
Асимптотика выполнения одного такого запроса, очевидно, <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
  
 
==Split==
 
==Split==
  
Чтобы разбить строку на две по некоторому индексу <tex>i</tex> необходимо спускаясь по дереву (аналогично операции <tex>\mathrm{get}</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
+
Чтобы разбить строку на две по некоторому индексу <tex>i</tex>, необходимо, спускаясь по дереву (аналогично операции <tex>\mathrm{get}</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одной из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
  
 
Пускай дано дерево:
 
Пускай дано дерево:
Строка 48: Строка 56:
 
[[file:Split1.png|800px|Перед операцией split.]]
 
[[file:Split1.png|800px|Перед операцией split.]]
  
Тогда результатом выполнения операции <tex>\mathrm{split}</tex> по индексу 16 будет:  
+
Тогда результатом выполнения операции <tex>\mathrm{split}</tex> по индексу <tex> 16 </tex> будет:  
  
 
[[file:Split2.png|800px|Результат выполнения операции split.]]
 
[[file:Split2.png|800px|Результат выполнения операции split.]]
  
Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавится, просто заменив их на этого потомка. Тогда результатом той же операции <tex>\mathrm{split}</tex> будет:
+
Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавиться, просто заменив их на этого потомка. Тогда результатом той же операции <tex>\mathrm{split}</tex> будет:
  
 
[[file:Split3.png|800px|Результат выполнения операции split.]]
 
[[file:Split3.png|800px|Результат выполнения операции split.]]
Строка 61: Строка 69:
 
     '''if''' node.left <tex>\ne \varnothing</tex>
 
     '''if''' node.left <tex>\ne \varnothing</tex>
 
         '''if''' node.left.w >= i
 
         '''if''' node.left.w >= i
             '''Pair''' res = split(node.left, i)
+
             res = split(node.left, i)
 
             tree1 = res.first
 
             tree1 = res.first
 
             tree2.left = res.second
 
             tree2.left = res.second
Строка 67: Строка 75:
 
             tree2.w = tree2.left.w + tree2.right.w
 
             tree2.w = tree2.left.w + tree2.right.w
 
         '''else'''
 
         '''else'''
             '''Pair''' res = split(node.right, i - node.left.w)     
+
             res = split(node.right, i - node.left.w)     
 
             tree1.left = node.left
 
             tree1.left = node.left
 
             tree1.right = res.first
 
             tree1.right = res.first
Строка 77: Строка 85:
 
         tree1.w = i
 
         tree1.w = i
 
         tree2.w = node.s.len - i
 
         tree2.w = node.s.len - i
     '''return''' '''Pair'''(tree1, tree2)
+
     '''return''' <tex> \langle </tex>tree1, tree2<tex> \rangle </tex>
  
 
===Время работы===
 
===Время работы===
  
Нетрудно заметить что асимптотическая сложность выполнения данной операции <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
+
Нетрудно заметить, что асимптотическая сложность выполнения данной операции {{---}} <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
  
 
==Операции удаления и вставки==
 
==Операции удаления и вставки==
  
Нетрудно понять, что имея операция <tex>\mathrm{merge}</tex> и <tex>\mathrm{split}</tex>, можно легко через них выразить операции <tex>\mathrm{delete}</tex> и <tex>\mathrm{insert}</tex> по аналогии с другими деревьями поиска.
+
Нетрудно понять, что имея операции <tex>\mathrm{merge}</tex> и <tex>\mathrm{split}</tex>, можно легко через них выразить операции <tex>\mathrm{delete}</tex> и <tex>\mathrm{insert}</tex> по аналогии с другими деревьями поиска.
  
Операция <tex>\mathrm{delete}</tex> удаляет из строки подстроку начиная с индекса <tex>beginIndex</tex> и заканчивая (не включая) индексом <tex>endIndex</tex>.
+
Операция <tex>\mathrm{delete}</tex> удаляет из строки подстроку, начиная с индекса <tex>beginIndex</tex> и заканчивая (не включая) индексом <tex>endIndex</tex>.
  
 
===Псевдокод===
 
===Псевдокод===
Строка 95: Строка 103:
 
     '''return''' merge(tree1, tree3)
 
     '''return''' merge(tree1, tree3)
  
Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную начиная с позиции <tex>insertIndex</tex>.
+
Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную, начиная с позиции <tex>insertIndex</tex>.
  
 
===Псевдокод===
 
===Псевдокод===
Строка 105: Строка 113:
 
===Время работы===
 
===Время работы===
  
Так как данные операции используют только <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex> то асимптотика времени их работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
+
Так как данные операции используют только <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex>, то асимптотика времени их работы {{---}} <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
  
 
==Балансировка==
 
==Балансировка==
  
Для того чтобы дерево не превращалось в бамбук:
+
Для того, чтобы дерево не превращалось в бамбук:
  
 
[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]
 
[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]
Строка 117: Строка 125:
 
==Оптимизации==
 
==Оптимизации==
  
* Для уменьшения объема памяти занимаемой деревом и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
+
* Для уменьшения объема памяти, занимаемой деревом, и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
  
* Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса <tex>get</tex> и на следующем запросе сначала искать в сохраненном листе.
+
* Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист (а также его границы), в который мы пришли после очередного запроса <tex>\mathrm{get}</tex>, и на следующем запросе сначала искать в сохраненном листе. Также если хранить у каждой вершины ее предка, то последовательный доступ к символам будет выполняться за <tex>O(m)</tex>, где <tex>m</tex> {{---}} количество символов.
  
 
==См. также==
 
==См. также==

Текущая версия на 01:07, 10 февраля 2018

Rope (рус. веревка) — структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.

Иногда при использовании строк нам нужны следующие свойства:

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

В данном случае Rope удовлетворяет всем этим свойствам.

Описание структуры[править]

Для хранения Rope создадим структуру, похожую на декартово дерево по неявному ключу. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины — самой строки. Используя информацию в промежуточных вершинах, можно получать символы строки по индексу, как будет показано ниже. Также заметим, что для отметки листа не обязательно хранить дополнительную информацию: все внутренние вершины имеют ровно двух детей, а листы — ни одного. Поэтому для проверки вершины на то, что она является листом, достаточно проверить, есть ли у неё дети.

Merge[править]

Когда приходит запрос на конкатенацию с другой строкой, мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки. Пример результата конкатенации двух строк:

Результат конкатенации двух строк.

Псевдокод[править]

Node merge(Node n1, Node n2):
    return Node(n1, n2, n1.w + n2.w)

Время работы[править]

Асимптотика выполнения операции конкатенации двух строк, очевидно, [math]O(1)[/math].

Получение символа по индексу[править]

Чтобы получить символ по некоторому индексу [math]i[/math], будем спускаться по дереву из корня, используя веса, записанные в вершинах, чтобы определить, в какое поддерево пойти из текущей вершины. Алгоритм выглядит следующим образом:

  • Текущая вершина — не лист, тогда возможно два варианта:
    • Вес левого поддерева больше либо равен [math]i[/math], тогда идем в левое поддерево.
    • Иначе идем в правое поддерево и ищем там [math]i - w[/math] символ, где [math]w[/math] вес левого поддерева.
  • Текущая вершина — лист, тогда в этом листе хранится ответ; необходимо взять символ с соответствующим номером у строки, которая там хранится.

Псевдокод[править]

char get(int i, Node node):
    if node.left [math]\ne \varnothing[/math]
        if node.left.w >= i
            return get(i, node.left)
        else
            return get(i - node.left.w, node.right)
    else
        return node.s[i]

Время работы[править]

Асимптотика выполнения одного такого запроса, очевидно, [math]O(h)[/math], где [math]h[/math] — высота дерева.

Split[править]

Чтобы разбить строку на две по некоторому индексу [math]i[/math], необходимо, спускаясь по дереву (аналогично операции [math]\mathrm{get}[/math]), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одной из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.

Пускай дано дерево:

Перед операцией split.

Тогда результатом выполнения операции [math]\mathrm{split}[/math] по индексу [math] 16 [/math] будет:

Результат выполнения операции split.

Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавиться, просто заменив их на этого потомка. Тогда результатом той же операции [math]\mathrm{split}[/math] будет:

Результат выполнения операции split.

Псевдокод[править]

Pair<Node, Node> split(Node node, int i):
    Node tree1, tree2
    if node.left [math]\ne \varnothing[/math]
        if node.left.w >= i
            res = split(node.left, i)
            tree1 = res.first
            tree2.left = res.second
            tree2.right = node.right
            tree2.w = tree2.left.w + tree2.right.w
        else
            res = split(node.right, i - node.left.w)     
            tree1.left = node.left
            tree1.right = res.first
            tree1.w = tree1.left.w + tree1.right.w
            tree2 = res.second
    else
        tree1.s = node.s.substr(0, i)
        tree2.s = node.s.substr(i, node.s.len)
        tree1.w = i
        tree2.w = node.s.len - i
    return [math] \langle [/math]tree1, tree2[math] \rangle [/math]

Время работы[править]

Нетрудно заметить, что асимптотическая сложность выполнения данной операции — [math]O(h)[/math], где [math]h[/math] — высота дерева.

Операции удаления и вставки[править]

Нетрудно понять, что имея операции [math]\mathrm{merge}[/math] и [math]\mathrm{split}[/math], можно легко через них выразить операции [math]\mathrm{delete}[/math] и [math]\mathrm{insert}[/math] по аналогии с другими деревьями поиска.

Операция [math]\mathrm{delete}[/math] удаляет из строки подстроку, начиная с индекса [math]beginIndex[/math] и заканчивая (не включая) индексом [math]endIndex[/math].

Псевдокод[править]

Node delete(Node node, int beginIndex, int endIndex):
    (tree1, tree2) = split(node, beginIndex)
    tree3 = split(tree2, endIndex - beginIndex).second
    return merge(tree1, tree3)

Операция [math]\mathrm{insert}[/math] вставляет данную строку [math]s[/math] в исходную, начиная с позиции [math]insertIndex[/math].

Псевдокод[править]

Node insert(Node node, int insertIndex, string s):
    (tree1, tree3) = split(node, insertIndex)
    tree2 = Node(s)
    return merge(merge(tree1, tree2), tree3)

Время работы[править]

Так как данные операции используют только [math]\mathrm{split}[/math] и [math]\mathrm{merge}[/math], то асимптотика времени их работы — [math]O(h)[/math], где [math]h[/math] — высота дерева.

Балансировка[править]

Для того, чтобы дерево не превращалось в бамбук:

Пример вырождения дерева в бамбук.

Предлагается хранить его как АВЛ-дерево и делать соответствующие балансировки. Тогда, так как высота АВЛ-дерева [math]h = \log{n}[/math], то асимптотика операций [math] \mathrm{get, split, delete, insert, merge}[/math] будет равна [math]O(\log{n})[/math], где [math]n[/math] — количество сконкатенированных строк.

Оптимизации[править]

  • Для уменьшения объема памяти, занимаемой деревом, и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
  • Кэширование. Так как зачастую нужен последовательный доступ к индексам (например [math]i[/math] и [math]i + 1[/math]), то можно запоминать лист (а также его границы), в который мы пришли после очередного запроса [math]\mathrm{get}[/math], и на следующем запросе сначала искать в сохраненном листе. Также если хранить у каждой вершины ее предка, то последовательный доступ к символам будет выполняться за [math]O(m)[/math], где [math]m[/math] — количество символов.

См. также[править]

Источники информации[править]