- Денисова Мария
- Конончук Сергей
- Полухин Максим
LOUDS - это компактная структура данных, предстовляющая корневое упорядоченное дерево, содержащее узлы произвольной степени.
- Данная структура позволяет хранить информацию о структуре дерева в формате битовой строки длиной 2n + 1, где n - число узлов.
- Битова строка формируется последовательностями единично-закодированных узлов, сортированных по уровням.
- Для построения битовой строки в дерево добавляется дополнительный узел - искусственный корень. Он кодируется как '10'. Он имеет индекс -1.
- Все настоящие узлы дерева индексируются начиная с 0 в порядке BFS(обход в ширину).
- В соответствии с нумерацией узлов заполняется битовая строка: для узла определяется количество потомков, в битовую строку записываются единицы в соответствии с количеством потомков, последовательность единиц заканчивает нулем, операция повторяется для следующего узла.
- Если узел является листом, он записывается просто как 0.
// Пример дерева: 0 / | \ 1 2 3 / \ 4 5 // Битова строка LOUDS: 10 1110 0 110 0 0 0 - Навигация по дереву осуществляется с помощью опираций RANK и SELECT.
- RANKx(i) возвращает количество бит, равных x, чьи индексы лежат на отрезке [0; i]. Так как x — значение бита, то он может быть равен исключительно 0 или 1.
- SELECTx(j) возвращает индекс j-го бита, равного x. j > 0, то есть подсчет ведется от единицы. Кроме того, j не может превышать суммарное количество битов в словаре, равных x.
- SELECT является обратной операцией для RANK.
- Эффективность использования LOUDS напрямую зависит от эффективности реализации методов RANK и SELECT. В нашей реализации происходит предрасчет таблиц для RANK1, SELECT1 и SELECT0, поэтому базовые операции (поиск родителя, первого потомка, последнего потомка) имеют сложность O(1).
Так как LOUDS является деревом, данная структура может быть использована как префиксное дерево для поиска слов. Префиксные деревья широко применяется в сжатии данных, вычислительной биологии, алгоритме поиска наибольшего префикса, используемом для таблиц маршрутизации IP-адресов, реализации словаря, поиске по шаблону, автодополнении текста, хранении XML-документов и запросах к ним и т. д.
Сравнительная таблица нашей реализации LOUDS Trie и простого Trie:
| LOUDS Trie | Trie | |
|---|---|---|
| Время построения дерева (5000 слов) | 6 ms | 2 ms |
| Время построения дерева (7500 слов) | 8 ms | 2 ms |
| Время построения дерева (10000 слов) | 11 ms | 3 ms |
| Время построения дерева (25000 слов) | 39 ms | 8 ms |
| Время построения дерева (50000 слов) | 83 ms | 16 ms |
| Время построения дерева (75000 слов) | 129 ms | 24 ms |
| Время построения дерева (100000 слов) | 177 ms | 34 ms |
| Память (5000 слов) | 1662 Kb | 3679 Kb |
| Память (7500 слов) | 2449 Kb | 5400 Kb |
| Память (10000 слов) | 3106 Kb | 7111 Kb |
| Память (25000 слов) | 7182 Kb | 16466 Kb |
| Память (50000 слов) | 13774 Kb | 30764 Kb |
| Память (75000 слов) | 20065 Kb | 44501 Kb |
| Память (100000 слов) | 25347 Kb | 58001 Kb |
| Сложность поиска слова | O(m*log(k)), где m - длина слова, k - средняя степень узла | O(n), где n - длина слова |
| Поиск 10% слов от общего объема | ||
| Среднее время поиска (5000 слов) | 2 ms | 1 ms |
| Среднее время поиска (7500 слов) | 2 ms | 1 ms |
| Среднее время поиска (10000 слов) | 2 ms | 1 ms |
| Среднее время поиска (25000 слов) | 3 ms | 1 ms |
| Среднее время поиска (50000 слов) | 7 ms | 2 ms |
| Среднее время поиска (75000 слов) | 9 ms | 4 ms |
| Среднее время поиска (100000 слов) | 15 ms | 4 ms |
| Поиск 500 слов | ||
| Среднее время поиска (5000 слов) | 2 ms | 1 ms |
| Среднее время поиска (7500 слов) | 1 ms | 1 ms |
| Среднее время поиска (10000 слов) | 1 ms | 1 ms |
| Среднее время поиска (25000 слов) | 2 ms | 1 ms |
| Среднее время поиска (50000 слов) | 1 ms | 1 ms |
| Среднее время поиска (75000 слов) | 2 ms | 1 ms |
| Среднее время поиска (100000 слов) | 2 ms | 1 ms |
| Поиск 1000 слов | ||
| Среднее время поиска (5000 слов) | 3 ms | 1 ms |
| Среднее время поиска (7500 слов) | 2 ms | 1 ms |
| Среднее время поиска (10000 слов) | 1 ms | 1 ms |
| Среднее время поиска (25000 слов) | 1 ms | 1 ms |
| Среднее время поиска (50000 слов) | 2 ms | 1 ms |
| Среднее время поиска (75000 слов) | 3 ms | 1 ms |
| Среднее время поиска (100000 слов) | 2 ms | 1 ms |
| Поиск по префиксу | ||
| Среднее время поиска (219 префиксов, 5000 слов) | 4 ms | 2 ms |
| Среднее время поиска (234 префиксов, 7500 слов) | 2 ms | 2 ms |
| Среднее время поиска (248 префиксов, 10000 слов) | 2 ms | 1 ms |
| Среднее время поиска (313 префиксов, 25000 слов) | 2 ms | 3 ms |
| Среднее время поиска (389 префиксов, 50000 слов) | 5 ms | 5 ms |
| Среднее время поиска (441 префиксов, 75000 слов) | 7 ms | 7 ms |
| Среднее время поиска (500 префиксов, 100000 слов) | 12 ms | 10 ms |
| Операции добавления/удаления узла | Не поддерживаются без дополнительных структур данных, так как номера узлов становятся не действительны | Поддерживаются |
- по памяти LOUDS Trie занимает меньше места ~ в 2,3 раза.
- По времени выполнения поиска слов классический Trie более эффективен, это особенно явно проявляется на больших объемах данных.
- Разница временной эффективности выполнения запросов между LOUDS Trie и простым Trie может варьироваться в зависимости от реализации LOUDS Trie.
- LOUDS Trie значительно компактнее классического префиксного дерева
- Для решения конкретной задачи стоит выбирать между LOUDS Trie и простым Trie в зависимости от требовай к занимаемой памяти и производительности запросов.