ヴァーヘフアルゴリズム

ヴァーヘフアルゴリズム^[1](Verhoeff algorithm)とは、オランダ人数学者ヤコブス・ヴァーヘフによって開発された、誤り検出のためのチェックサム計算式であり、1969年に初めて発表された^[2]^[3]。ヴァーヘフアルゴリズムは全ての1桁誤りと隣接する2桁の入れ替わり誤りを検出できる最初の十進チェックデジットアルゴリズムであり^[4]、当時は1桁の十進コードでは不可能であると考えられていた。

目的

ヴァーヘフは、全ての1桁誤りと隣接する2桁の入れ替わりを検出する1桁の十進コード(1桁の十進の数字であるチェックデジット)を見付けるという目標を持っていた。当時はそういったコードが存在しないという想定の証明^[5]により、例えばISBNのチェックデジットなどにおいて、十一進コードが一般的であった。

ヴァーヘフの目標は実地的でもあった。オランダの郵便システムから得た実データを使い、異なる種類の誤りに対する重み付き配点システムを使って異なるコードを評価して、それを基にした。ヴァーヘフによる分析では、誤りを複数のカテゴリーに分類した:まず何桁が誤っているのか、さらに2桁の場合、入れ替わり(ab → ba)、双子(aa → bb)、飛び越え入れ替わり(abc → cba)、音声的(1a → a0 (例えばオランダ語で17と70はそれぞれ/ˈzeːvə(n)tin/と/ˈzeːvə(n)təx/))、そして飛び双子(aba → cbc)に分けられた。さらに数字の欠落や追加もあった。ただし、一部の種類の誤りが起きる確率は小さいかもしれず、また一部のコードは1桁誤りと入れ替わりを検出するという主目的に加えてそういった誤りに対して耐性があった。

音声的な誤りは特に言語による影響が見られた。これはオランダ語において文字は2桁1組で読まれるためであった。またオランダ語で50は15と発音が似ているが、80は18とは発音が似ていない。

6桁の数字を例に取ると、ヴァーヘフは以下のように誤りの分類を報告している。

誤りの桁数	分類	件数	頻度
1	転写	9,574	79.05%
2	入れ替わり	1,237	10.21%
	双子	67	0.55%
	音声的	59	0.49%
	その他隣接	232	1.92%
	飛び越え入れ替わり	99	0.82%
	飛び越え双子	35	0.29%
	その他飛び越え誤り	43	0.36%
	その他	98	0.81%
3		169	1.40%
4		118	0.97%
5		219	1.81%
6		162	1.34%
計		12,112

解説

ヴァーヘフは位数10の二面体群(10要素に対する非可換な演算の系であり、正五角形の回転と反転に対応する)の性質を元に、置換を組み合わせてアルゴリズムを考案した。ヴァーヘフは、これは二面体群の初の実用的応用であり、全ての美しい数学には最終的には用途が見付かるという原則を確認したと主張した^[6]。もっとも、実際にはアルゴリズムは単純なルックアップテーブルによって実装され、元となる群と置換の理論からどうやってその表を生成するのか理解する必要はない。

ヴァーヘフアルゴリズムはより適切にはアルゴリズムの族であると考えられる。なぜならこの他の置換も考えられ、ヴァーヘフの論法で考察されているためである。ヴァーヘフはこの特定の置換 ${\begin{pmatrix}0&1&2&3&4&5&6&7&8&9\\1&5&7&6&2&8&3&0&9&4\end{pmatrix}}={\begin{pmatrix}1&5&8&9&4&2&7&0\end{pmatrix}}{\begin{pmatrix}3&6\end{pmatrix}}$ は、95.4%の音声的誤りを検出するという特性を持っているため、特別であると記している。^[7]

このアルゴリズムの強みは、全ての誤字と入れ替わり誤りと、ほとんどの双子・飛び越え双子・飛び越え入れ替わり・そして音声的誤りを検出する点である。

