Веревка (структура данных)

В компьютерном программировании веревка меньшего размера , или шнур — это структура данных, состоящая из строк которая используется для эффективного хранения и управления очень длинной строкой. Например, программа редактирования текста может использовать веревку для представления редактируемого текста, чтобы можно было эффективно выполнять такие операции, как вставка, удаление и произвольный доступ. ^[1]

Описание

Веревка — это тип двоичного дерева , в котором каждый лист (конечный узел) содержит строку и длину (также известную как «вес»), а каждый узел, расположенный дальше по дереву, содержит сумму длин всех листьев в его левое поддерево . Таким образом, узел с двумя дочерними элементами делит всю строку на две части: в левом поддереве хранится первая часть строки, в правом поддереве хранится вторая часть строки, а вес узла равен длине первой части.

Для операций с веревками строки, хранящиеся в узлах, считаются постоянными неизменяемыми объектами в типичном неразрушающем случае, что допускает некоторое поведение копирования при записи . Листовые узлы обычно реализуются как базовые строки фиксированной длины со счетчиком ссылок, присоединяемым для освобождения, когда они больше не нужны, хотя сборки мусора можно использовать и другие методы .

Операции

В следующих определениях N — длина веревки, то есть вес корневого узла.

Собирать листья

Определение: стек S и список L. Создайте Пройдите вниз по самому левому позвоночнику дерева, пока не дойдете до листа l', добавляя каждый узел n к S . к L. Добавьте l ' Родитель l' ( p ) находится на вершине стека. Повторите процедуру для правого поддерева p.

final class InOrderRopeIterator implements Iterator<RopeLike> {

    private final Deque<RopeLike> stack;

    InOrderRopeIterator(@NonNull RopeLike root) {
        stack = new ArrayDeque<>();
        var c = root;
        while (c != null) {
            stack.push(c);
            c = c.getLeft();
        }
    }

    @Override
    public boolean hasNext() {
        return stack.size() > 0;
    }

    @Override
    public RopeLike next() {
        val result = stack.pop();

        if (!stack.isEmpty()) {
            var parent = stack.pop();
            var right = parent.getRight();
            if (right != null) {
                stack.push(right);
                var cleft = right.getLeft();
                while (cleft != null) {
                    stack.push(cleft);
                    cleft = cleft.getLeft();
                }
            }
        }

        return result;
    }
}

Ребалансировка

Определение: Соберите набор листьев L и перестройте дерево снизу вверх.

static boolean isBalanced(RopeLike r) {
    val depth = r.depth();
    if (depth >= FIBONACCI_SEQUENCE.length - 2) {
        return false;
    }
    return FIBONACCI_SEQUENCE[depth + 2] <= r.weight();
}

static RopeLike rebalance(RopeLike r) {
    if (!isBalanced(r)) {
        val leaves = Ropes.collectLeaves(r);
        return merge(leaves, 0, leaves.size());
    }
    return r;
}

static RopeLike merge(List<RopeLike> leaves) {
    return merge(leaves, 0, leaves.size());
}

static RopeLike merge(List<RopeLike> leaves, int start, int end) {
    int range = end - start;
    if (range == 1) {
        return leaves.get(start);
    }
    if (range == 2) {
        return new RopeLikeTree(leaves.get(start), leaves.get(start + 1));
    }
    int mid = start + (range / 2);
    return new RopeLikeTree(merge(leaves, start, mid), merge(leaves, mid, end));
}

Вставлять

Определение: Insert(i, S’): вставьте строку S', начинающуюся с позиции i в строку s , чтобы сформировать новую строку

C 1, ..., C i, S', C i + 1, ..., C m

.

Временная сложность: ⁠

O(\log N)

⁠ .

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

public Rope insert(int idx, CharSequence sequence) {
    if (idx == 0) {
        return prepend(sequence);
    }
    if (idx == length()) {
        return append(sequence);
    }
    val lhs = base.split(idx);
    return new Rope(Ropes.concat(lhs.fst.append(sequence), lhs.snd));
}

Индекс

Определение: Index(i): вернуть символ в позицию i

Временная сложность: ⁠

O(\log N)

⁠

Чтобы получить i -й символ, мы начинаем рекурсивный поиск с корневого узла:

@Override
public int indexOf(char ch, int startIndex) {
    if (startIndex > weight) {
        return right.indexOf(ch, startIndex - weight);
    }
    return left.indexOf(ch, startIndex);
}

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

Конкат

Определение: Concat(S1, S2): объединить две веревки S ₁ и S ₂ в одну веревку.

Временная сложность: ⁠

O(1)

