Я пытаюсь написать (идеальную) хеш-таблицу для сжатия отображения от unicode codepoint names to their codepoint number (отображение второго столбца в первый столбец). Как вы можете видеть, возможные входы очень ограничены, на самом деле в алфавите есть ровно 38 символов: AB...YZ, 0...9, - и пространство. Кроме того, существует много (подстроки) повторения, DIGIT ZERO, DIGIT ONE, ..., LATIN CAPITAL LETTER A, LATIN CAPITAL LETTER B и т.д.Эффективная хеш-функция для буквенно-цифровых строк с низкой энтропией
Идеальный хэш-таблицы вычисляется путем выбора семян S, а затем пытается построить идеальный хэш-таблицу (в некотором роде) хешер на S. Если таблица не может быть выполнена, она повторяет попытку с новым семенем. Наличие большого количества столкновений обычно требует большего количества попыток, потому что алгоритм делает все более подходящим.
Результатом этого является мой входной домен с низкой энтропией, и для создания таблицы требуется много попыток с простыми хеш-функциями, такими как DJB2; лучшие хешеры, такие как FNV, работают достаточно хорошо, но более сложные и медленные функции, такие как SipHash, по-видимому, требуют в среднем еще меньше попыток.
Поскольку это полностью статическое и предварительно вычисленное, я не слишком беспокоюсь о качестве для качества (то есть безопасность и вероятностное распределение для произвольного ввода во время выполнения не имеет значения), но функции более высокого качества сокращают время предварительной компрессии для данного уровня сжатия, наоборот, позвольте мне добиться более высокого сжатия в течение определенного фиксированного времени.
Вопрос: существуют ли эффективные опубликованные функции хэша, настроенные для ввода с такими ограничениями домена? То есть существуют ли хеш-функции, которые используют дополнительную структуру для выполнения меньшего количества операций, но все же достигают разумного результата?
Я искал такие вещи, как «буквенно-цифровая хеш-функция», но результаты не связаны (в основном, просто генерируют буквенно-цифровую строку в качестве выхода хеш-функции); даже некоторые указания относительно правильного жаргона, чтобы я мог искать документы, были бы полезными.
(Этот вопрос мотивировано быть немного интересно решать, на самом деле не нужно.)
Вы хотите идеальный хэш для 27268 предметов? Мне это тяжело. Почему бы просто не использовать хэш-функцию * standard * и справиться с столкновениями? (и, возможно, использовать низкий коэффициент заполнения) – wildplasser
@wildplasser работает отлично, это может занять некоторое время, чтобы сгенерировать. Например. [этот массив] (https://github.com/huonw/unicode_names/blob/1f331f78201b914604346e1d6fc3e9b3b2eda772/src/generated_phf.rs # L771) является самой хэш-таблицей: используйте хеш входной строки в качестве индекса в эту таблицу (а затем проверьте ее правильность). Суть этого вопроса заключается в том, что структура ввода будет быстрее, делая как можно меньше работы. Кроме того, это для сжатия, поэтому коэффициент низкой нагрузки не очень хорош. – huon
@wildplasser Наконец, обратите внимание, что в настоящее время я использую стандартную хеш-функцию (на самом деле я упоминаю три вопроса). – huon