8-bit контрольная сумма или хеш-функция

Приветствую.
Сравниваются много строк (миллионы и миллиарды). Строки не сортированы, размер прыгает всегда. Прежде чем сравнить строку со строкой сравнивается размер. Далее есть свободный байт (8 бит), который хочется использовать как некую контрольную сумму или наподобие хеш-функции, что-бы ускорить процесс сравнения. Посоветуйте пожалуйста что-нибудь?

Пробовал CRC8 — очень много неверных попаданий, когда строки разные а CRC одинаков. Пока что остановился на простой сумме всех байт в строке, но может что-то есть лучше?
  • Вопрос задан
  • 5884 просмотра
Пригласить эксперта
Ответы на вопрос 7
zagayevskiy
@zagayevskiy
Android developer at Yandex
8 бит это всего лишь 256 различных значений. Конечно же, когда вы отображаете миллионы в 256, случается много коллизий, это очевидно. Неважно, насколько хорошую функцию вы возьмете, различных хешей все равно будет только 256.
Ответ написан
vsespb
@vsespb
Попробуйте последний один (крайний) байт какой-нибудь криптографической хэш-функции, например md5
Ответ написан
7workers
@7workers
вам в любом случае нужно использовать этот байт как дополнительную проверку. то есть если длина совпала, CRC8 совпали, только тогда проверять побитно. это даст выигрышь, если у вас совпадений мало по сравнению с общим объёмом и строки часто совпадают в начале. Как вариант, попробуйти сравнивать побитно «задом-на-перед», если первый символ совпал.
Ответ написан
Комментировать
@rozhik
Если говорить о английском тексте (как в прочем и о любой текстовой информации) — то CRC не эффективен (особенно для коротких строк). Как пример: простая хэш функция sum( str[i] + str[i+1] << 4) для 0 и четных i, имеет на порядок более равномерное распределение на коротких строках.
Но вообще посмотрите http://www.cse.yorku.ca/~oz/hash.html. Здесь есть несколько толковых функций — оцените по своим данным, какая из них лучше.
Ответ написан
Комментировать
@vilgeforce
Раздолбай и программист
x = 0
for i range(len(inData)):
x = x^inData[i]
x = _rotl(x,7)

чотатипа такого попробуйте… Помесь змеиного с вижуальным :-) _rotl — циклический сдвиг.
Ответ написан
@mayorovp
Автор, вариантов не так и много:

1. CRC8
2. Полиномиальный хеш (таких неплохо попробовать несколько вариантов — с разными нечетными множителями).
3. Хеш, основанный на операции циклического сдвига (тут вариантов немного — сдвигать следует на 3 или 5, можно использовать сложение или xor).

Все эти варианты можно проверить последовательно и выбрать наилучший.
Ответ написан
Комментировать
@dimarick
CRC8 дает достаточно хорошее распределение при хорошей скорости работы.
Если количество коллизий неприемлемо — то увеличивайте разрядность хеша. Другими алгоритмами заметно уменьшить количество коллизий не выйдет.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы