Comments 24
UFO just landed and posted this here
1) На первых двух графиках сравниваются между собой два времени, какая разница, какая там шкала? На третьем шкала обозначена… На серьезную статобработку данных времени и сил пока нет :)
2) Стек выдержал :) Кстати, да, надо было бы глубину дерева измерить. А в принципе, можно и итеративную реализацию сделать…
3) А какая длина массива должна быть (это в случае, когда дерево мутируется)? На самом деле я уже думал над таким вариантом — держать в узле вектор указателей на всех дочерей узла…
2) Стек выдержал :) Кстати, да, надо было бы глубину дерева измерить. А в принципе, можно и итеративную реализацию сделать…
3) А какая длина массива должна быть (это в случае, когда дерево мутируется)? На самом деле я уже думал над таким вариантом — держать в узле вектор указателей на всех дочерей узла…
UFO just landed and posted this here
1) С этим замечанием согласен, на графике время отнормировано на размер (в символах) используемого набора строк, иначе разброс для одного графика оказывался очень большим. Сейчас попробую пересчитать чистое время… На третьем графике шкала обозначена в подписи :) — по оси Y отложено количество байт на один символ (символ у меня занимает один байт)…
2,3) Про продакшн никто и не говорит :)
2,3) Про продакшн никто и не говорит :)
Глубина рекурсии в префиксных деревьях обычно мала: глубина дерева не больше самого длинного ключа, а число связей не больше размера алфавита. Если ключи разумные, а не «Война и Мир», то все нормально.
Внутренние участки без ветвлений — специфическая ситуация, редко возникающая на реальных данных. С самого начала строить структуру данных вокруг оптимизации этого момента мне кажется преждевременным. Попробуйте добавить к сравнению эту реализацию, разделяя слова «долларом».
Доля правды в ваших словах есть. Вот распределение длин ключей во внутренних узлах дерева для двух тестовых наборов:
Однако, хранить в одном узле один символ (при двух указателях) — это, по-моему, перебор. Хотя, с другой стороны, такой вариант (несжатое префиксное дерево) у меня реализован, но статистику я с него еще не снимал…
Ссылку попозже посмотрю, спасибо!
Однако, хранить в одном узле один символ (при двух указателях) — это, по-моему, перебор. Хотя, с другой стороны, такой вариант (несжатое префиксное дерево) у меня реализован, но статистику я с него еще не снимал…
Ссылку попозже посмотрю, спасибо!
Не хватает оптимизаций по памяти, in-place constructor и прочего. На каждый чих выделять кусок памяти — некрасиво.
P. S. Пролистал, вечером буду детально разбираться, но выглядит как и все прочие ваши статьи на 5+.
P. S. Пролистал, вечером буду детально разбираться, но выглядит как и все прочие ваши статьи на 5+.
«Полностью сжатое дерево», которое вы реализовали, вроде бы Patricia Tree называется (еще Radix Trie или PAT-trie).
В libdatrie достаточно большие накладные расходы на поддержку юникода: для каждого символа производится преобразование между «внешним» алфавитом и внутренним, и время поиска зависит линейно от количества интервалов во внешнем алфавите. Т.е. сравнение времени поиска не совсем 1 к 1 (вопрос о полезности этой фичи — отдельный).
К тому же в libdatrie каждому ключу сопоставляется целое число (это +4 байта к каждому ключу), а в вашей реализации нет, поэтому замеры памяти нечестные :)
Префиксные деревья, кстати, довольно плохо текстовую информацию все-таки сжимают. Самая эффективная схема хранения пока, насколько знаю, — это LOUDS-trie (в котором данные упаковываются с помощью разных битовых трюков). Есть MARISA-trie code.google.com/p/marisa-trie/, в котором строки хранятся в LOUDS-trie, а остатки не хранятся «как есть», а помещаются в LOUDS-trie следующего уровня (поэтому «рекурсивное trie») — на моих данных (3млн русских слов в utf8) marisa-trie тратит примерно в 10 раз меньше памяти, чем lidatrie. При этом каждому ключу в MARISA-trie тоже сопоставляется значение (4байтовое целое число), но это число не произвольное, а получается из ключа с использованием perfect hash-функции (которая вычисляет значение на основе положения ключа в дереве) — и поэтому эти значения памяти не требуют совсем.
Но MARISA-trie — это хак, причем я так и не понял, зачем он) Эта схема не поддерживает вставку новых значений и удаление существующих, а раз так, то MARISA-trie становится просто небыстрым не до конца минимизированным DAWG.
В DAWG текстовые данные занимают еще меньше места, т.к. строится минимальный автомат для данных строк. Те же 3 млн русских слов в utf8 в DAWG занимают меньше 3М с учетом значений (в 30+ раз меньше, чем в libdatrie) в реализации code.google.com/p/dawgdic/ — это DAWG, который основан на минимизации Double-Array Trie (той же структуры, что и в libdatrie).
Если интересно, еще обзор различных структур данных делал (применительно к питону, на английском, с уклоном в префиксные деревья): kmike.ru/python-data-structures/
В libdatrie достаточно большие накладные расходы на поддержку юникода: для каждого символа производится преобразование между «внешним» алфавитом и внутренним, и время поиска зависит линейно от количества интервалов во внешнем алфавите. Т.е. сравнение времени поиска не совсем 1 к 1 (вопрос о полезности этой фичи — отдельный).
К тому же в libdatrie каждому ключу сопоставляется целое число (это +4 байта к каждому ключу), а в вашей реализации нет, поэтому замеры памяти нечестные :)
Префиксные деревья, кстати, довольно плохо текстовую информацию все-таки сжимают. Самая эффективная схема хранения пока, насколько знаю, — это LOUDS-trie (в котором данные упаковываются с помощью разных битовых трюков). Есть MARISA-trie code.google.com/p/marisa-trie/, в котором строки хранятся в LOUDS-trie, а остатки не хранятся «как есть», а помещаются в LOUDS-trie следующего уровня (поэтому «рекурсивное trie») — на моих данных (3млн русских слов в utf8) marisa-trie тратит примерно в 10 раз меньше памяти, чем lidatrie. При этом каждому ключу в MARISA-trie тоже сопоставляется значение (4байтовое целое число), но это число не произвольное, а получается из ключа с использованием perfect hash-функции (которая вычисляет значение на основе положения ключа в дереве) — и поэтому эти значения памяти не требуют совсем.
Но MARISA-trie — это хак, причем я так и не понял, зачем он) Эта схема не поддерживает вставку новых значений и удаление существующих, а раз так, то MARISA-trie становится просто небыстрым не до конца минимизированным DAWG.
В DAWG текстовые данные занимают еще меньше места, т.к. строится минимальный автомат для данных строк. Те же 3 млн русских слов в utf8 в DAWG занимают меньше 3М с учетом значений (в 30+ раз меньше, чем в libdatrie) в реализации code.google.com/p/dawgdic/ — это DAWG, который основан на минимизации Double-Array Trie (той же структуры, что и в libdatrie).
Если интересно, еще обзор различных структур данных делал (применительно к питону, на английском, с уклоном в префиксные деревья): kmike.ru/python-data-structures/
Спасибо большое за ссылки, обязательно поизучаю на досуге! С libdatrie, кстати, я сравнение не делал… Относительно терминологии, мне больше нравится Radix Tree и русский вариант — дерево цифрового поиска.
упс, точно)
В libdatrie Double-Array используется, кстати, именно чтоб экономить память на узлах — в узлах не нужно хранить указатели. У вас там 3 указателя на узел (1 на текст и 2 для связи — это по 12 или 24 байта на узел в зависимости от разрядности ОС). По моим тестам (опять-таки те 3млн слов) Double-Array был эффективнее (по памяти) PAT-trie примерно в 2 раза, несмотря на то, что узлов больше.
Кроме того, хранение всего в линейных массивах должно ускорять работу, т.к. данные префетчатся в кеш процессора (а хождение по указателям для современных процессоров — это кошмар, т.к, нужно брать данные из разных участков памяти и пре-заполнение кеша не работает). По скорости самым быстрым считается HAT-trie, в котором структура данных спроектирована именно исходя из интересов современных процессоров, чтоб данные в кеш процессора попадали (но там гибрид trie и хэш-таблицы получился, и из-за этого всякие trie-операци медленные и корявые).
Кроме того, хранение всего в линейных массивах должно ускорять работу, т.к. данные префетчатся в кеш процессора (а хождение по указателям для современных процессоров — это кошмар, т.к, нужно брать данные из разных участков памяти и пре-заполнение кеша не работает). По скорости самым быстрым считается HAT-trie, в котором структура данных спроектирована именно исходя из интересов современных процессоров, чтоб данные в кеш процессора попадали (но там гибрид trie и хэш-таблицы получился, и из-за этого всякие trie-операци медленные и корявые).
Кстати, кто-нибудь может подскажет, где найти стандартные тестовые наборы для такого рода задач?
* google N-grams
* trec ( trec.nist.gov/data.html )
* собрание на amazon ( aws.amazon.com/datasets?_encoding=UTF8&jiveRedirect=1 )
* можно брать наборы url-ов c alexa.com
* archive.ics.uci.edu/ml/datasets.html
ну и т.д. ( см., например, www.quora.com/Data/Where-can-I-get-large-datasets-open-to-the-public )
* trec ( trec.nist.gov/data.html )
* собрание на amazon ( aws.amazon.com/datasets?_encoding=UTF8&jiveRedirect=1 )
* можно брать наборы url-ов c alexa.com
* archive.ics.uci.edu/ml/datasets.html
ну и т.д. ( см., например, www.quora.com/Data/Where-can-I-get-large-datasets-open-to-the-public )
Если вам действительно интересно, можете прочитать работу на близкую тему: ceur-ws.org/Vol-899/paper1.pdf
> И вот здесь все оказалось не так, как задумывалось. Сбалансированное двоичное дерево тратит на поиск в среднем примерно в два раза меньше времени, чем префиксное.
Разве должно было быть иначе?
Разве должно было быть иначе?
Таким образом, любой путь от корня дерева до некоторого его листа определяет ровно одну строку.
А если записать в дерево строку аб и аба, то оно ляжет как одна строка, хотя их 2.Нет?
А если записать в дерево строку аб и аба, то оно ляжет как одна строка, хотя их 2.Нет?
Sign up to leave a comment.
Сжатые префиксные деревья