Форум программистов, компьютерный форум, киберфорум
Наши страницы

Заготовки к алгоритму новой десятичной контрольной суммы

Войти
Регистрация
Восстановить пароль
Оценить эту запись

Заготовки к алгоритму новой десятичной контрольной суммы

Запись от mozgotron размещена 29.03.2018 в 21:03

Требования к контрольной сумме и алгоритму:
1. Длина конечного кода 10 знаков.
2. Хеш-код должен состоять только из 10 арабских цифр (0123456789).
3. Хеш-код должен меняться, если меняется расположение знаков в массиве.
3. Алгоритм должен быть очень простым и быстро вычисляемым.

Для генерации хеш-кода можно использовать переменные типа ULong (UInt64). Длина данного типа 20 знаков.
Хешируемый массив знаков обрабатывается поточно, знак за знаком, по одному знаку за цикл.
Для каждого знака из массива знаков создаётся уникальный код (далее индекс), длина которого не должна превышать 20.
Индекс состоит из двух частей: в одной части прописывается AscW-код знака, в другой части — порядковый номер знака. Такая комбинация двух чисел, относящихся к одному знаку, делают индексы неповторяющимися.
Так как самые большие AscW-коды знаков состоят из 5 цифр, под AscW-коды выделяем 5 позиций.
Оставшиеся 20-5=15 позиций выделяем под порядковые номера знаков.

Максимальное количество знаков, которое может поместиться в 15-разрядное число и которое может быть обработано предполагаемым новым хеш-алгоритмом: 999.999.999.999.999. В общем достаточно много.

Возможны 2 варианта компоновки частей индекса:
00000|000000000000000 — AscW-код | порядковый №
000000000000000|00000 — порядковый № | AscW-код

Примеры индексов для букв в строке во:
Первый вариант
в = 01074000000000000001
о = 01086000000000000002
Второй вариант
в = 00000000000000101074
о = 00000000000000201086

Для преобразований индексов можно использовать традиционный в хеш-алгоритмах оператор XOR.
Пример преобразования индексов для букв в, о
первый вариант: 00141197566507614211
второй вариант: 00000000000000170924
Очевидно, что первый вариант индексов даёт более пёстрый результат исключающего или. Поэтому остановимся на первом варианте компоновки: AscW-код | порядковый №.

Если поменять местами первые два знака хешируемого массива знаков, операция XOR даёт одинаковые результаты. А по условиям, хеш-код должен меняться от изменений положения знаков в массиве. Поэтому начинать преобразование индексов нужно не с индекса первого знака, а с некоего индекса инициализации. Таким индексом может быть сдвоенный набор из 10 арабских цифр. Например:
01234567890123456789
98765432109876543210
01234567899876543210
98765432100123456789

Рассмотрим результаты операции XOR для букв {в,о} и четырёх кандидатов на индекс инициализации:
98765432109876543210 xor 01074000000000000001 = калькуляторы не вмещают первое число
98765432100123456789 xor 01074000000000000001 = калькуляторы не вмещают первое число
01234567890123456789 xor 01074000000000000001 = 02289391820778275092 (в)
01234567899876543210 xor 01074000000000000001 = 02289391813644569323 (в)
01234567890123456789 xor 01086000000000000002 = 02175291171091939607 (о)
01234567899876543210 xor 01086000000000000002 = 02175291163595950824 (о)

Пусть индексом инициализации (ИИ) хеширования будет 01234567890123456789.

Теперь рассмотрим результаты операции XOR для комбинаций букв {в,о} и {о,в} с ИИ. Результаты должны быть разными.

Индекс в = 01074000000000000001
Индекс о = 01086000000000000002
01234567890123456789 xor 01074000000000000001 = 02289391820778275092
02289391820778275092 xor 01086000000000000002 = 01213634905531973910

Индекс о = 01086000000000000001
Индекс в = 01074000000000000002
01234567890123456789 xor 01086000000000000001 = 02175291171091939604
02175291171091939604 xor 01074000000000000002 = 01213634905531973910

01213634905531973910 = 01213634905531973910
В результате получились 2 одинаковых индекса. А надо чтобы были разные.

Посмотрим, что будет, если индекс инициализации и индекс первого знака просто складывать +.

Индекс в = 01074000000000000001
Индекс о = 01086000000000000002
01234567890123456789 + 01074000000000000001 = 02308567890123456790
02308567890123456790 xor 01086000000000000002 = 03394466709216526612

Индекс о = 01086000000000000001
Индекс в = 01074000000000000002
01234567890123456789 + 01086000000000000001 = 02320567890123456790
02320567890123456790 xor 01074000000000000002 = 03374266479216787732

03394466709216526612 ≠ 03374266479216787732
При таком преобразовании получились 2 разных индекса, что и требуется.

Для того, чтобы в результирующем индексе было только 10 знаков (по условию к хеш-коду), можно разрезать последний индекс на две равные части по 10 знаков в каждой и пропускать эти части через тот же оператор XOR. В результате должны получиться индексы длиной в 10 знаков.
Проверяем:
0339446670 xor 9216526612 = 9418474138
0337426647 xor 9216787732 = 9416326595

Что ж, пока на выходе получаются симпатичные десятичные хеш-коды:

9418474138 для слова во
9416326595 для слова ов

В принципе, можно попробовать использовать и 20-значный десятичный хеш-код. Там, по крайней, мере коллизий будет меньше, чем в 10-значном хеше.

Ошибка с иксором двух половинок 20-значного хеш-кода!
Результат иксора не должен повторяться для разных кодов, у которых две половинки как бы переставлены местами.
Например 10-значный XOR для кодов 03394466709216526612 и 92165266120339446670 будет одинаковым.
Так же одинаковым 10-значный XOR будет для кодов 92167877320337426647 и 03374266479216787732. У этих пар кодов половинки одинаковые. Эта ошибка увеличивает вероятность коллизий ровно в 2 раза. А по условию, хеш-код должен отличаться для разного расположения цифр.
Значит мало просто разбить 20-значный хеш-код на 2 половинки по 10 знаков и проиксорить. Нужно ещё какое-то действие, изменяющее первую или вторую половинку 20-значного хеш-кода.
Размещено в Без категории
Просмотров 350 Комментарии 0
Всего комментариев 0

Комментарии

 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru