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

Question

[tronix286]

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

Пробовал CRC8 — очень много неверных попаданий, когда строки разные а CRC одинаков. Пока что остановился на простой сумме всех байт в строке, но может что-то есть лучше?

Comments

[SeptiM]

Если не секрет, откуда ограничение в один байт?
Про природу строк что-нибудь известно?
Может есть возможность рассказать более общую задачу?

Answer 1

[Денис Загаевский]

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

Comments

[KrD]

Я полагаю, автор это уже знает. Может, просто коллизии «скучные»? </irony>

Answer 2

[vsespb]

Попробуйте последний один (крайний) байт какой-нибудь криптографической хэш-функции, например md5

Comments

[Владимир Мартьянов]

Очень сильно будет проц кушать, а эффективность сомнительна.

[vsespb]

Интересно, если у какой-либо функции «случайность» лучше, чем у криптографической, чем это объясняется?
Имхо, если у криптографической функции найдена «неслучайность» где-либо, это уже уязвимость.

[Sirion]

md5 уже не используется в криптографии

[vsespb]

Она используется в криптографии. Например в браузере можно посмотреть md5 fingerprint какого-нибудь SSL сертификата. Это криптографическая хэш-функция и она не на столько слаба и не на столько уязвима, чтобы вызвать проблемы для применения ТС.

Если для нужд ТС она слишком медлена, может использовать её для сравнения с другими функциями и их случайности.

Answer 3

[Max]

вам в любом случае нужно использовать этот байт как дополнительную проверку. то есть если длина совпала, CRC8 совпали, только тогда проверять побитно. это даст выигрышь, если у вас совпадений мало по сравнению с общим объёмом и строки часто совпадают в начале. Как вариант, попробуйти сравнивать побитно «задом-на-перед», если первый символ совпал.

Answer 4

[rozhik]

Если говорить о английском тексте (как в прочем и о любой текстовой информации) — то CRC не эффективен (особенно для коротких строк). Как пример: простая хэш функция sum( str[i] + str[i+1] << 4) для 0 и четных i, имеет на порядок более равномерное распределение на коротких строках.
Но вообще посмотрите http://www.cse.yorku.ca/~oz/hash.html. Здесь есть несколько толковых функций — оцените по своим данным, какая из них лучше.

Answer 5

[Владимир Мартьянов]

x = 0
for i range(len(inData)):
x = x^inData[i]
x = _rotl(x,7)

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

Comments

[mayorovp]

Сдвиг на 7 при рязрядности 8? Да вы большой оригинал…

Лично я бы попробовал 3 или 5, но никак не 7…

Answer 6

[mayorovp]

Автор, вариантов не так и много:

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

Все эти варианты можно проверить последовательно и выбрать наилучший.

Answer 7

[dimarick]

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

Comments

[rozhik]

Нет. CRC всегда в принципе дают плохое распределение при небольших размерах данных к примеру коротких строк. Вы не найдете ни одну серьёзную библиотеку с использованием CRC8 для хэширования ключей. Хотя часто используются hash функции с количеством значений <256.

CRC8 — специально пропустил словарь английского языка через него. В результате количество слов с CRC8 = 111 в 7 раз больше чем с CRC8 = 11.