Описание тега patricia-trie
Patricia trees are a term for a specialised kind of Radix tree.
A radix tree is a space-optimized trie data structure where each node with only one child is merged with its child. This means every internal node has at least two children. Unlike in regular tries, edges can be labeled with sequences of characters as well as single characters. This makes them much more efficient for small sets and for sets of strings that share long prefixes.
0
ответов
LevelDB и триоподобные структуры, сохраненные в них, улучшают обход
В настоящее время я работаю над реализацией Modified PatriciaTree в Java-реализацию. Я нашел реализацию ethereum здесь: https://github.com/ethereumj/ethereumj/tree/master/ethereumj-core/src/main/java/org/ethereum/trie. Я хочу сохранить сгенерированн…
07 авг '18 в 10:41
2
ответа
Реализация Patricia Trie для использования в качестве словаря
Я пытаюсь реализовать Патрицию Три с помощью методов addWord(), isWord(), а также isPrefix() как средство для хранения большого словарного запаса слов для быстрого поиска (включая поиск по префиксу). Я прочитал о концепциях, но они просто не разъясн…
09 мар '10 в 03:20
4
ответа
Поиск префикса по основному дереву /patricia trie
В настоящее время я использую основную ветвь дерева / Патрисии (как бы вы это ни называли). Я хочу использовать его для поиска префиксов в словаре на жестком оборудовании. Предполагается, что он будет работать более или менее как автозаполнение, т.е…
27 апр '09 в 18:09
2
ответа
Расширение дерева до большего количества листьев
Я должен сделать словарь, используя попытки, количество букв в алфавите увеличится с 26 до 120, и, следовательно, число листовых узлов увеличится в геометрической прогрессии. Какие оптимизации можно использовать, чтобы время поиска, вставки и удален…
24 мар '16 в 23:52
1
ответ
Как построить Radix Tree в JavaScript?
Вдохновленный предсказанием следующего слова iOS7 iMessage, я решил попытаться написать скрипт, который на основе пользовательского ввода узнает, какие слова / буквы, скорее всего, хотят завершить текущее слово пользователя или какое слово, скорее в…
11 фев '15 в 06:43
1
ответ
Значение термина "Radix" в дереве Radix
Хотя трудно найти единодушное определение "дерева радиксов", большинство принятых определений дерева корней указывают, что это сжатое дерево префиксов. Что я пытаюсь понять, так это значение термина "основание" в данном случае. Почему сжатые префикс…
17 окт '16 в 13:14
4
ответа
В чем разница между структурами данных trie и radix trie?
Структуры данных trie и radix trie - это одно и то же? Если они одинаковы, то в чем смысл radix trie (AKA Patricia trie)?
05 фев '13 в 12:58
2
ответа
Патриция Три для быстрого поиска адреса IPv4 и спутниковых данных
Я пишу программу на C++, которая требует, чтобы IP-адреса (все IPv4) были быстро найдены и сохранены. Каждый IP-адрес имеет данные, связанные с ним. Если он уже существует в дереве, я намерен объединить данные IP-адреса в дереве с данными новых адре…
03 окт '12 в 13:41
2
ответа
Определите, является ли одна строка префиксом другой
Я написал простую функцию, которая определяет, является ли str1 префиксом str2. Это очень простая функция, которая выглядит так (в JS): function isPrefix(str1, str2) // determine if str1 is a prefix of a candidate string { if(str2.length < str1.l…
03 сен '13 в 01:35
3
ответа
Алгоритм / шаги по поиску длинного префикса поиска в Патрисии Три
Я реализую попытки Патрисии для поиска префикса IP, я мог бы заставить код работать на полное совпадение ключей, но столкнулся с проблемами с поиском префиксов, когда есть ключи, которые являются префиксами других ключей, например: 1.2.3.0 1.2.0.0 М…
26 май '09 в 18:07
0
ответов
Как получить значение в каждой функции keyup, используя этот код для структуры Trie?
Как я могу использовать функцию keyup для этой функции, чтобы получить значение? если я нажму "m", все значения m будут показаны, а если я нажму s, все значения "s" будут показаны ниже. Спасибо <body> <div style="text-align: center;" class=…
13 фев '18 в 06:01
1
ответ
Реализация Python Патриция пытается
Оглядываясь на реализации Python для попыток, просто чтобы я мог понять, что они из себя представляют и как они работают, я натолкнулся на пример Патрисии Джастина Пила и нашел его очень поучительным: он достаточно прост для того, чтобы новенький и …
25 июн '10 в 22:47
1
ответ
Как хранить много долгот / широт на устройстве Android
Я пытаюсь написать приложение для Android, которое имеет базу данных приблизительно 2000 долгот и широт, которые эффективно жестко запрограммированы. Я предполагаю, что после установки моего приложения я могу поместить эту информацию в базу данных S…
26 июл '10 в 17:51
0
ответов
Сохраняет ли основание три строки всю строку в узле?
Сегодня я программировал основополагающее дерево в классе Java. В классе мы узнали, что каждый узел в основном дереве хранит строку. Например, если родительский узел узла B является узлом A, узел A хранит "корову", а узел B хранит "коров" Тем не мен…
26 ноя '17 в 15:47
1
ответ
Патриция Три
Я пытаюсь написать простую поисковую систему, которая использует структуру данных trie (узел содержит только один символ), чтобы найти слова. И когда он получает команду "сжатия" от пользователя, дерево должно превратиться в форму дерева событий (уз…
30 июн '13 в 07:55
1
ответ
Три против Radix Tree против Патрисии Три
Как я понимаю (также отсюда), сложность памяти этих DS можно заказать как Trie > Radix > Patricia. Но как насчет сложности времени? Я предполагаю, что они почти одинаковы. Если упомянуть мою проблему, я хочу сделать много поисковых запросов с префик…
29 мар '16 в 09:57
1
ответ
Функция STLish lower_bound для Radix/Patricia Trie
В последнее время я изучаю попытки Патриции и работаю с действительно хорошей реализацией C++, которую можно использовать в качестве сортированного STL-ассоциативного контейнера. Попытки Патрисии отличаются от обычных двоичных деревьев, потому что к…
20 сен '10 в 14:06
2
ответа
Использование (несжатого) Trie
Я изучаю различные структуры данных с префиксным поиском, такие как Tries и Radix Tries (Patricia Tries). На данный момент у меня есть четкое понимание как попыток, так и основательных попыток, а также хорошее понимание их вариантов использования. Т…
16 сен '14 в 17:45
1
ответ
Proto-Buf.Net и сериализация
У меня проблема с сериализацией объекта с использованием protobuf.net. Я использовал его в других классах, и он работает очень хорошо, но, используя его, это не так. Не могли бы вы помочь мне сказать, почему. Благодарю. Я хочу использовать protobuf,…
21 июн '12 в 08:33
4
ответа
Что автор nedtries подразумевает под "на месте"?
I. Только что реализовал своего рода побитовое преобразование (на основе nedtries), но мой код много распределяет память (для каждого узла). Вопреки моей реализации, nedtries, как утверждают, являются быстрыми, среди прочего, из-за их небольшого кол…
14 янв '11 в 14:29