Асимптотически быстрая ассоциативная матрица с низкими требованиями к памяти

Question

Хорошо, попытки были вокруг некоторое время.Типичная реализация должна дать вам O (m) операции поиска, вставки и удаления независимо от размера n набора данных, где m - длина сообщения.Однако эта же реализация занимает 256 слов на входной байт, в худшем случае.

Другие структуры данных, в частности хеширование, обеспечивают ожидаемый O (m) поиск, вставку и удаление, а в некоторых реализациях даже есть постояннаявремя поиска.Тем не менее, в худшем случае подпрограммы либо не останавливаются, либо не занимают O (нм) времени.

Вопрос в том, существует ли структура данных, которая обеспечивает O (m) поиск, вставку и удаление времени при сохраненииобъем памяти, сравнимый с хешированием или поисковыми деревьями?

Можно сказать, что меня интересует только худшее поведение, как во времени, так и в пространстве.

Answer 1

Пробовали ли вы попытки Патрисии (псевдоним критбит или радикс)? Я думаю, что они решают проблему космоса в худшем случае.

Answer 2

По моему опыту, есть три реализации, которые, я думаю, могли бы удовлетворить ваши требования:

• HAT-Trie (комбинация между trie и hashtable)
• JudyArray (сжатое n-арное дерево)
• Double Array Tree

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

Answer 3

Я не думаю, что есть причина беспокоиться о худшем случае по двум причинам:

1. У вас никогда не будет больше общих активных ветвей в сумме всех узлов Trie, чем в суммеразмер хранимых данных.
2. Единственный раз, когда размер узла становится проблемой, - это большой размах данных, которые вы сортируете / храните.Мнемоника была бы примером этого.Если вы полагаетесь на три в качестве механизма сжатия, то хеш-таблица не будет лучше для вас.

Если вам нужно сжимать и у вас мало / нет общих подпоследовательностей, то вам нужно разработать алгоритм сжатия на основе конкретной формы данных, а не на общих предположениях о строках.Например, в случае полностью / очень заполненного набора мнемонических данных структура данных, которая отслеживает «дыры» в данных, а не в заполненных данных, может быть более эффективной.

При этом можно заплатитьдля вас, чтобы избежать фиксированного размера узла Trie, если у вас есть умеренное разветвление.Вы можете сделать каждый узел дерева хеш-таблицей.Начните с небольшого размера и увеличивайте по мере вставки элементов.В худшем случае вставка будет c * m, когда каждая хеш-таблица должна быть реорганизована из-за увеличения, где c - число возможных символов / уникальных атомарных элементов.

Answer 4

Существует структура, известная как массив суффиксов.Я не могу вспомнить исследования в этой области, но я думаю, что они получили чертовски близко к O (m) времени поиска с этой структурой, и это гораздо более компактно, чем ваши типичные методы индексации на основе дерева.

Книга Дэна Гасфилда - Библия строковых алгоритмов.