Известно, Верхофф (Verhoeff) поставил точку в вопросе вычисления десятичной контрольной цифры. Но слишком интригует эта тема. Примите мои 4400 чатлов.
Все врут календари!
Вот что интересно. Как так получается, что алгоритм, не имеющий никаких специальных средств для определения фонетических ошибок (15=50), может настолько эффективно (кое-где пишут, что более 95%) их обнаруживать? И хотя в русском языке проблемы фонетических ошибок нет, давайте разбираться.
Мне пришлось написать тестовую программу, чтобы убедиться в том, что на самом деле алгоритм пропускает в несколько раз больше фонетических ошибок, чем обещают. Пускай он ловит довольно много ошибок, но все потому, что ошибки не могут 'угадать' одну правильную цифру из десяти.
Номер 5, или 40 штук по цене одного
Давайте предпримем небольшое исследование и посмотрим, нет ли у алгоритма каких-либо параметров, от которых зависит его работа. Оказывается, они есть. Можно поиграть с векторами замены цифр. Существуют 40 перестановок, каждая из которых может быть использована в алгоритме Верхоффа. Не совсем ясно, почему они имеют порядок 8. Их полный список приведен в коде ниже.
Реализации алгоритма, которые удалось найти, оказались похожи, как близнецы. Все они используют нулевую перестановку, которая, как мы знаем, не очень хорошо выявляет фонетические ошибки. С этим неплохо справляются перестановки с номерами 5, 6, 7, 8, 9, 24, 28, 32, 36. Вероятно, лучше всего использовать перестановку номер 5. Ей на клавиатуре соответствуют более удобно расположенные клавиши, которые могут давать одинаковые коды на парных ошибках (11=55 и 77=99). Ну вот, теперь у вас есть еще одна КЦ, годная, но нестандартная:
//Sha 2012
//ver 2012-07-07
//Free for any use
(*--------------------------------------------------------------------------------------------------
In 1969, a Dutch mathematician Jacobus Verhoeff carried out a study of errors made
by humans in handling decimal numbers. He identified the following principal types:
single errors: a changed to b (60 to 95 percent of all errors)
adjacent transpositions: ab changed to ba (10 to 20 percent)
twin errors: aa changed to bb (0.5 to 1.5 percent)
jump transpositions: acb changed to bca (0.5 to 1.5 percent)
jump twin errors: aca changed to bcb (below 1 percent)
phonetic errors: a0 changed to 1a (0.5 to 1.5 percent; "phonetic"
because in some languages the two have similar pronunciations, as with thirty and thirteen)
omitting or adding a digit: (10 to 20 percent)
----------------------------------------------------------------------------------------------------
Verhoeff's check catches all single errors and all adjacent transpositions.
It also catches 95.555% of twin errors, 94.222% of jump transpositions and jump twin errors,
and most of phonetic errors (assuming a ranges from 2 to 9).
----------------------------------------------------------------------------------------------------
Modified version uses non-standard permutation number: 5, 6, 7, 8, 9, 24, 28, 32 or 36.
It detects more phonetic errors and produces non-standart check digit.
--------------------------------------------------------------------------------------------------*)
unit Verhoeff;
interface
function VerhoeffCalculateChar(const s: string): char;
function VerhoeffValidateString(const s: string): boolean;
function VerhoeffSelfTest: boolean;
procedure VerhoeffInit(SubNo: integer= 0);
implementation
var
//The multiplication table
//is based on multiplication in the dihedral group D5.
//It used to multiply state with (permutated) digit and to get new state.
d: array[0..9] of array [0..9] of byte = (
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
(1, 2, 3, 4, 0, 6, 7, 8, 9, 5),
(2, 3, 4, 0, 1, 7, 8, 9, 5, 6),
(3, 4, 0, 1, 2, 8, 9, 5, 6, 7),
(4, 0, 1, 2, 3, 9, 5, 6, 7, 8),
(5, 9, 8, 7, 6, 0, 4, 3, 2, 1),
(6, 5, 9, 8, 7, 1, 0, 4, 3, 2),
(7, 6, 5, 9, 8, 2, 1, 0, 4, 3),
(8, 7, 6, 5, 9, 3, 2, 1, 0, 4),
(9, 8, 7, 6, 5, 4, 3, 2, 1, 0));
//The permutation table
//applies a permutation to each digit based on its position in the number.
//The positions of the digits are counted from right to left, starting with zero.
//The permutation repeats after eight rows (the row for pos=8 is identical to the row for pos=0).
p: array[0..7] of array [0..9] of byte = (
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
(1, 5, 7, 6, 2, 8, 3, 0, 9, 4),
(5, 8, 0, 3, 7, 9, 6, 1, 4, 2),
(8, 9, 1, 6, 0, 4, 3, 5, 2, 7),
(9, 4, 5, 3, 1, 2, 6, 8, 7, 0),
(4, 2, 8, 6, 5, 7, 3, 9, 0, 1),
(2, 7, 9, 3, 8, 0, 6, 4, 1, 5),
(7, 0, 4, 6, 9, 1, 3, 2, 5, 8));
//The inverse table
//represents the multiplicative inverse of a digit in the dihedral group D5:
//in other words, for any j, the inv table shows the value k such that d(j,k)=0.
inv: array[0..9] of byte =
(0, 4, 3, 2, 1, 5, 6, 7, 8, 9);
function VerhoeffCalculateChar(const s: string): char;
var
len, c, i, j: integer;
begin;
len:=Length(s);
c:=0;
i:=1; //count from 1 not 0! because where is no check digit in the string
while len>0 do begin;
j:=ord(s[len])-ord('0');
if (j<0) or (j>9) then break;
c:=d[c, p[i and 7, j]];
dec(len);
inc(i);
end;
Result:=chr(inv[c]+ord('0'));
end;
function VerhoeffValidateString(const s: string): boolean;
var
len, c, i, j: integer;
begin;
len:=Length(s);
c:=0;
i:=0; //count from 0, because where is check digit in the string
while len>0 do begin;
j:=ord(s[len])-ord('0');
if (j<0) or (j>9) then break;
c:=d[c, p[i and 7, j]];
dec(len);
inc(i);
end;
Result:=(c or len=0);
end;
function VerhoeffSelfTest: boolean;
begin;
Result:=(VerhoeffCalculateChar('75872')='2')
and VerhoeffValidateString('758722')
and (VerhoeffCalculateChar('12345')='1')
and VerhoeffValidateString('123451')
and (VerhoeffCalculateChar('142857')='0')
and VerhoeffValidateString('1428570')
and (VerhoeffCalculateChar('123456789012')='0')
and VerhoeffValidateString('1234567890120')
and (VerhoeffCalculateChar('8473643095483728456789')='2')
and VerhoeffValidateString('84736430954837284567892')
and not VerhoeffValidateString('122451')
and not VerhoeffValidateString('128451');
end;
//#0 is original Verhoeff permutation.
//Other permutations from this array also work (with another check digit).
//Numbers 5, 6, 7, 8, 9, 24, 28, 32, 36 detect phonetic errors much better.
var
Sub: array[0..39,0..9] of byte= (
(1, 5, 7, 6, 2, 8, 3, 0, 9, 4), //0
(1, 6, 8, 7, 2, 4, 9, 3, 0, 5), //1
(1, 7, 9, 8, 2, 6, 4, 5, 3, 0), //2
(1, 8, 5, 9, 2, 0, 7, 4, 6, 3), //3
(1, 9, 6, 5, 2, 3, 0, 8, 4, 7), //4
(2, 5, 8, 4, 7, 1, 3, 0, 9, 6), //5
(2, 6, 9, 4, 8, 7, 1, 3, 0, 5), //6
(2, 7, 5, 4, 9, 6, 8, 1, 3, 0), //7
(2, 8, 6, 4, 5, 0, 7, 9, 1, 3), //8
(2, 9, 7, 4, 6, 3, 0, 8, 5, 1), //9
(3, 5, 1, 9, 7, 0, 2, 4, 6, 8), //10
(3, 6, 1, 5, 8, 9, 0, 2, 4, 7), //11
(3, 7, 1, 6, 9, 8, 5, 0, 2, 4), //12
(3, 8, 1, 7, 5, 4, 9, 6, 0, 2), //13
(3, 9, 1, 8, 6, 2, 4, 5, 7, 0), //14
(4, 3, 5, 9, 6, 2, 8, 1, 7, 0), //15
(4, 3, 6, 5, 7, 0, 2, 9, 1, 8), //16
(4, 3, 7, 6, 8, 9, 0, 2, 5, 1), //17
(4, 3, 8, 7, 9, 1, 5, 0, 2, 6), //18
(4, 3, 9, 8, 5, 7, 1, 6, 0, 2), //19
(5, 0, 4, 6, 8, 2, 3, 1, 9, 7), //20
(5, 2, 9, 0, 8, 1, 3, 6, 4, 7), //21
(5, 7, 0, 6, 3, 4, 8, 1, 9, 2), //22
(5, 7, 9, 1, 0, 3, 8, 6, 4, 2), //23
(6, 0, 4, 7, 9, 8, 2, 3, 1, 5), //24
(6, 2, 5, 0, 9, 8, 1, 3, 7, 4), //25
(6, 8, 0, 7, 3, 2, 4, 9, 1, 5), //26
(6, 8, 5, 1, 0, 2, 3, 9, 7, 4), //27
(7, 0, 4, 8, 5, 6, 9, 2, 3, 1), //28
(7, 2, 6, 0, 5, 4, 9, 1, 3, 8), //29
(7, 9, 0, 8, 3, 6, 2, 4, 5, 1), //30
(7, 9, 6, 1, 0, 4, 2, 3, 5, 8), //31
(8, 0, 4, 9, 6, 1, 7, 5, 2, 3), //32
(8, 2, 7, 0, 6, 9, 4, 5, 1, 3), //33
(8, 5, 0, 9, 3, 1, 7, 2, 4, 6), //34
(8, 5, 7, 1, 0, 9, 4, 2, 3, 6), //35
(9, 0, 4, 5, 7, 3, 1, 8, 6, 2), //36
(9, 2, 8, 0, 7, 3, 5, 4, 6, 1), //37
(9, 6, 0, 5, 3, 7, 1, 8, 2, 4), //38
(9, 6, 8, 1, 0, 7, 5, 4, 2, 3)); //39
procedure VerhoeffInit(SubNo: integer= 0);
var
i, j: integer;
begin;
SubNo:=SubNo mod 40;
for j:=0 to 9 do p[0,j]:=j;
for j:=0 to 9 do p[1,j]:=Sub[SubNo,j];
for i:=2 to 7 do for j:=0 to 9 do p[i,j]:=p[i-1,p[1,j]];
end;
initialization
//VerhoeffInit(0);
end.