Хешировать строку байтов - PullRequest
Новая
       6

Хешировать строку байтов

2 голосов
/ 10 мая 2011

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

  1. Все строки байтов будут иметь длину не менее двух байтов.
  2. Максимальный размер хеш-таблицы будет равен 3839.и весьма вероятно, что он заполнится.
  3. Тестирование показало, что для любого заданного байта бит старшего разряда будет значительно менее вероятным по сравнению с младшими семью битами.
  4. В противном случае байты в строке могут иметь любое значение от 0 до 255. (Я работаю с необработанными байтовыми данными любого формата).
  5. Я работаю с языком C в среде UNIX.Я бы предпочел придерживаться стандартных библиотек, но он не должен быть переносимым на другие ОС.(IE unistd.h в порядке).
  6. Безопасность не имеет значения.
  7. Скорость имеет большое значение.
  8. Размер не имеет большого значения, так какон НЕ будет записан в файл.Однако, учитывая потенциальный размер хранимых байтовых строк, во время сжатия может возникнуть проблема с объемом памяти.

1 Ответ

5 голосов
/ 10 мая 2011

A trie лучше подходит для такого рода вещей, поскольку позволяет хранить ваши символы в виде дерева и быстро анализировать их на соответствие значениям (или отклонять их).

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

Редактировать: И в качестве дополнительного бонуса, с помощью только второго анализа, вы можете искать последовательности, которые «близки» к вашей текущей последовательности, так что вы можете избавиться от последовательности и использовать предыдущую для них обоих, с некоторыми внутренними обозначениями для хранения различий. Это поможет вам лучше сжать файлы, потому что:

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