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

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

История

В 1960-х годах с распространением компьютерных систем и автоматизированной обработки данных остро встала проблема защиты от ошибок при вводе числовых идентификаторов (номеров счетов, паспортов, товарных кодов). Существовавшие алгоритмы, такие как контрольная цифра по модулю 10 (например, в стандарте ISBN-10), не обнаруживали некоторые типичные ошибки, особенно перестановку двух соседних цифр (транспозицию).

Якобус Верхофф, работавший в Математическом центре в Амстердаме, в 1969 году опубликовал работу, в которой предложил новый метод. В отличие от арифметических подходов, он применил математический аппарат теории групп, а именно — диэдральную группу D₅ (группу симметрий правильного пятиугольника). Это позволило создать алгоритм, гарантированно выявляющий все ошибки двух типов: замену одной цифры на другую и перестановку любых двух соседних цифр. Долгое время алгоритм оставался малоизвестным за пределами Нидерландов, но впоследствии нашёл применение в системах, где требуется высокая надёжность ручного ввода.

Математические основы

Алгоритм Верхоффа использует не коммутативную операцию, определённую на множестве цифр от 0 до 9. Эта операция моделируется с помощью таблицы умножения, основанной на диэдральной группе D₅.

Диэдральная группа D₅

Группа D₅ состоит из 10 элементов: пяти поворотов правильного пятиугольника (обозначаются 0, 1, 2, 3, 4) и пяти отражений (обозначаются 5, 6, 7, 8, 9). Цифры от 0 до 9 отождествляются с этими элементами. Операция * (умножение) в этой группе не коммутативна: порядок операндов важен.

