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

Question

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

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

• HAT-Trie (сочетание между синтаксическим деревом и Hashtable)
• JudyArray (сжатый п-арной деревом)
• Double Array Tree

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