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

Ответ 1

Комбинация сбалансированного дерева (например, красно-черного дерева) и дерева суффиксов (или массив суффиксов).

• Сбалансированное дерево: операция 1, 2 (реализована как remove + insert), 3 и 5.
• Дерево суффикса: операция 4.

ПРИМЕЧАНИЕ. Хэш-таблица не сможет эффективно поддерживать работу.

Я думаю, вам будет трудно реализовать дерево суффикса. Вы могли бы использовать Mark Nelson С++ для реализации алгоритма Ukkonen, но он имеет утечки памяти и по сути является одноэлементным, поэтому вам нужно его очистить перед тем, как быть готовым к производству. Даже после того, как вы его исправите, вам нужно будет настроить его так, чтобы он работал с вашей "другой" структурой данных (которая является сбалансированным деревом в моем предложении) вместо одной большой простой строки.

Если вы выполняете операцию 1 чаще, чем операцию 4, и/или можете жить с линейным управлением 4, я рекомендую вам пропустить всю сложность с деревом суффикса и просто пересечь структуру данных линейно.

Ответ 2

Для первых трех операций хэш-таблица может быть хорошей идеей.

Для 4-й операции (выберите часть ключа) вам может потребоваться написать хеш-функцию по-разному. Да, хеш-функция, которая использовалась для поиска/вычисления хэш-значения из заданного ключа. Поскольку вы хотите поддерживать частичное совпадение, а ваш ключ - строка, вы можете использовать суффикс-дерево или trie.

Для 5-й операции (с максимальным элементом) вы можете захотеть сохранить кучу или отсортированный Linked-list (или skip-list), который взаимодействует с хэш-таблицей.

Вам также нужно будет увидеть различные варианты использования и найти, какая операция должна быть оптимизирована. Для exa: Если у вас много запросов на операцию part_of_key, вы должны использовать структуру суффикса-дерева/LC-trie, и это даст хорошие результаты. Однако операция поиска может быть не быстрой, так как вместо постоянного поиска потребуется O (logN).

Подводя итог, вам необходимо интегрировать дерево хеш-таблицы, кучи и суффикса для достижения всех операций.

Ответ 3

В то время как точный ответ зависит от частоты ваших операций, ваш список параметров должен включать массив суффиксов

Ответ 4

Я думаю, что лучше всего выиграть три с несколькими ярлыками.

1-3 уже поддерживаются trie как можно быстрее (длина ключа).

Для 4 я бы добавил дополнительную таблицу из 256 элементов ко всем трем узлам, которые могут быть введены из этого символа. Таким образом, я могу быстро найти части строки, не создавая и не сохраняя суффиксы, как в дереве суффиксов.

В течение 5 я добавил бы связанный список на листах, которые будут обновляться при сортировке данных. Возможно, вам понадобится еще одна ссылка на главу списка и обратные ссылки в trie, чтобы найти правильное значение и получить ключ.

С этими дополнениями сложность памяти не меняется, поскольку она ограничена количеством узлов trie. Однако время, в которое вставляются данные, может измениться из-за неэффективного вида связанного списка.

Окончательная структура, вероятно, должна быть названа хэш-листом-trie. Но я бы не хотел, чтобы это зверь реализовывал.

Ответ 5

Я думаю, что эффективная база данных будет измененной trie, с двунаправленными ссылками [может идти от листьев до корня и восстановите слово], и каждое завершение node будет иметь дополнительное поле "значение".
Вам также понадобится мультимап (т. карта, в которой каждое значение представляет собой набор адресов].
Ключи будут упорядочены в виде дерева, а набор значений будет основан на хэше. [в jave, это должно быть что-то вроде TreeMap<Integer,HashSet<Node>>]

Псевдокод: [ну, очень псевдо... он просто показывает общие идеи для каждого op].

Insert(key):
1. Insert a word into the trie
2. add the value `1` to the terminating node.
3. add the terminating field to the multimap [i.e. map.add(1,terminating_node_address)]
Increment(key):
1. read the word in the trie, and store the value from the terminating node as temp.
2. delete the entree (temp,terminating_node_address) from the multimap.
3. insert the entree (temp+1,terminating_node_address) to the multimap.
4. increase the value of the terminating node address by 1.
Find(key):
1. find the terminating node for the key in the trie, return its value.
Select(part_of_key):
1. go to the last node you can reach with part_of_key.
2. from this node: do BFS and retrieve all possible words [store them in an empty set you will later return].
Max(i):
1. find the i'th biggest element key in the multimap.
2. choose an arbitrary address, and return get the relevant terminating word node.
3. build the string by following the uplinks to the root, and return it.

Сложности:
let n - число строк, k - максимальное значение, а S - длина строки.
Вставка: O (S) [trie insertion - O (S)]. Наименьший элемент (1) на карте может быть кэширован и, следовательно, может быть доступен в O (1).
Приращение: O (S + logk): найти строку в trie - это O (S), найти соответствующий ключ O (logk), удаление элемента из хэш-набора - O (1), найти следующий элемент в дереве также O (logk) [может быть O (1) на самом деле, для skip-list основанная на карте] и вставка значения O (1). Обратите внимание, что, связывая node с соответствующим ключом на карте, сложность может быть даже улучшена до O (S), так как поиск не требуется.
Найти: O (S): просто найдите в trie и верните значение.
Выбрать: O (S * n): в худшем случае вам нужно получить все элементы, что заставляет вас перебирать все три, чтобы найти все слова.
Макс: O (logk + S): найдите ключ в сортированной карте, восстановите слово.

РЕДАКТИРОВАТЬ: Обратите внимание, что здесь я предположил, что для find (i) вам нужен i'th отличный большой элемент. Если это не так, вам нужно будет немного изменить бит набора и использовать мультимап, который позволяет дублировать ключи [вместо этого как значение]. Это сделает все операции на основе дерева O (logn) вместо O (logk), по-прежнему эффективными по моему мнению...