Go の Tips に追記してもよかったのですが, 長くなってきたので独立して書きます。
チェックディジット
チェックディジット (Check Digit) は数字列の誤りを検出するための数値。身近な例だと, マイナンバーにも Modulus11 Weight2~7 というチェックデジットが使われている。
ちなみに, bit列などに対して誤りの検出と訂正が行える仕組みを ECC (Error Check and Correct) といいハミング符号が有名。
Damm
Dammはラテン方格 （Latin square） を用いたチェックディジットのアルゴリズムであり, 全ての1桁入力誤りと全ての隣り合う2桁の入れ替え誤りを検出することができる。(2004, H.Michael Damm)
ラテン方格とは n x n 行列に n 個の異なる要素が各行各列に 1回 だけ現れるように配置された行列。以前取り上げた 実験計画法の直交計画 でも実験回数を減らして効率的に実験を設計するためにラテン方格が使われている。
Dammアルゴリズムはシンプル。
まず, 仮変数 (interim) を 0 で初期化し, 数値列を順に1桁ずつ処理する。
処理中の数字を列番号, 仮変数を行番号とした時の行列の要素を新しい仮変数の値とする。これがコード中の `interim = matrix[interim][row]` の部分。
全ての桁を計算した時の仮変数の値が検査数値となる。
利用するときは上記を計算した結果, 仮変数が 0 となっていれば正しいと確認できる。
func encode(s string) (int, error) {
// 10 x 10 matrix
matrix := [][]int{
[]int{0, 3, 1, 7, 5, 9, 8, 6, 4, 2},
[]int{7, 0, 9, 2, 1, 5, 4, 8, 6, 3},
[]int{4, 2, 0, 6, 8, 7, 1, 3, 5, 9},
[]int{1, 7, 5, 0, 9, 8, 3, 4, 2, 6},
[]int{6, 1, 2, 3, 0, 4, 5, 9, 7, 8},
[]int{3, 6, 7, 4, 2, 0, 9, 5, 8, 1},
[]int{5, 8, 6, 9, 7, 2, 0, 1, 3, 4},
[]int{8, 9, 4, 5, 3, 6, 2, 0, 1, 7},
[]int{9, 4, 3, 8, 6, 1, 7, 2, 0, 5},
[]int{2, 5, 8, 1, 4, 3, 6, 7, 9, 0},
}
interim := 0
for _, v := range strings.Split(s, "") {
row, err := strconv.Atoi(v)
if err != nil {
return 0, err
}
interim = matrix[interim][row]
}
return interim, nil
}
チェックディジットは簡易にチェックできるのが良い点であるが対象が数値なので, 英数字 (大文字・小文字含む) の方が62文字で多少は安心できる気もする。
最終的な Code は GitHub に置いた。