Редактирование: Rope

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Rope''' (рус. ''веревка'') {{---}} структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
+
{{Определение
 +
|definition=
 +
Rope - структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.
 +
}}
  
Иногда при использовании строк нам нужны следующие свойства:
+
Заведем двоичное сбалансированное дерево поиска. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.
*Операции, которые часто используются на строках, должны быть более эффективными. Например: конкатенация, взятие подстроки.
 
*Также эти операции должны эффективно работать и с длинными строками. Не должно быть прямой зависимости от длины строк.
 
*Персистентность. Иногда необходимо при изменении строки сохранить ее состояние перед изменением и вернуться к нему, если необходимо.
 
 
 
В данном случае Rope удовлетворяет всем этим свойствам.
 
 
 
==Описание структуры==
 
Для хранения Rope создадим структуру, похожую на [[Декартово дерево по неявному ключу|декартово дерево по неявному ключу]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} самой строки. Используя информацию в промежуточных вершинах, можно получать символы строки по индексу, как будет показано ниже. Также заметим, что для отметки листа не обязательно хранить дополнительную информацию: все внутренние вершины имеют ровно двух детей, а листы {{---}} ни одного. Поэтому для проверки вершины на то, что она является листом, достаточно проверить, есть ли у неё дети.
 
  
 
==Merge==
 
==Merge==
Когда приходит запрос на конкатенацию с другой строкой, мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
+
Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
 
Пример результата конкатенации двух строк:
 
Пример результата конкатенации двух строк:
  
 
[[file:String_concat.png|800px|Результат конкатенации двух строк.]]
 
[[file:String_concat.png|800px|Результат конкатенации двух строк.]]
  
===Псевдокод===
+
'''Псевдокод:'''
Node merge(Node n1, Node n2):
+
<pre>
    '''return''' Node(n1, n2, n1.w + n2.w)
+
merge(T1, T2):
 
+
    Node node
===Время работы===
+
    node.left = T1
 +
    node.right = T2
 +
    return node
 +
</pre>
  
Асимптотика выполнения операции конкатенации двух строк, очевидно, <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):
 
    '''if''' node.left <tex>\ne \varnothing</tex>
 
        '''if''' node.left.w >= i
 
            '''return''' get(i, node.left)
 
        '''else'''
 
            '''return''' get(i - node.left.w, node.right)
 
    '''else'''
 
        '''return''' node.s[i]
 
  
===Время работы===
+
'''Псевдокод:'''
 +
<pre>
 +
get(i, node):
 +
    if (!isNil(node):
 +
        if (node.left >= i):
 +
            return get(i, node.left)
 +
        else:
 +
            return get(i - node.left.w, node.right)
 +
    else:
 +
        return node.s[i]
 +
</pre>
  
Асимптотика выполнения одного такого запроса, очевидно, <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>get</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
  
 
Пускай дано дерево:
 
Пускай дано дерево:
Строка 56: Строка 54:
 
[[file:Split1.png|800px|Перед операцией split.]]
 
[[file:Split1.png|800px|Перед операцией split.]]
  
Тогда результатом выполнения операции <tex>\mathrm{split}</tex> по индексу <tex> 16 </tex> будет:  
+
Тогда результатом выполнения операции <tex>split</tex> по индексу 16 будет:  
  
 
[[file:Split2.png|800px|Результат выполнения операции split.]]
 
[[file:Split2.png|800px|Результат выполнения операции split.]]
  
Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавиться, просто заменив их на этого потомка. Тогда результатом той же операции <tex>\mathrm{split}</tex> будет:
+
Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавится, просто заменив их на этого потомка. Тогда результатом той же операции <tex>split</tex> будет:
  
 
[[file:Split3.png|800px|Результат выполнения операции split.]]
 
[[file:Split3.png|800px|Результат выполнения операции split.]]
  
===Псевдокод===
+
'''Псевдокод:'''
'''Pair'''<Node, Node> split(Node node, '''int''' i):
+
<pre>
    Node tree1, tree2
+
split(node, i):
    '''if''' node.left <tex>\ne \varnothing</tex>
+
    Node t1, t2
        '''if''' node.left.w >= i
+
    t1.w = i
            res = split(node.left, i)
+
    t2.w = node.w - i
            tree1 = res.first
+
    Pair res
            tree2.left = res.second
+
    if (!isNil(node)):
            tree2.right = node.right
+
        if (node.left >= i):
            tree2.w = tree2.left.w + tree2.right.w
+
            res = split(node.left, i)
        '''else'''
+
            t1 = res.first
            res = split(node.right, i - node.left.w)     
+
            t2.left = res.second
            tree1.left = node.left
+
            t2.right = node.right
            tree1.right = res.first
+
        else:
            tree1.w = tree1.left.w + tree1.right.w
+
            res = split(node.right, i - node.left.w)     
            tree2 = res.second
+
            t1.left = node.left
    '''else'''
+
            t1.right = res.first
        tree1.s = node.s.substr(0, i)
+
            t2 = res.second
        tree2.s = node.s.substr(i, node.s.len)
+
    else:
        tree1.w = i
+
        t1.s = node.s.substr(0, i)
        tree2.w = node.s.len - i
+
        t2.s = node.s.substr(i, s.len)
    '''return''' <tex> \langle </tex>tree1, tree2<tex> \rangle </tex>
+
    return pair(t1, t2)
 
+
</pre>
===Время работы===
 
  
Нетрудно заметить, что асимптотическая сложность выполнения данной операции {{---}} <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>merge</tex> и <tex>split</tex>, можно легко через них выразить операции <tex>delete</tex> и <tex>insert</tex> по аналогии с другими деревьями поиска.
 
 
Операция <tex>\mathrm{delete}</tex> удаляет из строки подстроку, начиная с индекса <tex>beginIndex</tex> и заканчивая (не включая) индексом <tex>endIndex</tex>.
 
  
===Псевдокод===
+
Операция <tex>delete</tex> удаляет из строки подстроку начиная с индекса <tex>beginIndex</tex> и заканчивая(не включая) индексом <tex>endIndex</tex>.
Node delete(Node node, '''int''' beginIndex, '''int''' endIndex):
 
    (tree1, tree2) = split(node, beginIndex)
 
    tree3 = split(tree2, endIndex - beginIndex).second
 
    '''return''' merge(tree1, tree3)
 
  
Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную, начиная с позиции <tex>insertIndex</tex>.
+
'''Псевдокод:'''
 +
<pre>
 +
delete(node, beginIndex, endIndex):
 +
    Node t1, t2, t3
 +
    (t1, t2) = split(node, beginIndex)
 +
    t3 = split(t2, endIndex).second
 +
    return merge(t1, t3)
 +
</pre>
  
===Псевдокод===
+
Операция <tex>insert</tex> вставляет данную строку <tex>s</tex> в исходную начиная с позиции <tex>insertIndex</tex>.
Node insert(Node node, '''int''' insertIndex, '''string''' s):
 
    (tree1, tree3) = split(node, insertIndex)
 
    tree2 = Node(s)
 
    '''return''' merge(merge(tree1, tree2), tree3)
 
  
===Время работы===
+
'''Псевдокод:'''
 +
<pre>
 +
insert(node, insertIndex, s):
 +
    Node t1, t2
 +
    (t1, t2) = split(node, insertIndex)
 +
    Node t3 = node(s)
 +
    t1 = merge(t1, t3)
 +
    return merge(t1, t2)
 +
</pre>
  
Так как данные операции используют только <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex>, то асимптотика времени их работы {{---}} <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
+
Так как данные операции используют только <tex>split</tex> и <tex>merge</tex> то асимптотика времени их работы <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
  
 
==Балансировка==
 
==Балансировка==
  
Для того, чтобы дерево не превращалось в бамбук:
+
Для того чтобы дерево не превращалось в бамбук:
  
 
[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]
 
[[file:Bamboo.png|800px|Пример вырождения дерева в бамбук.]]
  
Предлагается хранить его как [[АВЛ-дерево]] и делать соответствующие балансировки. Тогда, так как высота АВЛ-дерева <tex>h = \log{n}</tex>, то асимптотика операций <tex> \mathrm{get, split, delete, insert, merge}</tex> будет равна <tex>O(\log{n})</tex>, где <tex>n</tex> {{---}} количество сконкатенированных строк.
+
Предлагается хранить его как [[АВЛ-дерево]] и делать соответствующие балансировки. Тогда так как высота АВЛ-дерева <tex>h = \log{n}</tex> то асимптотика операций <tex> get, split, delete, insert</tex> будет равна <tex>O(\log{n})</tex>.
  
 
==Оптимизации==
 
==Оптимизации==
  
* Для уменьшения объема памяти, занимаемой деревом, и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
+
* Для уменьшения объема памяти занимаемой деревом и уменьшения высоты дерево, предлагается при конкатенации с маленькой строкой делать конкатенацию классическим способом.
 
 
* Кэширование. Так как зачастую нужен последовательный доступ к индексам (например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист (а также его границы), в который мы пришли после очередного запроса <tex>\mathrm{get}</tex>, и на следующем запросе сначала искать в сохраненном листе. Также если хранить у каждой вершины ее предка, то последовательный доступ к символам будет выполняться за <tex>O(m)</tex>, где <tex>m</tex> {{---}} количество символов.
 
  
==См. также==
+
* Кэширование. Так как зачастую нужна последовательный доступ к индексам(например <tex>i</tex> и <tex>i + 1</tex>), то можно запоминать лист, а также его границы, в который мы пришли после очередного запроса <tex>get</tex> и на следующем запросе сначала искать в сохраненном листе.
  
*[[АВЛ-дерево]]
+
==Литература==
*[[Splay-дерево]]
 
*[[Декартово дерево по неявному ключу]]
 
==Источники информации==
 
  
*[[wikipedia:en:Rope_(data_structure)|Wikipedia {{---}} Rope]]
+
*[[wikipedia:en:Rope_(data_structure)|Википедия - Rope]]
*[http://habrahabr.ru/post/144736/ Ropes {{---}} быстрые строки]
+
*[http://habrahabr.ru/post/144736/ Ropes быстрые строки]
 
*[http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf Ropes: an Alternative to Strings]
 
*[http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf Ropes: an Alternative to Strings]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Деревья поиска]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: