Chained Hash Table и понимание Deflate

Question

В настоящее время я пытаюсь создать собственную реализацию Deflate в C #.

В настоящее время я пытаюсь реализовать часть "поиска по шаблону", в которой у меня есть (до) 32 КБ данных.и я пытаюсь найти самый длинный шаблон для моего ввода.

RFC 1951 , который определяет Deflate, говорит об этом процессе:

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

Я знаю, что такое хеш-функция, и знаю, что такое HashTable.Но что такое «цепочечная хеш-таблица» и как такая структура может быть спроектирована, чтобы быть эффективной (в C #) при обработке большого количества данных?К сожалению, я не понял, как работает структура, описанная в RFC.

Какую хеш-функцию я могу выбрать (что имело бы смысл)?

Заранее спасибо!

Answer 1

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

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

Многие реализации хеш-таблицы / словаря хранят обаключ и данные для каждого элемента.Не обязательно хранить ключ в таблице для DEFLATE, но это не повредит ничему, кроме использования немного большего объема памяти во время сжатия.

Некоторые реализации хеш-таблиц / словарей, такие как C ++ STL unordered_map, настаивают на том, чтокаждый элемент (ключ, данные), который они хранят, должен иметь уникальный ключ.Когда вы пытаетесь сохранить другой элемент (ключ, данные) с тем же ключом, что и некоторый более старый элемент, уже существующий в таблице, эти реализации удаляют старый элемент и заменяют его новым элементом.Это причиняет вред - если вы случайно используете C ++ STL unordered_map или аналогичную реализацию, ваш сжатый файл будет больше, чем если бы вы использовали более подходящую библиотеку, такую ​​как C ++ STL hash_multimap.Подобную ошибку может быть трудно обнаружить, так как результирующие (излишне большие) сжатые файлы могут быть правильно распакованы любым стандартным компрессором DEFLATE в файл бит-за-битом, идентичный исходному файлу.Несколько реализаций DEFLATE и других алгоритмов сжатия намеренно используют такую ​​реализацию, сознательно жертвуя размером сжатого файла, чтобы получить скорость сжатия.

Как сказал Ник Джонсон, хеш-функция по умолчанию, используемая в вашей стандартной «хеш-таблице» илиреализация словаря, вероятно, более чем адекватна.

http://en.wikipedia.org/wiki/Hashtable#Separate_chaining

Answer 2

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

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