チェックディジット

番号の最後に付けて誤記をチェックするための余分の桁。10進法(0〜9)の範囲に限れば,Dammアルゴリズムが有名である。これを付けておけば,1文字を書き間違えたときや,隣同士の桁を入れ替えたときに,必ずチェックに引っかかる。

Pythonでは pip install damm として入るモジュールでDammアルゴリズムのチェックディジットが計算できる。

import damm

damm.encode(12345)  # => 9
damm.check(123459)  # => True
damm.check(128459)  # => False
damm.check(124359)  # => False

damm.encode("01234") # 文字列でもよい

16進の場合は import damm16 とする。

モジュール damm.py の中身は,コメントやテストコードを除けば以下のように非常に単純である:

matrix = (
    (0, 3, 1, 7, 5, 9, 8, 6, 4, 2),
    (7, 0, 9, 2, 1, 5, 4, 8, 6, 3),
    (4, 2, 0, 6, 8, 7, 1, 3, 5, 9),
    (1, 7, 5, 0, 9, 8, 3, 4, 2, 6),
    (6, 1, 2, 3, 0, 4, 5, 9, 7, 8),
    (3, 6, 7, 4, 2, 0, 9, 5, 8, 1),
    (5, 8, 6, 9, 7, 2, 0, 1, 3, 4),
    (8, 9, 4, 5, 3, 6, 2, 0, 1, 7),
    (9, 4, 3, 8, 6, 1, 7, 2, 0, 5),
    (2, 5, 8, 1, 4, 3, 6, 7, 9, 0)
)

def encode(number):
    number = str(number)
    interim = 0
    digits = ('0','1','2','3','4','5','6','7','8','9','0')
    for digit in number:
        if digit in digits:
            interim = matrix[interim][int(digit)]
    return interim
    
def check(number):
    return encode(number) == 0

本当に1文字の間違いや隣同士の桁の交換を検出できるかテスト:

import numpy as np

rng = np.random.default_rng(20210523)

def test1():
    s = '00000000' + str(rng.integers(0, 1000000000))
    s = s[len(s) - 9:]
    t = s + str(damm.encode(s))
    i = rng.integers(0, 10)
    j = rng.integers(0, 9)
    if j >= int(t[i]):
        j += 1
    u = t[:i] + str(j) + t[i+1:]
    if damm.check(u):
        print("Damm error:", t, "->", u)
    i = rng.integers(0, 9)
    u = t[:i] + t[i+1] + t[i] + t[i+2:]
    if t != u and damm.check(u):
        print("Damm error:", t, "->", u)

for i in range(10000):
    test1()

ハッシュ値を0〜9にしたものを追加する方法もある。例:

import hashlib

def md5digit(s):
    return int(hashlib.md5(s.encode('utf-8')).hexdigest(), 16) % 10

def md5check(s):
    return md5digit(s[:len(s)-1]) == int(s[len(s)-1])

これはどんな間違いも一様に(9/10の確率で)検出できるが,1文字の間違いや隣同士の桁の交換を検出できないこともある(練習問題:試してみよ)。


Last modified: