ヴァーヘフアルゴリズムのソースを表示

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

==目的==
ヴァーヘフは、全ての1桁誤りと隣接する2桁の入れ替わりを検出する1桁の十進コード(1桁の十進の数字であるチェックデジット)を見付けるという目標を持っていた。当時はそういったコードが存在しないという想定の証明<ref name=Sisson_1958 />により、例えば[[ISBN#チェックディジット（2006年まで）|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桁の数字を例に取ると、ヴァーヘフは以下のように誤りの分類を報告している。
{| class="wikitable"
|- valign="middle"
! style="background:#ffc" | 誤りの桁数
! style="background:#ffc" | 分類
! style="background:#ffc" | 件数
! style="background:#ffc" | 頻度
|-
|style="background:#ffc" |1||style="background:#ffc" |転写||align="right"|9,574||align="right"|79.05%
|-
|style="background:#ffc" rowspan=8 |2||style="background:#ffc" |入れ替わり||align="right"|1,237||align="right"|10.21%
|-
|style="background:#ffc" |双子||align="right"|67||align="right"|0.55%
|-
|style="background:#ffc" |音声的||align="right"|59||align="right"|0.49%
|-
|style="background:#ffc" |その他隣接||align="right"|232||align="right"|1.92%
|-
|style="background:#ffc" |飛び越え入れ替わり||align="right"|99||align="right"|0.82%
|-
|style="background:#ffc" |飛び越え双子||align="right"|35||align="right"|0.29%
|-
|style="background:#ffc" |その他飛び越え誤り||align="right"|43||align="right"|0.36%
|-
|style="background:#ffc" |その他||align="right"|98||align="right"|0.81%
|-
|colspan=2 style="background:#ffc" |3||align="right"|169||align="right"|1.40%
|-
|colspan=2 style="background:#ffc" |4||align="right"|118||align="right"|0.97%
|-
|colspan=2 style="background:#ffc" |5||align="right"|219||align="right"|1.81%
|-
|colspan=2 style="background:#ffc" |6||align="right"|162||align="right"|1.34%
|-
|colspan=2 style="background:#ffc" |'''計''' || align="right"|'''12,112'''
|}

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

ヴァーヘフアルゴリズムはより適切にはアルゴリズムの族であると考えられる。なぜならこの他の置換も考えられ、ヴァーヘフの論法で考察されているためである。ヴァーヘフはこの特定の置換
<math>\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}
</math>は、95.4%の音声的誤りを検出するという特性を持っているため、特別であると記している。<ref>Verhoeff 1969, p. 95</ref>

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

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

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

{{col-begin}}
{{col-break}}
{| class="wikitable" style="text-align:center"
|- valign="middle"
! rowspan=2 colspan=2 style="background:#ffc" | ''d(j,k)''<ref>Verhoeff 1969, p. 83</ref>
! colspan=10 style="background:#ffc" | k
|- valign="middle"
! style="background:#ffc; width:1em" |  0
! style="background:#ffc; width:1em" |  1
! style="background:#ffc; width:1em" |  2
! style="background:#ffc; width:1em" |  3
! style="background:#ffc; width:1em" |  4
! style="background:#ffc; width:1em" |  5
! style="background:#ffc; width:1em" |  6
! style="background:#ffc; width:1em" |  7
! style="background:#ffc; width:1em" |  8
! style="background:#ffc; width:1em" |  9
|- valign="middle"
! rowspan=10 style="background:#ffc; width:1em" |  j
! style="background:#ffc; width:1em" |  0
| 0 || 1|| 2 || 3|| 4 || 5|| 6 || 7|| 8 || 9
|- valign="bottom"
! style="background:#ffc" | 1
| 1|| 2 || 3|| 4 || 0|| 6 || 7|| 8 || 9|| 5
|- valign="bottom"
! style="background:#ffc" | 2
| 2|| 3 || 4|| 0 || 1|| 7 || 8|| 9 || 5|| 6
|- valign="bottom"
! style="background:#ffc" | 3
| 3|| 4 || 0|| 1 || 2|| 8 || 9|| 5 || 6|| 7
|- valign="bottom"
! style="background:#ffc" | 4
| 4|| 0 || 1|| 2 || 3|| 9 || 5|| 6 || 7|| 8
|- valign="bottom"
! style="background:#ffc" | 5
| 5|| 9 || 8|| 7 || 6|| 0 || 4|| 3 || 2|| 1
|- valign="bottom"
! style="background:#ffc" | 6
| 6|| 5 || 9|| 8 || 7|| 1 || 0|| 4 || 3|| 2
|- valign="bottom"
! style="background:#ffc" | 7
| 7|| 6 || 5|| 9 || 8|| 2 || 1|| 0 || 4|| 3
|- valign="bottom"
! style="background:#ffc" | 8
| 8|| 7 || 6|| 5 || 9|| 3 || 2|| 1 || 0|| 4
|- valign="bottom"
! style="background:#ffc" | 9
| 9|| 8 || 7|| 6 || 5|| 4 || 3|| 2 || 1|| 0
|}
{{col-break|gap=1em}}
{| class="wikitable" style="text-align:center"
|- valign="middle"
! rowspan=2 colspan=2 style="background:#ffc" | &nbsp;
! style="background:#ffc" | &nbsp;
|- valign="middle"
! style="background:#ffc; width:1em" | ''inv(j)''
|- valign="middle"
! rowspan=10 style="background:#ffc; width:1em" |  j
! style="background:#ffc; width:1em" |  0
| 0
|- valign="bottom"
! style="background:#ffc" | 1
| 4
|- valign="bottom"
! style="background:#ffc" | 2
| 3
|- valign="bottom"
! style="background:#ffc" | 3
| 2
|- valign="bottom"
! style="background:#ffc" | 4
| 1
|- valign="bottom"
! style="background:#ffc" | 5
| 5
|- valign="bottom"
! style="background:#ffc" | 6
| 6
|- valign="bottom"
! style="background:#ffc" | 7
| 7
|- valign="bottom"
! style="background:#ffc" | 8
| 8
|- valign="bottom"
! style="background:#ffc" | 9
| 9
|}
{{col-break|gap=1em}}
{| class="wikitable" style="text-align:center"
|- valign="middle"
! rowspan=2 colspan=2 style="background:#ffc" | ''p(pos,num)''
! colspan=10 style="background:#ffc" | num
|- valign="middle"
! style="background:#ffc; width:1em" |  0
! style="background:#ffc; width:1em" |  1
! style="background:#ffc; width:1em" |  2
! style="background:#ffc; width:1em" |  3
! style="background:#ffc; width:1em" |  4
! style="background:#ffc; width:1em" |  5
! style="background:#ffc; width:1em" |  6
! style="background:#ffc; width:1em" |  7
! style="background:#ffc; width:1em" |  8
! style="background:#ffc; width:1em" |  9
|- valign="middle"
! rowspan=8 style="background:#ffc" | &nbsp;pos&nbsp;<br />(mod&nbsp;8)
! style="background:#ffc; width:1em" |  0
| 0 || 1|| 2 || 3|| 4 || 5|| 6 || 7|| 8 || 9
|- valign="bottom"
! style="background:#ffc" | 1
| 1|| 5 || 7|| 6 || 2|| 8 || 3|| 0 || 9|| 4
|- valign="bottom"
! style="background:#ffc" | 2
| 5|| 8 || 0|| 3 || 7|| 9 || 6|| 1 || 4|| 2
|- valign="bottom"
! style="background:#ffc" | 3
| 8|| 9 || 1|| 6 || 0|| 4 || 3|| 5 || 2|| 7
|- valign="bottom"
! style="background:#ffc" | 4
| 9|| 4 || 5|| 3 || 1|| 2 || 6|| 8 || 7|| 0
|- valign="bottom"
! style="background:#ffc" | 5
| 4|| 2 || 8|| 6 || 5|| 7 || 3|| 9 || 0|| 1
|- valign="bottom"
! style="background:#ffc" | 6
| 2|| 7 || 9|| 3 || 8|| 0 || 6|| 4 || 1|| 5
|- valign="bottom"
! style="background:#ffc" | 7
| 7|| 0 || 4|| 6 || 9|| 1 || 3|| 2 || 5|| 8
|}
{{col-end}}

最初の表'''''d'''''は、二面体群D<sub>5</sub>の積に基づくものであり<ref name=Gallian_2010 />、単にその群の{{仮リンク|ケイリー表|en|Cayley table}}である。この群は[[可換]]ではない、つまりある値''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''))である(参考: {{Clarify|reason=不完全な文|date=2014年4月}}

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

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

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

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

== 例 ==
{{col-begin}}
{{col-2}}
''236''に対するチェックデジットの'''生成''':
{| class="wikitable" style="text-align:center"
|-
! style="background:#ffc" | ''i''
! style="background:#ffc" | ''n<sub>i</sub>''
! style="background:#ffc" | ''p(i,n<sub>i</sub>)''
! style="background:#ffc" | ''c''
|-
|0||0||0||0
|-
|1||6||3||3
|-
|2||3||3||1
|-
|3||2||1||2
|}
''c''は''2''であるので、チェックデジットは''inv(2)''つまり''3''となる。
{{col-2}}
''2363''のチェックデジットの'''検証''':
{| class="wikitable" style="text-align:center"
|-
! style="background:#ffc" |  ''i''
! style="background:#ffc" |  ''n<sub>i</sub>''
! style="background:#ffc" |  ''p(i,n<sub>i</sub>)''
! style="background:#ffc" | ''c''
|-
|0||3||3||3
|-
|1||6||3||1
|-
|2||3||3||4
|-
|3||2||1||0
|}
''c''は0であり、チェックデジットは正しい。
{{col-end}}

== 参考文献 ==
{{reflist|refs=
<ref name="Verhoeff_1969">
{{cite book
| title=Error Detecting Decimal Codes (Tract 29)
| author= Verhoeff, J.
| publisher=The Mathematical Centre, Amsterdam
| year=1969
| doi=10.1002/zamm.19710510323
}}
</ref>
<ref name=Verhoeff_1975>
{{cite book
| title=Error Detecting Decimal Codes (Tract 29), second printing
| author= Verhoeff, J.
| publisher=The Mathematical Centre, Amsterdam
| year=1975
}}
</ref>

<ref name=Kirtland_2001>{{cite book | title=Identification Numbers and Check Digit Schemes | author=Kirtland, Joseph | publisher=Mathematical Association of America | year=2001 | page=153 | isbn=0-88385-720-0 | url=https://books.google.co.jp/books?id=npTxORxmLosC&pg=PA121&lpg=PA121&dq=verhoeff+check+digit&source=bl&ots=ovegXzJqwI&sig=YA10aVVcv7Uw-hRGuxX6LO7ai04&hl=en&ei=ONpXTqi_EcfSiAKtotWSCQ&sa=X&oi=book_result&ct=result&redir_esc=y#v=onepage&q=verhoeff%20check%20digit&f=false | accessdate=August 26, 2011}}</ref>

<ref name=Salomon_2005>{{cite book | title=Coding for Data and Computer Communications | author=Salomon, David | publisher=Springer | year=2005 | isbn=0-387-21245-0 |page=56 | url=https://books.google.co.jp/books?id=A88kvYwIVu0C&pg=PA57&lpg=PA57&dq=verhoeff+check+digit&source=bl&ots=yEqVwTaslG&sig=t4whVVHrJUJ7x8eWgIsarvD3hh8&hl=en&ei=WNpXTsXdHLPSiAKm_LimCQ&sa=X&oi=book_result&ct=result&redir_esc=y#v=onepage&q=verhoeff%20check%20digit&f=false | accessdate=August 26, 2011 }}</ref>

<ref name=Haunsperger_2006>{{cite book | title=The Edge of the Universe: Celebrating Ten Years of Math Horizons | editor1-last=Haunsperger | editor1-first=Deanna | editor2-last=Kennedy | editor2-first=Stephen | publisher=Mathematical Association of America | year=2006 | isbn=978-0-88385-555-3 | lccn=2005937266 | url=https://books.google.co.jp/books?id=jiaIeCUpoFwC&pg=PA39&lpg=PA39&dq=verhoeff+check+digit&source=bl&ots=ioBdL0e7ox&sig=tMFBBNAbTN_r8lXn-2RoAO-2syc&hl=en&ei=WNpXTsXdHLPSiAKm_LimCQ&sa=X&oi=book_result&ct=result&redir_esc=y#v=onepage&q=verhoeff%20check%20digit&f=false | page=38 | accessdate=August 26, 2011 }}</ref>

<ref name=Sisson_1958>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.</ref>

<ref name=Gallian_2010>{{cite book | title=Contemporary Abstract Algebra | edition=7th | author=Gallian, Joseph A. | publisher=Brooks/Cole | year=2010 | isbn=978-0-547-16509-7 | lccn=2008940386 | page=111 | url=https://books.google.co.jp/books?id=CnH3mlOKpsMC&pg=PA111&lpg=PA111&dq=verhoeff+check+digit&source=bl&ots=nqn1LC4H3Z&sig=4CWKNR6vvesEGPRWUzeotpXZfA8&hl=en&ei=WNpXTsXdHLPSiAKm_LimCQ&sa=X&oi=book_result&ct=result&redir_esc=y#v=onepage&q=verhoeff%20check%20digit&f=false | accessdate=August 26, 2011}}</ref>

}}

==外部リンク==
{{Wikibooks|Algorithm_Implementation/Checksums/Verhoeff_Algorithm}}
* [http://www.cs.utsa.edu/~wagner/laws/verhoeff.html Detailed description of the Verhoeff algorithm]
* [http://www.augustana.ab.ca/~mohrj/algorithms/checkdigit.html A description] using lookup tables
* [http://search.cpan.org/~jpeterson/Algorithm-Verhoeff-0.3/lib/Algorithm/Verhoeff.pm Verhoeff implementation in Perl] (from [[CPAN]])
* [http://www.briandunning.com/cf/616 Verhoeff implementation in FileMaker Pro]
* [http://www.stens.ca/kb/VerhoeffCheck Verhoeff implementation in MS SQL Server Transact SQL]
* [http://www.ams.org/featurecolumn/archive/verhoeff.html Biographical sketch] of Jacobus Verhoeff
* [https://sites.google.com/site/abapexamples/c/verhoeff-algorithm Verhoeff validation and generation code in C++]
* [https://sites.google.com/site/abapexamples/javascript/verhoeff-algorithm Verhoeff validation & generation code in Javascript]
* [http://en.wikibooks.org/wiki/Algorithm_Implementation/Checksums/Verhoeff_Algorithm Verhoeff validation & generation code in C#, VB.NET, VBA, Java, Python, D, PHP, ActionScript and Pascal/Delphi]

{{DEFAULTSORT:うあへふあるこりすむ}}
[[Category:合同算術]]
[[Category:誤り検出訂正]]