#c #hash #byte #hashtable
#c #хэш #байт #хэш-таблица
Вопрос:
Я работаю над личным проектом, программой сжатия файлов, и у меня возникли проблемы со своим словарем символов. Мне нужно сохранить ранее встречавшиеся байтовые строки в структуру таким образом, чтобы я мог быстро проверить их существование и извлечь их. Я действовал в предположении, что хэш-таблица лучше всего подойдет для этой цели, поэтому мой вопрос будет относиться к хэш-функциям. Однако, если кто-то может предложить лучшую альтернативу хэш-таблице, я весь внимание. Все в порядке. Итак, проблема в том, что я не могу придумать хороший ключ хэширования для этих байтовых строк. Все, о чем я думаю, либо имеет очень неравномерное распределение, либо занимает слишком много времени. Вот список ситуаций, с которыми я работаю:
- Все байтовые строки будут иметь длину не менее двух байт.
- Максимальный размер хэш-таблицы будет равен 3839, и весьма вероятно, что она заполнится.
- Тестирование показало, что при любом заданном байте вероятность установки бита старшего порядка значительно меньше по сравнению с младшими семью битами.
- В противном случае байты в строке могут иметь любое значение от 0 до 255 (я работаю с необработанными байтовыми данными любого формата).
- Я работаю с языком C в среде UNIX. Я бы предпочел придерживаться стандартных библиотек, но это не обязательно должно быть переносимо на другие операционные системы. (Т.е. unistd.h подойдет).
- Безопасность не вызывает беспокойства.
- Скорость вызывает серьезную озабоченность.
- Размер не вызывает особого беспокойства, поскольку он НЕ будет записан в файл. Однако, учитывая потенциальный размер сохраняемых байтовых строк, во время сжатия может возникнуть проблема с объемом памяти.
Комментарии:
1. «Все, о чем я думаю» — Вместо того, чтобы делать это, вы могли бы поискать в Google «хэш-функцию»; в Интернете доступны обширные ссылки.
2. @Джим, вместо того, чтобы подумать? Вы серьезно только что предложили Google в качестве альтернативы мышлению?
3. @Blindy Я предложил использовать богатство человеческих знаний вместо того, чтобы пытаться изобретать велосипед, исходя из пределов личных усилий. Вся история разработки программного обеспечения (и человеческой культуры, если уж на то пошло) посвящена использованию того, что уже доступно. Размышление привело бы вас к пониманию этого вместо карикатурного описания того, что я написал. И по иронии судьбы, ваш собственный ответ отражает это — конечно, вы не изобретали попытки, и Пол не додумался бы до них, просто просмотрев все, что он мог придумать.
4. Постскриптум burtleburtle.net/bob/hash/doobs.html это прекрасный пример того, что поиск в Google может дать вам то, чего не может дать простое мышление. Конечно, учитывая эту предыдущую работу, к ней можно приложить много размышлений, но отказываться от исследований и просто довольствоваться тем, что можно придумать самостоятельно, некомпетентно, непрофессионально и непродуктивно.
Ответ №1:
Trie лучше подходит для такого рода вещей, потому что это позволяет вам хранить ваши символы в виде дерева и быстро анализировать его, чтобы соответствовать значениям (или отклонять их).
И в качестве бонуса, вам вообще не нужен хэш. Вы сохраняете / извлекаете / сравниваете всю последовательность сразу, при этом все еще занимая минимальный объем памяти.
Редактировать: И в качестве дополнительного бонуса, только со вторым разбором, вы можете искать последовательности, которые «близки» к вашей текущей последовательности, так что вы можете избавиться от последовательности и использовать предыдущую для них обоих, с некоторыми внутренними обозначениями для хранения различий. Это поможет вам лучше сжимать файлы, потому что:
- меньший словарь означает меньшие файлы, вы должны записать словарь в свой файл
- меньшее количество элементов может освободить место для хранения других, более редких последовательностей, если вы добавите ограничение по численности и нажмете на него с помощью большого файла.
Комментарии:
1. Хороший ответ! Хороший аргумент в пользу того, что хэш не нужен. Возможно, если Пол сможет хранить данные в виде числа, а не строки, у него мог бы быть упорядоченный список и выполнять в нем двоичный поиск.
2. На самом деле мне не нужно записывать словарь в файл; Я использую схему сжатия LZW. Тем не менее, trie действительно звучит привлекательно. Я собираюсь попробовать.