ヴァーヘフアルゴリズムとは - わかりやすく解説 Weblio辞書

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

ヴァーヘフアルゴリズム

(Verhoeffアルゴリズムから転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/12 06:49 UTC 版)

ナビゲーションに移動検索に移動

ヴァーヘフアルゴリズム^[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}}$