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

Описание тега Вопросы с тегом
В информатике дерево, также называемое цифровым деревом, а иногда и дерево счисления или дерево префиксов (поскольку их можно искать по префиксам), представляет собой упорядоченную древовидную структуру данных, которая используется для хранения динамического набора или ассоциативного массива, в котором обычно находятся ключи. струны
3 ответа

Найти единственного ближайшего соседа, используя дерево префиксов в O(1)?

Я читаю статью, где они упоминают, что им удалось найти единственного ближайшего соседа в O(1), используя префиксное дерево. Я опишу общую проблему, а затем классическое решение и, наконец, предлагаемое решение в статье: Проблема: учитывая список би…
24 июн '13 в 18:05
0 ответов

Префикс результатов поиска с использованием структуры данных Trie в Java

Я застрял в этой проблеме с задачей получения результата с префиксом, так как строка, введенная до сих пор, отображается после того, как пользователь вводит каждый символ. Прикрепленный код работает нормально с большинством тестовых случаев, но я не…
24 апр '18 в 12:20
2 ответа

Как освободить память в дереве префиксов? (ANSI C)

Я пытался освободить память в функции dict_free(), но она не работает, и я не знаю почему. Я что-то пропустил? Не могу понять, что не так. Редактировать: если я вызываю free () в dict_free(), я ожидаю увидеть, что указатель free'd указывает на NULL,…
22 сен '10 в 22:30
2 ответа

Алгоритм для сопоставления двух шаблонных строк

Мне нужно написать алгоритм для самого длинного совпадения префикса / суффикса с двумя образцами, сложность которого равна O(n+m1+m2), где n - длина строки, а m1, m2 - длины pattern1 и pattern2 соответственно. Пример: если строка - "OBANTAO", а Patt…
17 фев '14 в 20:22
3 ответа

Выбор подходящей структуры данных (хэш-таблица или дерево суффиксов) для индексации очень большого набора похожих строк

У меня есть большой набор строк, порядка ~10^12 или около того, и мне нужно выбрать подходящую структуру данных, чтобы при наличии строки я мог получить и связать целочисленное значение в чем-то вроде O(log(n)) или O(m) время, где "n" - длина списка…
22 окт '12 в 02:19
1 ответ

Коды переменной длины

Предположим, что нам дали, что наш двоичный код без префиксов имеет 11 кодовых слов длиной 4 и 2 кодовых слова длины 2. Мы просим придумать пример для этого, но как мы можем сделать 11 кодовых слов, когда длина кода равна 4, и мы можем использовать …
18 сен '13 в 00:29
1 ответ

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

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

Кто-нибудь имеет или знает постоянный префикс три в F#?

Производительность F# и Map и Set довольно не хватает для моего конкретного приложения. Кажется, хороший префикс tree увеличит производительность моего интерпретатора, особенно с точки зрения поиска символов по имени. Единственное предостережение за…
09 июл '12 в 13:21
2 ответа

C++ FP-дерево или префиксное дерево

У меня есть несколько последовательностей, как эти (100) - (102) - (103) - (104,106) - (108) (101) - (103) (102) - (106) есть какая-то эффективная реализация префиксного дерева или fp-дерева или аналогичного в C + +?
03 дек '11 в 13:25
1 ответ

Каково время выполнения моего алгоритма?

Я пишу алгоритм, который сначала примет файл конфигурации с различными конечными точками и связанный с ними метод, как показано ниже: /guest guestEndpoint /guest/lists listEndpoint /guest/friends guestFriendsEndpoint /guest/X/friends guetFriendsEndp…
22 июл '17 в 18:50
1 ответ

Какая структура данных самая быстрая, чтобы найти наиболее подходящий префикс?

Контекст: я работаю над анализатором для строк useragent ( Yauaa), и в рамках этого анализа я хочу сделать обоснованное предположение, о какой марке устройства следует сообщать. У меня есть реализация, которую мне нужно переписать, чтобы она была на…
19 ноя '18 в 09:20
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
2 ответа

Подсчет количества слов при разборе дерева Trie

Я пытаюсь решить проблему автозаполнения клавиатуры, описанную здесь. Задача состоит в том, чтобы рассчитать, сколько нажатий клавиш требует слово, учитывая некоторые словарь и правила автозаполнения. Например, для словаря: data = ['hello', 'hell', …
08 ноя '16 в 21:15
2 ответа

Основной вопрос реализации дерева префиксов

Я реализовал базовое дерево префиксов или "Trie". Три состоит из таких узлов: // pseudo-code struct node { char c; collection<node> childnodes; }; Скажем, я добавляю следующие слова в мой список: "Яблоко", "Ковчег" и "Кошка". Теперь, когда я с…
14 июн '11 в 18:42
1 ответ

Как сгенерировать код префикса Хаффмана?

Я работаю над программой на C++ и над моей группой, и я не могу понять логику того, как генерировать префиксный код, используя обход inOrder. У нас есть дерево префиксного кода, и мы хотим сгенерировать из него коды. Поскольку у нас возникают пробле…
22 окт '15 в 22:48
1 ответ

Управление реализацией Trie для получения найденных элементов в массиве

Я нашел эту реализацию из Code Review, она работает отлично, я уже как-то изменил ее, чтобы соответствовать потребностям моей программы, теперь я хочу манипулировать find() функция, чтобы я мог иметь результаты в массиве. Благодарю. Вот код класса: …
20 май '15 в 09:59
1 ответ

В чем преимущество обобщенного дерева суффиксов перед деревом префиксов?

Будет очень полезно, если кто-то объяснит причину в мельчайших подробностях и в каком сценарии один более выгоден, чем другой. Заранее спасибо!!
21 мар '14 в 05:36
1 ответ

Ошибка сегментации при добавлении в дерево префиксов

Я пытаюсь написать функцию для ввода слов из текстового файла в дерево префиксов, но это продолжает давать мне ошибку сегментации int wordCount = 0; typedef struct node { bool isWord; struct node* children[26]; }node; struct node* newNode(struct nod…
26 фев '14 в 04:38
3 ответа

Реализация Trie для поддержки автозаполнения в Python

Я пытаюсь реализовать структуру данных, которая поддерживает автозаполнение на веб-сайте. Мне удалось реализовать итеративную версию Trie. Он поддерживает два основных метода добавления и поиска в Trie. Однако теперь мне нужно добавить метод, которы…
04 сен '17 в 14:00
1 ответ

Какой поиск быстрее, бинарный поиск или дерево префиксов?

Предположим, у меня есть список строк и префиксное дерево этих строк, и я хотел бы найти строку по заданному ключу, какая из них быстрее? бинарный поиск или поиск по префиксу дерева? Почему и во сколько сложность? Спасибо!
24 июн '13 в 10:20