🔢

Dammアルゴリズム〜超簡単で特性のよいチェックディジットの計算方法

2023/12/21に公開

アルゴリズム

tech

Damnではありません！

チェックディジットとは

ある数字列があったとします。

123456879

この数字をユーザに入力してもらう際、ユーザが誤って以下のように入力しました。

123456789 ← 7と8が逆！

この入力を「誤り」と検出するにはどうすればよいでしょうか？

一つの方法として「数字列から計算した誤り検出用の数字を元の数字列に付加しておく」という方法が考えられます。

例えば「各数字とその位置を掛けたものを全て足し、10の剰余をとったもの」を数字列の末尾に付加します。

1234568794
         ↑
    誤り検出用の数字
(1*1 + ... 7*8 + 8*7 + 9*9) mod 10

この数字のことをチェックディジットと呼びます。

チェックディジットがついた数字列はJANコード、ISBN、マイナンバーなど、チェックディジットの計算方法は違えど世の中に溢れています。

ISBNの例:
978-3-16-148410-0 ← 末尾がチェックディジット

チェックディジットがきちんと機能するかどうかはその計算方法に大きく依存します。
その中で簡単なのにとてもよい特性を持つ、あまり知られていない（らしい）アルゴリズムを紹介します。

Dammの特徴

Dammアルゴリズムはよくある以下の入力誤りを検出できます。

数字列のうち1桁を勘違いしてしまった
数字列のうち隣合う2つの数字を入れ替えてしまった
（英語で）13と30など発音が似ている数字を聞き間違えてしまった

他にも、10以上の数を使わない（チェックディジットが1桁の数字で済む）という嬉しい特性もあります。

アルゴリズムと実装

Dammは予め定義された10x10の数字表を使います。

// 数字の置換表
class Table {
  private values: number[]
  constructor(values: number[]) {
    if (values.length < 100) {
      throw new Error('Table must be length of 100 at least')
    }
    this.values = values
  }
  at(row: number, col: number): number | undefined {
    return this.values.at(row*10 + col)
  }
}

// Wikipedia「Dammアルゴリズム」より
const defaultTable = new Table([
  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,
])

チェックディジットを求めるには、以下の操作をします。

変数iの初期値を0にする
数字列の全ての数字xについて以下を繰り返す
- 表の(列x, 行i)の位置にある数字を新たなiの値とする
全ての数字について処理し終わった時のiの値がチェックディジットである

コードで書いた方がわかりやすいかもしれませんので、この文章通り実装してみます。

class Table {
  /* ... */
  checkDigit(xs: number[]) : number {
    let i = 0;
    for (let x of xs) {
      i = this.at(x, i)
    }
    return i
  }
}

これはつまり、こういうことです。

checkDigit(xs: number[]): number {
  return xs.reduce((i, x) => this.at(i, x), 0)
}

逆にチェックディジットが正しいか検証するには以下の操作をします。

変数iの初期値を0にする
（チェックディジットを含む）数字列の全ての数字xについて以下を繰り返す
- 表の(列x, 行i)の位置にある数字を新たなiの値とする
全ての数字について処理し終わった時のiの値が0なら正しいチェックディジットである

ほぼコピペです。
実装も先程のcheckDigitを使えば簡単に書けます。

validate(xs: number[]): boolean {
  return this.checkDigit(xs) === 0
}

いかにこのアルゴリズムがシンプルかお分かりいただけると思います。

これら2つのメソッドを使って、数字の配列ではなく文字列ベースで操作するメソッドを定義しておくと便利です。

class Table {
  /* ... */

  // チェックディジットを計算して末尾に付与した文字列を返すメソッド
  encode(s: string): string {
    const xs = intsOfString(s)
    return xs ? `${s}${this.checkDigit(xs)}` : ''
  }
  // 文字列を検証してOKならチェックディジットを除いた部分文字列を返すメソッド
  decode(s: string): string | undefined {
    return this.validate(intsOfString(s)) ? s.slice(0, -1) : undefined
  }
}

function intsOfString(s: string): number[] {
  const xs = Array.from(s).map(c => Number.parseInt(c, 10))
  return (xs.some(x => Number.isNaN(x))) ? [] : xs
}

まとめ

ユーザによる入力間違いを検出する技術であるチェックディジットについて、シンプルかつ使いやすいアルゴリズムであるDammを紹介しました。

誤りを発見するだけでなく訂正もできる誤り訂正符号（チェックサム）についても、こういった表を使用して実装をシンプルにした手法があるのか気になりますね。

余談ですが、このアルゴリズムを知ったきっかけはマイナンバーのチェックディジットの計算方法について調べたことでした。

こちらの記事でマイナンバーのチェックディジットは誤りを発見できない場合が（チェックディジットとしてはかなりの確率で）あるということを知り、そこで紹介されていたDammアルゴリズムを調べてみた、というわけです。
こちらの記事とその続きである法人マイナンバーのチェックディジットについての記事、どちらもおもしろかったので興味があれば読んでみてください。

チェックディジットとは

Dammの特徴

アルゴリズムと実装

まとめ

Discussion