Контрольную цифру часто добавляют к идентификаторам, которые люди могут записывать или передавать с ошибками, чтобы эти ошибки потом обнаруживать.
Примерами могут служить последняя цифра номера кредитной карты, девятая цифра VIN автомобилей, продаваемых в в США, или последняя цифра ISBN.
Алгоритм контрольной цифры ван Дамма — относительно новый и потому малоизвестный. Он опубликован 2004 году.
Алгоритм обнаруживает все ошибки в одной цифре и все одиночные перестановки соседних цифр. Он заметно проще, чем сравнимый по возможностям алгоритм Верхуффа, и не требует использования специальных символов (таких как X в 10-значном ISBN).
В основе алгоритма лежит полностью антисимметричная квазигруппа. Ниже приведён один из примеров порядка 10. До диссертации Дамма [1] считалось, что подобные квазигруппы не существуют.
Квазигруппа подобрана так, чтобы помимо прочего определять максимальное количество фонетических ошибок, характерных для английского языка (13 вместо 30 и т.п.)
Промежуточная цифра | Входная цифра | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
0 | 0 | 3 | 1 | 7 | 5 | 9 | 8 | 6 | 4 | 2 |
1 | 7 | 0 | 9 | 2 | 1 | 5 | 4 | 8 | 6 | 3 |
2 | 4 | 2 | 0 | 6 | 8 | 7 | 1 | 3 | 5 | 9 |
3 | 1 | 7 | 5 | 0 | 9 | 8 | 3 | 4 | 2 | 6 |
4 | 6 | 1 | 2 | 3 | 0 | 4 | 5 | 9 | 7 | 8 |
5 | 3 | 6 | 7 | 4 | 2 | 0 | 9 | 5 | 8 | 1 |
6 | 5 | 8 | 6 | 9 | 7 | 2 | 0 | 1 | 3 | 4 |
7 | 8 | 9 | 4 | 5 | 3 | 6 | 2 | 0 | 1 | 7 |
8 | 9 | 4 | 3 | 8 | 6 | 1 | 7 | 2 | 0 | 5 |
9 | 2 | 5 | 8 | 1 | 4 | 3 | 6 | 7 | 9 | 0 |
Кроме квазигруппы алгоритм использует одну промежуточную цифру, инициализируемую нулём, и по сути состоит всего из одной операции присваивания interim_digit_ = quasigroup[interim_digit_][digit]
.
Пример вычисления контрольной цифры
Предположим, что нам нужно вычислить контрольную цифру для последовательности 572.
- Инициализируем промежуточную цифру значением 0.
- Находим цифру в колонке 5 (это первая цифра входной последовательности) и строке 0 (это значение промежуточной цифры). Там 9. Присваиваем это значение промежуточной цифре.
- Находим цифру в колонке 7 (это вторая цифра входной последовательности) и строке 9 (это значение промежуточной цифры). Там 7. Присваиваем это значение промежуточной цифре.
- Находим цифру в колонке 2 (это третья цифра входной последовательности) и строке 7 (это значение промежуточной цифры). Там 4. Присваиваем это значение промежуточной цифре.
- Входная последовательность закончилась. Последнее значение промежуточной цифры (4) и есть контрольная цифра. Добавляем её в конец последовательности и получаем 5724.
Пример проверки контрольной цифры
Проверяем последовательность цифр 5724. Если ошибок нет, контрольная цифра у неё должна быть 0.
- Инициализируем промежуточную цифру значением 0.
- Находим цифру в колонке 5 (это первая цифра входной последовательности) и строке 0 (это значение промежуточной цифры). Там 9. Присваиваем это значение промежуточной цифре.
- Находим цифру в колонке 7 (это вторая цифра входной последовательности) и строке 9 (это значение промежуточной цифры). Там 7. Присваиваем это значение промежуточной цифре.
- Находим цифру в колонке 2 (это третья цифра входной последовательности) и строке 7 (это значение промежуточной цифры). Там 4. Присваиваем это значение промежуточной цифре.
- Находим цифру в колонке 4 (это четвёртая цифра входной последовательности) и строке 4 (это значение промежуточной цифры). Там 0. Присваиваем это значение промежуточной цифре.
- Входная последовательность закончилась. Последнее значение промежуточной цифры равно 0, как и ожидалось.
Исходный код полностью
#include <iostream> #include <cassert> class Damm { public: Damm() : interim_digit_(0) {} void push(int digit) { static const int quasigroup[10][10] = { {0, 3, 1, 7, 5, 9, 8, 6, 4, 2}, {7, 0, 9, 2, 1, 5, 4, 8, 6, 3}, {4, 2, 0, 6, 8, 7, 1, 3, 5, 9}, {1, 7, 5, 0, 9, 8, 3, 4, 2, 6}, {6, 1, 2, 3, 0, 4, 5, 9, 7, 8}, {3, 6, 7, 4, 2, 0, 9, 5, 8, 1}, {5, 8, 6, 9, 7, 2, 0, 1, 3, 4}, {8, 9, 4, 5, 3, 6, 2, 0, 1, 7}, {9, 4, 3, 8, 6, 1, 7, 2, 0, 5}, {2, 5, 8, 1, 4, 3, 6, 7, 9, 0} }; assert(digit >= 0); assert(digit <= 9); interim_digit_ = quasigroup[interim_digit_][digit]; } int check_digit(void) const { return interim_digit_; } void clear(void) { interim_digit_ = 0; } private: int interim_digit_; }; int main(void) { Damm d; d.push(5); d.push(7); d.push(2); int check_digit = d.check_digit(); std::cout << "Check digit (572) = " << check_digit << ", expected 4\n"; d.clear(); d.push(5); d.push(7); d.push(2); d.push(4); check_digit = d.check_digit(); std::cout << "Check digit (5724) = " << check_digit << ", expected 0\n"; return 0; }
Ссылка на первоисточник
[1] Damm, H. Michael Total anti-symmetrische Quasigruppen PDF
ссылка на оригинал статьи http://habrahabr.ru/post/272003/
Добавить комментарий