Описание тега radix-tree

Радикс-дерево - это дерево, в котором каждый узел с одним дочерним элементом объединяется со своим дочерним элементом в качестве формы оптимизации пространства.
1 ответ

Почему в ядре Linux radix_tree_preload возвращается с отключенным выгрузкой

Я просматривал статью о реализации ядра ядра Linux, ссылка на статью упомянута ниже: http://lwn.net/Articles/175432/ В этой статье упоминается, что radix_tree_preload выделяет достаточно памяти, чтобы последующая вставка в дерево не завершилась неуд…
16 дек '13 в 13:51
2 ответа

Расширение дерева до большего количества листьев

Я должен сделать словарь, используя попытки, количество букв в алфавите увеличится с 26 до 120, и, следовательно, число листовых узлов увеличится в геометрической прогрессии. Какие оптимизации можно использовать, чтобы время поиска, вставки и удален…
24 мар '16 в 23:52
1 ответ

Как построить Radix Tree в JavaScript?

Вдохновленный предсказанием следующего слова iOS7 iMessage, я решил попытаться написать скрипт, который на основе пользовательского ввода узнает, какие слова / буквы, скорее всего, хотят завершить текущее слово пользователя или какое слово, скорее в…
11 фев '15 в 06:43
1 ответ

Проблема со списком Python для сложных типов

Ниже приведен фрагмент кода в Python, который хранит префиксы IP в основополагающем дереве, а затем связывает IP и ASN в словаре, если IP принадлежит префиксу. Я хотел бы узнать все различные ASN для конкретного префикса. Более подробная информация …
18 сен '15 в 09:37
1 ответ

Разыменование указателя на неполный тип (основное дерево)

У меня большие проблемы с моим определением структуры. Я пробовал несколько разных способов их определения, но не могу избавиться от ошибки. У меня, вероятно, также есть множество других проблем с кодом, но я не могу исправить их, не найдя их, запус…
27 апр '15 в 14:30
1 ответ

Значение термина "Radix" в дереве Radix

Хотя трудно найти единодушное определение "дерева радиксов", большинство принятых определений дерева корней указывают, что это сжатое дерево префиксов. Что я пытаюсь понять, так это значение термина "основание" в данном случае. Почему сжатые префикс…
17 окт '16 в 13:14
4 ответа

В чем разница между структурами данных trie и radix trie?

Структуры данных trie и radix trie - это одно и то же? Если они одинаковы, то в чем смысл radix trie (AKA Patricia trie)?
1 ответ

Поменять местами (или упростить) декартово произведение?

Чтобы упростить, но и усложнить задачу, я попытался реализовать концепцию " комбинированных / кратких тегов ", которая в дальнейшем расширится до нескольких основных форм тегов. В этом случае теги состоят из (одного или нескольких) "под-тега (ов)", …
31 дек '14 в 18:18
1 ответ

Слияние двух двоичных файлов

Я хочу объединить две структуры дерева, но лучшая сложность, о которой я могу думать, это Получить список значений из другого дерева: O(n), n - количество узлов в дереве. Вставьте все значения из списка вводной цели: n * O(m), m - длина ключа. Учиты…
18 дек '17 в 20:57
2 ответа

Патриция Три для быстрого поиска адреса IPv4 и спутниковых данных

Я пишу программу на C++, которая требует, чтобы IP-адреса (все IPv4) были быстро найдены и сохранены. Каждый IP-адрес имеет данные, связанные с ним. Если он уже существует в дереве, я намерен объединить данные IP-адреса в дереве с данными новых адре…
0 ответов

Сброс дерева корней на диск

Я реализовал основополагающее дерево в Scala. Используя список слов, я могу успешно создать дерево в памяти. Проблема в том, что я пытаюсь проиндексировать очень большой файл, содержащий около 30 миллионов слов, и дерево не помещается в памяти. Пред…
16 мар '18 в 19:28
1 ответ

Как пройти по дереву кэша страниц (основному дереву) адресного пространства файла в ядре Linux

Мне нужно получить статистику кэша страниц открытого файла. В файловой структуре есть указатель address_space (f_mapping), который, в свою очередь, имеет корень корневого дерева, называемого page_tree. Мне нужно пройти по этому дереву, чтобы получит…
24 апр '15 в 12:59
3 ответа

Какова пространственная сложность радикального дерева?

Я всегда был обеспокоен использованием пространства радикс-дерева, но я не нашел никаких полезных обсуждений по этому вопросу. Теперь давайте предположим, что у нас есть реализация основанного на ядре дерева, аналогичная linux radix-tree.c, которая …
13 дек '13 в 18:14
3 ответа

Слова, содержащие как минимум 2 общие буквы

Строка называется 2-согласованной, если каждое слово имеет как минимум 2 буквы, общие со следующим словом. Например "Атом другой эпохи" [atom имеет a а также t общего с another а также another имеет e а также a общего с era (ответ не уникален). Преж…
16 июл '15 в 04:59
1 ответ

Поиск строк в адаптивном радикальном дереве

Я просматривал исследовательскую работу "Дерево адаптивных корней: индексирование ARTful для баз данных основной памяти", у меня был вопрос о том, как вы можете сопоставить строки с ключами узла. Например: если бы у меня было слово: Iota, которое бы…
19 ноя '17 в 22:18
1 ответ

Самый длинный поиск префикса с диска

В настоящее время у меня есть некоторая реализация, которая выполняет Longest Prefix Lookup (LPM) из структуры данных радикального дерева. Эта структура данных содержит префиксы IP (основополагающее дерево с максимальной глубиной 128 бит), и в насто…
18 фев '18 в 12:22
0 ответов

Сохраняет ли основание три строки всю строку в узле?

Сегодня я программировал основополагающее дерево в классе Java. В классе мы узнали, что каждый узел в основном дереве хранит строку. Например, если родительский узел узла B является узлом A, узел A хранит "корову", а узел B хранит "коров" Тем не мен…
26 ноя '17 в 15:47
4 ответа

Оценка скорости / использования памяти для различных структур данных

Я пытаюсь решить, какую структуру данных использовать для следующего. Допустим, у меня есть около 10 миллионов ключей, которые содержат указатели на уникальные объекты, содержащие некоторые данные. Ключи UUID представляют собой 16-байтовые двоичные …
1 ответ

Упорядочение дочерних узлов в дереве trie / radix

Когда я просматриваю Трисы и радикальные деревья, такие как http://en.wikipedia.org/wiki/Compact_prefix_tree и http://en.wikipedia.org/wiki/Trie, я не вижу конкретной информации о лексикографическом упорядочении дети узла. так, например, в этом прим…
16 янв '14 в 03:28
1 ответ

Три против Radix Tree против Патрисии Три

Как я понимаю (также отсюда), сложность памяти этих DS можно заказать как Trie > Radix > Patricia. Но как насчет сложности времени? Я предполагаю, что они почти одинаковы. Если упомянуть мою проблему, я хочу сделать много поисковых запросов с префик…