⁠ (или ⁠

O(\log N)

⁠ время для вычисления веса корня)

Конкатенацию можно выполнить, просто создав новый корневой узел с влево = S1 и right = S2 , что является постоянным временем. Вес родительского узла равен длине левого дочернего узла S ₁ , что потребует ⁠ $O(\log N)$ ⁠ время, если дерево сбалансировано.

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

Расколоть

Определение: Split (i, S): разделить строку S на две новые строки S ₁ и S ₂ ,

S 1 = C 1, ..., C i

и

S 2 = C i + 1, ..., C m

.

Временная сложность: ⁠

O(\log N)

⁠

Есть два случая, которые необходимо рассмотреть:

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

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

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

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

public Pair<RopeLike, RopeLike> split(int index) {
    if (index < weight) {
        val split = left.split(index);
        return Pair.of(rebalance(split.fst), rebalance(new RopeLikeTree(split.snd, right)));
    } else if (index > weight) {
        val split = right.split(index - weight);
        return Pair.of(rebalance(new RopeLikeTree(left, split.fst)), rebalance(split.snd));
    } else {
        return Pair.of(left, right);
    }
}

Удалить

Определение: Delete(i, j): удалить подстроку

C i, \dots, C i + j - 1

из s , чтобы сформировать новую строку

C 1, \dots, C i - 1, C i + j, \dots, C m

.

Временная сложность: ⁠

O(\log N)

⁠ .

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

@Override
public RopeLike delete(int start, int length) {
    val lhs = split(start);
    val rhs = split(start + length);
    return rebalance(new RopeLikeTree(lhs.fst, rhs.snd));
}

Отчет

Определение: Report(i, j): вывести строку

C i, \dots, C i + j - 1

.

Временная сложность: ⁠

O(j+\log N)

⁠

Чтобы сообщить строку $C i, \dots, C i + j - 1$ , найдите узел u , который содержит C _i и weight(u) >= j, а затем пройдите T, начиная с узла u . Выведите $C i, \dots, C i + j - 1,$ выполнив упорядоченный обход T , начиная с узла u .

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

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

Преимущества:

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

Недостатки:

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

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

См. также

Среда программирования Cedar , в которой веревки использовались «почти с момента ее создания». ^[1]
Анфилада Model T , аналогичная структура данных начала 1970-х годов.
Буфер пробела — структура данных, обычно используемая в текстовых редакторах, которая позволяет эффективно выполнять операции вставки и удаления, сгруппированные в одном и том же месте.
Таблица частей — еще одна структура данных, обычно используемая в текстовых редакторах.

Ссылки

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Бём, Ханс-Дж; Аткинсон, Расс; Пласс, Майкл (декабрь 1995 г.). «Веревки: альтернатива струнам» ( PDF ) . Программное обеспечение: практика и опыт . 25 (12). Нью-Йорк, штат Нью-Йорк, США: John Wiley & Sons, Inc.: 1315–1330. дои : 10.1002/спе.4380251203 . Архивировано из оригинала 8 марта 2020 г.
^ Jump up to: Перейти обратно: ^а ^б «Обзор реализации веревки» . www.sgi.com . Архивировано из оригинала 19 декабря 2017 г. Проверено 01 марта 2017 г.

Внешние ссылки

Реализация веревок "absl::Cord" в библиотеке Abseil.
Реализация веревок «C cords» в библиотеке Boehm Garbage Collector.
Спецификация SGI C++ для веревок (поддерживается STLPort и libstdc++ )
Веревки для C#
веревки для Common Lisp
Веревки для Java
Струнные веревки для Java
Веревки для JavaScript
Веревки для Лимбо
веревки для Нима
Веревки для OCaml
пиропы для Python
Веревки для Smalltalk
SwiftRope для Swift
«Ропи» для Rust

[Boehm-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Бём, Ханс-Дж; Аткинсон, Расс; Пласс, Майкл (декабрь 1995 г.). «Веревки: альтернатива струнам» ( PDF ) . Программное обеспечение: практика и опыт . 25 (12). Нью-Йорк, штат Нью-Йорк, США: John Wiley & Sons, Inc.: 1315–1330. дои : 10.1002/спе.4380251203 . Архивировано из оригинала 8 марта 2020 г.

[:0-2] Jump up to: Перейти обратно: ^а ^б «Обзор реализации веревки» . www.sgi.com . Архивировано из оригинала 19 декабря 2017 г. Проверено 01 марта 2017 г.

[1]

[2]

v т и Струны
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt pattern matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm Raita algorithm Trigram search Two-way string-matching algorithm Zhu–Takaoka string matching algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	BLAST Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting String rewriting systems String operations