Алгоритм Верхуффа

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Верхуффа (англ. Verhoeff algorithm) — алгоритм расчёта контрольной цифры для обнаружения ошибок при ручном вводе длинных цифровых последовательностей. Впервые опубликован в 1969 г. голландским математиком Якобом Верхуффом. Алгоритм позволяет выявить большее число ошибок, нежели аналогичный алгоритм Луна.

Диэдрическая группа D5[править | править исходный текст]

Вместо суммирования произведений цифр на весовые коэффициенты Верхуфф предложил использовать групповую операцию, известную как диэдрическая группа D5.

d(j, k) k
j 0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 1 2 3 4 0 6 7 8 9 5
2 2 3 4 0 1 7 8 9 5 6
3 3 4 0 1 2 8 9 5 6 7
4 4 0 1 2 3 9 5 6 7 8
5 5 9 8 7 6 0 4 3 2 1
6 6 5 9 8 7 1 0 4 3 2
7 7 6 5 9 8 2 1 0 4 3
8 8 7 6 5 9 3 2 1 0 4
9 9 8 7 6 5 4 3 2 1 0

Результат операции d(j, k) проще всего определить по таблице, где он располагается на пересечении j-й строки и k-того столбца таблицы. Выбранная Верхуффом операция не является коммутативной, то есть для неё не всегда выполняется условие d(j, k) = d(k, j).

Последовательно выполняя операцию d(j, k), где j — результат предыдущей итерации (0 для первой итерации), а k — очередная цифра числа, можно получить алгоритм вычисления контрольной цифры, лучший, чем обычное сложение по модулю 10. Действительно, несмотря на то, что оба алгоритма выявляют одиночные ошибки, алгоритм Верхуффа позволяет определить 60 из 90 возможных ошибок перестановки соседних цифр, в отличие от сложения по модулю 10.

Однако Верхуфф пошёл дальше. Он предложил использовать в качестве второго параметра d(j, k) не саму цифру, а результат ещё одной операции — p(x, y), где y - цифра, x - позиция этой цифры по модулю 8. Результат этой операции также удобно определять по таблице.


p(x, y) y
x 0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9
1 1 5 7 6 2 8 3 0 9 4
2 5 8 0 3 7 9 6 1 4 2
3 8 9 1 6 0 4 3 5 2 7
4 9 4 5 3 1 2 6 8 7 0
5 4 2 8 6 5 7 3 9 0 1
6 2 7 9 3 8 0 6 4 1 5
7 7 0 4 6 9 1 3 2 5 8

Алгоритм проверки[править | править исходный текст]

  1. Взять исходное значение c = 0.
  2. Для каждой цифры проверяемого числа, начиная с наименее значимой (справа), вычислить c = d(c, p(i, ni)), где i — порядковый номер цифры, а ni — значение цифры.
  3. Если c = 0, контрольная цифра верна.

Алгоритм вычисления[править | править исходный текст]

  1. Взять исходное значение c = 0.
  2. Для каждой цифры исходного числа, начиная с наименее значимой (справа), вычислить c = d(c, p(i + 1, ni)), где i — порядковый номер цифры, а ni — значение цифры.
  3. Добавить справа к исходному числу результат операции inv(c), определяемый по ещё одной таблице:
j 0 1 2 3 4 5 6 7 8 9
inv(j) 0 4 3 2 1 5 6 7 8 9

Достоинства и недостатки[править | править исходный текст]

Сравнение процента ошибок, выявляемый при помощи алгоритма Верхуффа:

Описание ошибки Алгоритм
Верхуффа
Алгоритм
Луна
Алгоритм SHA1
(равномерный)
ИНН
остаток от
деления на 11
ОКПО
двойной остаток
от деления на 11
EAN13
Одиночные ошибки (6 вместо 7) 100% 100% 94.5% 98.1% 100% 100%
Перестановки соседних цифр (67 вместо 76) 100% 97.7% 94.5% 98.1% 100% 88.8%
Двойные ошибки (66 вместо 77) 95.5% 93.3% 94.5% 98.1% 81.8% 88.8%
Перестановки четных\нечетных позиций цифр (637 вместо 736) 94.2% 0% 94.5% 98.1% 100% 0%
Перестановки любых позиций цифр (6327 вместо 7326) 94.9% 58.6% 94.5% 98.1% 100% 53.3%
Двойные ошибки в несоседних цифрах (636 вместо 737) 94.2% 100% 94.5% 98.1% 100% 88.8%
Вставка любой цифры - (67 вместо 6) 90% 94% 94.5% 90.6% 93.0% 91.4%
Дублирование любой цифры (66 вместо 6) 90% 93.8% 94.5% 89.2% 93.5% 90%

К недостаткам алгоритма традиционно относили его высокую, по сравнению с другими алгоритмами, сложность. Достаточно сложно произвести все вычисления вручную, особенно для длинных последовательностей. Однако при машинной проверке сложность вычислений не играет решающей роли, что позволяет использовать алгоритм Верхуффа при проверке введенных значений в различных устройствах.

Ссылки[править | править исходный текст]