Контрольную цифру часто добавляют к идентификаторам, которые люди могут записывать или передавать с ошибками, чтобы эти ошибки потом обнаруживать.Примерами могут служить последняя цифра номера кредитной карты, девятая цифра VIN автомобилей, продаваемых в в США, или последняя цифра ISBN.
Алгоритм контрольной цифры
Алгоритм обнаруживает все ошибки в одной цифре и все одиночные перестановки соседних цифр. Он заметно проще, чем сравнимый по возможностям алгоритм Верхуффа, и не требует использования специальных символов (таких как 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
Комментарии (31)
vvovas
01.12.2015 11:13+14Еще бы описание что такое квазигруппа и почему именно такая, в смысле по какому принципу там цифры подобраны. А то получается: берем число, МАГИЯ, получаем циферку.
Randl
01.12.2015 11:46+5И правда. Главная фишка алгоритма это та самая табличка, как её получили и какие у нее свойства. Алгоритм то элементарный.
JeStoneDev
01.12.2015 15:49+4На DUMP 2015 был очень доступный для понимания доклад «Свежие новости из мира слабо полностью антисимметричных квазигрупп десятого порядка». Там Алексей Кирпичников достаточно последовательно приходит к методу Дамма, по ходу рассказа объясняя и о том, что значит «квазигруппы» и «антисимметричность». Но как была получена «магическая» табличка он не объясняет.
www.youtube.com/watch?v=cwKnHHRutUs
xenohunter
01.12.2015 17:25+9> очень доступный для понимания
> слабо полностью антисимметричных квазигрупп десятого порядка
Challenge accepted!
BeeVee
04.12.2015 16:50+2Вот самый короткий вариант доказательства, который мне известен (6 страниц на английском языке): www.researchgate.net/publication/220186571_Totally_anti-symmetric_quasigroups_for_all_orders
В формате доклада на нематематической конференции это вряд ли хорошо зашло бы :)
BalinTomsk
01.12.2015 23:57+5конвертнул на TSQL
CREATE FUNCTION fn_dhmd( @value int ) RETURNS int AS BEGIN declare @damm table( inter tinyint not null, input tinyint not null, value tinyint not null, primary key(inter, input)); declare @result int = 0; declare @txt varchar(16); SET @txt = CAST(@value as varchar(16)); declare @length int = LEN(@txt), @idx int = 1; insert into @damm (inter, input, value) values (0,0,0), (0,1,3), (0,2,1), (0,3,7), (0,4,5), (0,5,9), (0,6,8), (0,7,6), (0,8,9), (0,9,2), (1,0,7), (1,1,0), (1,2,9), (1,3,2), (1,4,1), (1,5,5), (1,6,4), (1,7,8), (1,8,6), (1,9,3), (2,0,4), (2,1,2), (2,2,0), (2,3,6), (2,4,8), (2,5,7), (2,6,1), (2,7,3), (2,8,5), (2,9,9), (3,0,1), (3,1,7), (3,2,5), (3,3,0), (3,4,9), (3,5,8), (3,6,3), (3,7,4), (3,8,2), (3,9,6), (4,0,6), (4,1,1), (4,2,2), (4,3,3), (4,4,0), (4,5,4), (4,6,5), (4,7,9), (4,8,7), (4,9,8), (5,0,3), (5,1,6), (5,2,7), (5,3,4), (5,4,2), (5,5,0), (5,6,9), (5,7,5), (5,8,8), (5,9,1), (6,0,5), (6,1,8), (6,2,6), (6,3,9), (6,4,7), (6,5,2), (6,6,0), (6,7,1), (6,8,3), (6,9,4), (7,0,8), (7,1,9), (7,2,4), (7,3,5), (7,4,3), (7,5,6), (7,6,2), (7,7,0), (7,8,1), (7,9,7), (8,0,9), (8,1,4), (8,2,3), (8,3,8), (8,4,6), (8,5,1), (8,6,7), (8,7,2), (8,8,0), (8,9,5), (9,0,2), (9,1,5), (9,2,8), (9,3,1), (9,4,4), (9,5,3), (9,6,6), (9,7,7), (9,8,9), (9,9,0); while @length > 0 begin SELECT top 1 @result = value, @idx = @idx + 1, @length = @length - 1 FROM @damm WHERE inter = @result AND input = RIGHT(LEFT(@txt, @idx),1) end; RETURN 10 * @value + @result; END GO declare @result int = ( SELECT dbo.fn_dhmd( 572 ) ); IF 5724 <> @result begin RAISERROR ('FAILED: incorreclt calculate dhmd number: %d ', 16, -1, @result ) end set @result = ( SELECT dbo.fn_dhmd( 5724 ) ); IF 57240 <> @result begin RAISERROR ('FAILED: incorreclt calculate dhmd number: %d ', 16, -1, @result ) end
potan
08.12.2015 15:55-1Хорошо бы написать, что означает «полностью антисимметричная квазигруппа»? Понятие «антисимметричность» обычно используется для колец.
ivanych
Что это значит?
Ogra
Помогает не путать 13 (thirteen) и 30 (thirty), чтобы вместо 1913 не оказалось 1930, например.
ivanych
Каким образом помогает? Как это выглядит?
mayorovp
13 и 30 дают разные контрольные суммы, очевидно же…
ivanych
Ну так это работает для любых неправильных цифр, при чем тут фонетические ошибки?
iDeBugger
Алгоритм обнаруживает однократные ошибки, а 13 и 30 — двукратная
ivanych
Так однократные или двукратные? Или все однократные и некоторые двукратные? А трехкратные не обнаруживает?
FractalizeR
Вы прикалываетесь? ;) Или и правда непонятно?
ivanych
Правда непонятно.
ivanych
У меня ощущение, что Вы и комментаторы выше не поняли вопрос. Я не спрашиваю, что такое контрольная сумма. Я понимаю, что контрольная сумма не совпадет, если ошибиться при вводе числа.
Давайте я переформулирую вопрос:
«К чему тут упоминание фонетических ошибок? Этот алгоритм как-то по особому обрабатывает фонетические ошибки? Эти ошибки чем-то отличаются от просто опечаток?»
mayorovp
Этот алгоритм находит любые однократные ошибки и некоторые многократные, в том числе фонетические.
ivanych
Любой алгоритм для вычисления контольной суммы делает то же самое, в том ведь и смысл контрольной суммы. Или нет?
FractalizeR
Разные алгоритмы делают это с разной степенью вероятности. Данный алгоритм с большей степенью вероятности обнаруживает многократные фонетические ошибки.
ivanych
Т.е. алгоритм заточен на выявление именно фонетических ошибок, так?
Ctacus
Наверное имеются в виду ошибки, которые могут возникнуть при записи номера на слух.
FractalizeR
Алгоритм заточен на обнаружение 100% однократных ошибок и на обнаружение многократных фонетических с большей вероятностью, чем некоторые другие алгоритмы.
ivanych
Ок, спасибо.
dimview
Любой алгоритм может найти ограниченное количество ошибок. Но можно выбрать из возможных квазигрупп такую, которая находит больше фонетических ошибок и меньше нефонетических.
Поскольку люди чаще совершают фонетические ошибки, такой алгоритм на практике будет обнаруживать больше ошибок.
Scratch
Перепутаете — при проверке код не совпадет и всё
ivanych
habrahabr.ru/post/272003/?reply_to=8672129#comment_8672135