ヴァーヘフアルゴリズムの主な弱みは複雑さと、必要な計算が手で簡単にできない点である。類似するコードはダムアルゴリズムであり、似た性質を持つ。

表に基づくアルゴリズム

ヴァーヘフアルゴリズムは3つの表を使って実装できる: 積表d・逆元表inv・そして置換表pである。

d(j,k)^[8]		k
d(j,k)^[8]		0	1	2	3	4	5	6	7	8	9
j	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


		inv(j)
j	0	0
	1	4
	2	3
	3	2
	4	1
	5	5
	6	6
	7	7
	8	8
	9	9

p(pos,num)		num
p(pos,num)		0	1	2	3	4	5	6	7	8	9
pos (mod 8)	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

最初の表dは、二面体群D₅の積に基づくものであり^[9]、単にその群のケイリー表（英語版）である。この群は可換ではない、つまりある値jとkに対して、d(j,k) ≠ d(k, j)であることに注意せよ。

逆元表invは数字に対して積における逆元、つまりd(j, inv(j)) = 0を満す数を表す。

置換表pは各数字に対して、数値の中における位置を元に、置換を適用する。これは実際には単一置換(1 5 8 9 4 2 7 0)(3 6)を繰り返し適用したものである。つまり、p(i+j,n) = p(i, p(j,n))である(参考: ^[要説明]

ヴァーヘフチェックサムの計算は次のように実行される:

数値の各桁から配列nを作成する。桁は右から左へ取る(最も右の桁がn₀,となる)。
チェックサムcを0に初期化する。
配列nの各添字i(0から始まる)に対して、cをd(c, p(i mod 8, n_i))で置き換える。

元の数値はc = 0となるとき、かつそのときのみ妥当である。

チェックデジットを生成するには、0を末尾に追加して上記の計算をする。すると正しいチェックデジットはinv(c)となる。

例

236に対するチェックデジットの生成:

i	n_i	p(i,n_i)	c
0	0	0	0
1	6	3	3
2	3	3	1
3	2	1	2

cは2であるので、チェックデジットはinv(2)つまり3となる。

2363のチェックデジットの検証:

i	n_i	p(i,n_i)	c
0	3	3	3
1	6	3	1
2	3	3	4
3	2	1	0

cは0であり、チェックデジットは正しい。

参考文献

外部リンク

[Verhoeff_1969-1] Verhoeff, J. (1969). Error Detecting Decimal Codes (Tract 29). The Mathematical Centre, Amsterdam. doi:10.1002/zamm.19710510323

[Kirtland_2001-2] Kirtland, Joseph (2001). Identification Numbers and Check Digit Schemes. Mathematical Association of America. p. 153. ISBN 0-88385-720-0 August 26, 2011閲覧。

[Salomon_2005-3] Salomon, David (2005). Coding for Data and Computer Communications. Springer. p. 56. ISBN 0-387-21245-0 August 26, 2011閲覧。

[Haunsperger_2006-4] Haunsperger, Deanna; Kennedy, Stephen, eds (2006). The Edge of the Universe: Celebrating Ten Years of Math Horizons. Mathematical Association of America. p. 38. ISBN 978-0-88385-555-3. LCCN 2005-937266 August 26, 2011閲覧。

[Sisson_1958-5] Sisson, Roger L., An improved decimal redundancy check, Communications of the ACM Vol. 1, Iss. 5, May 1958, pp10-12, DOI: 10.1145/368819.368854.

[Verhoeff_1975-6] Verhoeff, J. (1975). Error Detecting Decimal Codes (Tract 29), second printing. The Mathematical Centre, Amsterdam

[7] Verhoeff 1969, p. 95

[8] Verhoeff 1969, p. 83

[Gallian_2010-9] Gallian, Joseph A. (2010). Contemporary Abstract Algebra (7th ed.). Brooks/Cole. p. 111. ISBN 978-0-547-16509-7. LCCN 2008-940386 August 26, 2011閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]