Таблица умножения (Verhoeff's dihedral group multiplication table)

Для вычислений используется заранее заданная таблица d[i][j], где i и j — цифры от 0 до 9, а результат — элемент группы (цифра от 0 до 9). Эта таблица является латинским квадратом и строится на основе правил умножения в D₅. Например, d[0][1] = 1, d[1][0] = 2 (что демонстрирует некоммутативность).

Таблица перестановок (inverse permutation table)

Также используется таблица inv[i], которая для каждой цифры i возвращает обратный элемент в группе D₅. То есть, d[i][inv[i]] = 0 (нейтральный элемент группы, соответствующий цифре 0).

Таблица позиционных перестановок (permutation table)

Ключевая особенность алгоритма — учёт позиции цифры в последовательности. Для этого применяется таблица p[pos][digit], которая задаёт перестановку цифры в зависимости от её позиции pos (позиции нумеруются с 0 справа налево). Таблица p построена таким образом, что для любой пары соседних позиций pos и pos+1 перестановки p[pos] и p[pos+1] не коммутируют, что и обеспечивает обнаружение транспозиций. В оригинальной работе Верхоффа эта таблица задаётся степенями фиксированной перестановки σ = (1 4 8 7)(2 5 9 6)(0 3).

Алгоритм вычисления контрольной цифры

Процесс вычисления контрольной цифры для последовательности цифр a₁, a₂, ..., aₙ (где a₁ — самая левая цифра) состоит из следующих шагов:

1. Инициализация: Переменная c устанавливается в 0 (нейтральный элемент группы).
2. Итерация по цифрам: Для каждой цифры aᵢ последовательности, начиная с самой правой (i = n) и заканчивая самой левой (i = 1), выполняется:

• c = d[ c ][ p[ i % 8 ][ aᵢ ] ]
• Здесь i % 8 — номер позиции, взятый по модулю 8 (поскольку таблица p определена для позиций 0..7, после чего цикл повторяется). Важно: позиции нумеруются с 0 для самой правой цифры.

1. Выбор контрольной цифры: После обработки всех цифр, контрольная цифра k выбирается такой, чтобы при её добавлении справа к исходной последовательности и повторном вычислении c (с учётом контрольной цифры на позиции 0) результат стал равен 0. То есть k = inv[ c ].

Таким образом, для последовательности цифр a₁...aₙ контрольная цифра k вычисляется как k = inv[ f(a₁...aₙ) ], где f — результат итеративного применения таблиц d и p.

Алгоритм проверки

Для проверки последовательности цифр a₁, a₂, ..., aₙ, k (где k — контрольная цифра) выполняется аналогичная процедура:

1. Инициализация: c = 0.
2. Итерация: Для каждой цифры, начиная с самой правой (k на позиции 0) и заканчивая самой левой (a₁ на позиции n), выполняется:

• c = d[ c ][ p[ i % 8 ][ digit ] ]

1. Результат: Если итоговое значение c равно 0, последовательность считается корректной. Любое другое значение указывает на наличие ошибки.

Свойства и преимущества

Алгоритм Верхоффа обнаруживает все ошибки следующих типов (при условии, что в последовательности допущена ровно одна ошибка):

• Замена одной цифры на любую другую: 100% обнаружение.
• Перестановка двух любых соседних цифр (транспозиция): 100% обнаружение.
• Перестановка двух произвольных цифр (вставка одной цифры между ними): 100% обнаружение для случая, когда расстояние между цифрами не кратно 8 (из-за периодичности таблицы p). Для расстояний, кратных 8, вероятность обнаружения ниже, но такие ошибки крайне редки на практике.
• Вставка или удаление одной цифры: Обнаруживается с высокой вероятностью, но не гарантируется на 100%.

Для сравнения, простой контрольный разряд по модулю 10 не обнаруживает примерно 10% ошибок транспозиции (например, замена 09 на 90 даёт ту же сумму). Алгоритм Луна (Luhn algorithm), используемый в номерах кредитных карт, обнаруживает все одиночные ошибки, но не все транспозиции (например, 09 ↔ 90). Алгоритм Верхоффа является более надёжным для обнаружения наиболее частых ошибок ручного ввода.

Применение

Несмотря на свою математическую элегантность, алгоритм Верхоффа не получил столь широкого распространения, как более простые алгоритмы (например, Луна). Основные причины — бо́льшая вычислительная сложность (требуется три таблицы поиска) и патентные ограничения в прошлом (патент США № 3,636,320, выданный в 1972 году, срок действия которого истёк).

Тем не менее, он применяется в следующих областях:

• Нидерландские банковские счета: Исторически использовался для расчёта контрольных цифр в некоторых старых системах банковских номеров (например, в системе postgiro).
• Национальные идентификационные номера: Использовался в некоторых странах для построения контрольных цифр в персональных идентификационных номерах (хотя точные данные о таких применениях часто не раскрываются).
• Криптография и теория кодирования: Алгоритм служит классическим примером неарифметического подхода к обнаружению ошибок и изучается в учебных курсах по дискретной математике и теории информации.

Критика

Основным недостатком алгоритма Верхоффа является его относительная сложность по сравнению с аналогами. Для реализации требуется хранение трёх таблиц (умножения, обратных элементов и позиционных перестановок), что усложняет его реализацию в простых встроенных системах или при ручном вычислении. Кроме того, алгоритм не является универсальным: он оптимизирован для обнаружения двух конкретных типов ошибок, но не гарантирует обнаружения всех возможных ошибок (например, двойных ошибок или ошибок вставки/удаления). В современных системах, где ошибки ввода часто исправляются автоматически с помощью проверки по базе данных или используются более мощные коды (например, коды Рида-Соломона), алгоритм Верхоффа уступил место более простым методам, таким как алгоритм Луна.

Интересные факты

• Алгоритм Верхоффа является одним из немногих практически используемых алгоритмов, основанных на неабелевой группе.
• Таблица позиционных перестановок p построена таким образом, что для любой позиции i перестановка p[i] является обратной к p[i+1] (с точностью до сопряжения), что и обеспечивает обнаружение транспозиций.
• В оригинальной работе Верхоффа таблица p была задана с помощью перестановки σ = (1 4 8 7)(2 5 9 6)(0 3), которая является элементом группы D₅.

Источники

1. Verhoeff, J. (1969). Error Detecting Decimal Codes. Mathematical Centre Tracts, 29. Amsterdam: Mathematisch Centrum.
2. Wagner, N. R., & Putter, P. S. (1989). Error Detecting Decimal Codes. Communications of the ACM, 32(1), 106-110.
3. Патент США № 3,636,320 "Method and apparatus for detecting errors in a sequence of digits", выдан 18 января 1972 года.