Я думаю, что эффективная база данных будет модифицирована trie , с двунаправленными ссылками [может идти от листьев к корню и восстанавливать слово], и каждый конечный узел будет иметь дополнительное «значение» поле.
Вам также понадобится мультикарта [т.е. карта, в которой каждое значение представляет собой набор адресов].
Ключи будут расположены в виде дерева, а набор значений будет основан на хэше.
[в джаве, это должно быть что-то вроде TreeMap<Integer,HashSet<Node>>]
Псевдокод: [ну, очень псевдо… он просто показывает общие идеи для каждой операции].
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's 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.
Сложность:
пусть n будет количеством строк, k будет максимальным значением и S длиной строки.
Вставка: O (S) [Три вставки O (S)]. Наименьший элемент (1) в карте может быть кэширован, и, следовательно, доступ к нему можно получить в точке O (1).
Инкремент: O (S + logk) : найти строку в дереве O (S), найти соответствующий ключ O (logk), удалить элемент из хеш-набора O ( 1), нахождение следующего элемента в дереве также O (logk) [фактически может быть O (1), для skip-list based map], и вставка значения - O (1). Обратите внимание, что, связав узел с соответствующим ключом на карте, сложность может быть даже улучшена до O (S) , поскольку поиск фактически не требуется.
Найти: O (S) : просто найти в дереве и вернуть значение.
Выберите: O (S * n) : в худшем случае вам нужно извлечь все элементы, что заставляет вас повторять весь набор, чтобы найти все слова.
Макс .: O (logk + S) : найти ключ в отсортированной карте, восстановить слово.
РЕДАКТИРОВАТЬ: Обратите внимание, что здесь, я предполагаю, для find (i) вы хотите, чтобы i * i отдельный самый большой элемент. Если это не так, вам нужно будет немного изменить набор и использовать мультикарту, которая позволяет дублировать ключи [вместо набора в качестве значения]. Это сделает все операции на основе дерева O (logn) вместо O (logk), по-прежнему эффективными, на мой взгляд ...