倭算数理研究所

科学・数学・学習関連の記事を、「倭マン日記」とは別に書いていくのだ!

チェックサムと ISBN 番号

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ(目次)。 『Java によるアルゴリズム事典』で、関数型プログラミングで書きやすそうなアルゴリズムがあったので Scala で書いてみた。 今回は、データに誤りが無いかチェックするのに使うチェックサムと、同様の仕組みを持った書籍を識別するのに使われている ISBN 番号を扱います。

この記事の内容

参考

チェックサム

チェックサムは、バイト列に対してそのバイト値の和もしくはビットごとの排他的論理和を計算しておいて、誤りを検出する手法です。 ユースケース

です。 入力の型を Seq[I]、チェックサムの型を S として、それぞれに対応するメソッドを

  • calculateChecksum(Seq[I]): S
  • check(Seq[I]): Boolean

としましょう。 どちらの場合も和のような同じ計算をするので、これを

  • sum(Seq[I]): S

として抜き出し、この sum() メソッドを使ってちょっと実装を加えて、以下のように Checksum トレイトを定義します:

trait Checksum[I, S]{

  protected def sum(input: Seq[I]): S

  /** チェックサムを計算する */
  def calculateChecksum(input: Seq[I]): S = sumToChecksum(sum(input))
  /** sum() の結果をチェックサムに変換する(そのまま返すことも多い) */
  protected def sumToChecksum(sum: S): S

  /** 入力の誤りを検出する */
  def check(input: Seq[I]): Boolean = testSum(sum(input))
  /** sum() の結果から誤りを検出する */
  protected def testSum(sum: S): Boolean
}

実際に使うなら、入力の Seq の最後にチェックサムを加えた Seq を返すメソッドや、入力が誤っていたときにその場所を返すメソッド(ビットごとの排他的論理和を使ったチェックサムでは場所を誤り箇所を同定することはできませんが)などが必要だと思いますが、ちょっと面倒かつアルゴリズムの本質から外れるので、ここでは省きます。

さて、ビットごとの排他的論理和を使った、単純なチェックサムの実装を行ってみましょう。

object SimpleChecksum extends Checksum[Byte, Byte]{

  override protected def sum(input: Seq[Byte]): Byte =
    input.reduce((x, y) => (x ^ y).toByte)

  override protected def sumToChecksum(sum: Byte): Byte = sum

  override protected def testSum(sum: Byte): Boolean = sum == 0
}
  • sum() メソッドは Seq#reduce() メソッドを使えば簡単に実装できます(foldLeft() とかでもいいですが)。 Scala では Byte 同士の排他的論理和 (^) が Int を返すので toByte を呼び出して Byte 型に変換しています。
  • sumToChecksum() メソッドは sum() の結果をそのまま返しています。
  • ビットごとの排他的論理和チェックサムとして使う場合、sum() の結果が0であれば誤りがないので、testSum() メソッドは単に「sum == 0」の結果を返してます。

さて、この SimpleChecksum を使ってみましょう。 input はチェックサムの付いていない適当なバイト列、checked は input の後にチェックサムを加えたバイト列です:

// 準備
val input = ('a' to 'z').map(_.toByte)
val cs = SimpleChecksum.calculateChecksum(input)
val checked = Vector() ++ input :+ cs
  // チェックサムは最後に要素を追加するので Vector にしてみましたが、
  // 大して必要ないかな?

// 検証
assert( !SimpleChecksum.check(input) )  // チェックサムなし => false
assert( SimpleChecksum.check(checked) )  // チェックサムあり => true

という具合に、実装も使用方法も簡単ですね。

ISBN 番号

チェックサムと同じような仕組みを使って誤り検出をしている ISBN 番号に対して、上記のような実装を行ってみましょう。 ISBN 番号は10桁と13桁のものがあり、現在では基本的に13桁のものが使われています。 ここでは実装練習のために両方やってみましょう(10桁の ISBN 番号を対応する13桁のものに変換する手順も定められているようですが、これは無視)。

ISBN 番号のチェックサムの計算では、sum() で計算する和が重み付きの和になっています。

10桁 ISBN 番号
10桁の ISBN 番号では、ハイフンを除いて  { a_0a_1a_2\cdots a_8a_9 } という番号に対して

  { \displaystyle\begin{align*}
  10a_0 + 9 a_1 + 8a_2 + \cdots + 2a_8 + a_9
\end{align*}}

という重み付きの和が11の倍数になるようにチェックサム  { a_9 } が定められています。 場合によっては  { a_9 } を10にしないといけないことがありますが、このときには「X」が使われます。 誤りを検証する場合には、この和を11で割った余りが0かどうかを検証します。

では、上記の Checksum トレイトを使って実装してみましょう。 ちょっと13桁の ISBN 番号にも使える機能を ISBN トレイトとして抜き出しています(というか、ほとんど ISBN トレイトに実装書いてます・・・):

trait ISBN extends Checksum[Int, Int]{

  val modulus: Int  // 10桁の場合は 11
  val weight: Seq[Int]  // 10 桁の場合は Seq(10, 9, 8, ... , 1)

