Структура данных с O (1) время вставки и O (log m) поиска?

Question

Backstory (переходите от второго к последнему абзацу для части структуры данных): я работаю над алгоритмом сжатия (разновидности LZ77). Алгоритм сводится к тому, чтобы найти самое длинное соответствие между данной строкой и всеми строками, которые уже были замечены.

Чтобы сделать это быстро, я использовал хеш-таблицу (с отдельной цепочкой) , как рекомендовано в спецификации DEFLATE : я вставляю каждую строку, видимую до сих пор, по одной за раз (по одной на входной байт) с m слотами в цепочке для каждого хеш-кода. Вставки выполняются быстро (постоянное время без условной логики), но поиск идет медленно, потому что мне нужно посмотреть на O ( m ) строк, чтобы найти самое длинное совпадение. Поскольку в типичном примере я выполняю сотни тысяч вставок и десятки тысяч поисков, мне нужна высокоэффективная структура данных, если я хочу, чтобы мой алгоритм работал быстро (в настоящее время он слишком медленный для m > 4; Я бы хотел м ближе к 128).

Я реализовал особый случай, когда m равен 1, при котором быстрые удары очень предлагают только среднюю компрессию. Сейчас я работаю над алгоритмом для тех, кто предпочел бы улучшенную степень сжатия по сравнению со скоростью, где чем больше m , тем лучше сжатие (в какой-то степени, очевидно). К сожалению, мои попытки пока слишком медленны для скромного увеличения степени сжатия, так как m увеличивается.

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

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

Спасибо!

Answer 1

Вас может заинтересовать эта структура поиска совпадений:

http://encode.ru/threads/1393-A-proposed-new-fast-match-searching-structure

Это O (1) время вставки и O (м) поиск. Но (m) во много раз ниже стандартной хэш-таблицы для эквивалентного результата поиска совпадения. Например, при m = 4 эта структура получает эквивалентные результаты, чем хеш-таблица с 80 зондами.

Answer 2

Возможно, вы захотите использовать trie (дерево префиксов) вместо хеш-таблицы.

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

Answer 3

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

Если вы выполняете все вставки перед поиском, вы можете добавить бит для каждого сегмента, который говорит, отсортирована ли цепочка для этого сегмента.При каждом поиске вы можете проверить бит, чтобы увидеть, отсортирован ли сегмент.Если нет, вы бы отсортировали ведро и установили бит.После сортировки сегмента каждый поиск имеет значение O (lg m).

Если вы чередуете вставки и поиски, вы можете иметь 2 списка для каждого сегмента: один отсортированный, а другой - нет.Вставки всегда идут в несортированный список.Поиск сначала проверяет отсортированный список, и только если его там нет, он просматривает несортированный список.Когда он будет найден в несортированном списке, вы удалите его и поместите в отсортированный список.Таким образом, вы платите только за сортировку нужных вам предметов.