  /** 入力の Int 列を、(weight による)重みをつけて和をとる */
  override protected def sum(isbn: Seq[Int]): Int =
    isbn.zip(weight).map(n => n._1 * n._2).sum

  /** sum (最後の数字以外の和)と加えると modulus の倍数になるような値をチェックサムとして返す */
  override protected def sumToChecksum(sum: Int): Int = modulus - (sum % modulus)

  /** 1桁足りない ISBN 番号を受け取って、適切な ISBN 番号を返す。 */
  def completeISBN(isbn: String): String = {
    val s = sum(ISBN.toIntSeq(isbn)) match {
      case 10 => "X" // for ISBN-10
      case d  => d.toString
    }

    // 10桁でも13桁でも、最後の数値の前には必ずハイフンがつく
    if(isbn.endsWith("-")) isbn + s
    else                   isbn + "-" + s
  }

  /** sum の結果を modulus で割った余りが0なら誤りなし */
  protected override def testSum(sum: Int): Boolean = sum % modulus == 0

  /** 文字列で渡された ISBN 番号を検証する */
  def check(isbn: String): Boolean = check(ISBN.toIntSeq(isbn))
}

object ISBN{
  /** 文字列で渡された ISBN 番号を、ハイフンを除いて Seq[Int] にする  */
  def toIntSeq(isbn: String): Seq[Int] = {
    isbn.collect {
      case 'x' | 'X' => 10  // for ISBN-10
      case c if c.isDigit => c.toString.toInt
    }
  }
}

object ISBN10 extends ISBN{

  override val modulus: Int = 11
  override val weight: Seq[Int] = Seq.iterate(10, 10)(i => i-1)
    // 10 から始めて、長さが10で1ずつ減っていく Seq。
    // つまり Seq(10, 9, 8, ... , 1)
}
  • sum() メソッドでは、重み付きの和を Seq#zip() メソッドを使って計算しています。 うーん、便利!
  • 文字列で渡された ISBN 番号は ISBN オブジェクトの toIntSeq() メソッドで Seq[Int] に変換しています。 Seq#collect() メソッドを使うと、ハイフンは落として数値(と X を変換した 10)のみからなる Seq を得られます。 うーん、これまた便利!
  • 10桁の ISBN 番号の重みは Seq#iterate() メソッドを使って作っています。

Java によるアルゴリズム事典』には、10桁の ISBN 番号の検証を行う際、掛け算を使わずに足し算だけで計算できる方法が載せられてますが、再帰を使って書くと上記のコードより少々複雑になるのと、ISBN 番号の補完には使えなさそうなためここでは扱いません。

ISBN10 を使うコードはこんな感じ:

// 1桁足りない ISBN 番号を完成させる
val isbn = ISBN10.completeISBN("4-7741-1729-")
assert( isbn == "4-7741-1729-3" )

// ISBN 番号の検証
assert( ISBN10.check(isbn) )
assert( !ISBN10.check("4-7741-1729-2") )  // 最後の数値を変えてみたら誤り検出

ISBN 番号、結構簡単に検証できますね。

13桁の ISBN 番号
10桁の場合と同様にして、現在使われている13桁の ISBN 番号の計算と検証を行うコードを書いて見ましょう。 13桁の ISBN 番号は、ハイフンを除いて  { a_0a_1a_2a_3\cdots a_{11}a_{12} } という番号に対して

  { \displaystyle\begin{align*}
  a_0 + 3 a_1 + a_2 + 3a_3 + \cdots + 3a_{11} + a_{12}
\end{align*}}

という風に、1と3を交互に重みにした重み付きの和が10の倍数になるようにチェックサムを定めます。 重み weight と modulus が異なるだけなので、上記の ISBN トレイトを使えば簡単に実装できますね:

object ISBN13 extends ISBN{

  override val modulus: Int = 10

  override val weight: Seq[Int] = Stream.continually(List(1, 3)).flatten.take(13)
}
  • weight は和をとる際の重みで、Seq(1, 3, 1, 3, ... , 1) です。 Scala だとどういう風に作るのが普通なのか分からなかったんですが、とりあえず Stream#continually() と Stream#flatten 使ってみました。

ISBN13 の使い方は10桁の ISBN 番号 ISBN10 と同じです:

// 1桁足りない ISBN 番号を完成させる
val isbn = ISBN13.completeISBN("978-4-7741-6366-")
assert( isbn == "978-4-7741-6366-6" )

// ISBN 番号の検証
assert( ISBN13.check(isbn) )
assert( !ISBN13.check("978-4-7741-6366-5") )  // 最後の数値を変えてみたら誤り検出

うん、簡単。

本格的な誤り検出符号が必要な場合は CRC (Cyclic Redunduncy Check) というのをやるそうですが、ビットごとの論理演算がいろいろ出てきて結構複雑。 有限体(ガロア体)とかも関連項目で出てきてるのでまとめて解読中。 そもそも Java の標準 API にあるのでモチベーションが上がらんのだけど。

Javaによるアルゴリズム事典

Javaによるアルゴリズム事典