text: # -*- coding: utf-8 -*-
  
  #
  # レーベンシュタイン距離を用いて，
  # 認識結果の誤り数を算出します．
  #
  
  import numpy as np
  import copy
  
  def calculate_error(hypothesis, reference):
      ''' レーベンシュタイン距離を計算し，
          置換誤り，削除誤り，挿入誤りを出力する
      hypothesis:       認識結果(トークン毎に区切ったリスト形式)
      reference:        正解(同上)
      total_error:      総誤り数
      substitute_error: 置換誤り数
      delete_error:     削除誤り数
      insert_error:     挿入誤り数
      len_ref:          正解文のトークン数
      '''
      # 認識結果および正解系列の長さを取得
      len_hyp = len(hypothesis)
      len_ref = len(reference)
  
      # 累積コスト行列を作成する
      # 行列の各要素には，トータルコスト，
      # 置換コスト，削除コスト，挿入コストの
      # 累積値が辞書形式で定義される．
      cost_matrix = [[{"total":0, 
                       "substitute":0,
                       "delete":0,
                       "insert":0} \
                       for j in range(len_ref+1)] \
                           for i in range(len_hyp+1)]
  
      # 0列目と0行目の入力
      for i in range(1, len_hyp+1):
          # 縦方向への遷移は，削除処理を意味する
          cost_matrix[i][0]["delete"] = i
          cost_matrix[i][0]["total"] = i
      for j in range(1, len_ref+1):
          # 横方向への遷移は，挿入処理を意味する
          cost_matrix[0][j]["insert"] = j
          cost_matrix[0][j]["total"] = j
  
      # 1列目と1行目以降の累積コストを計算していく
      for i in range(1, len_hyp+1):
          for j in range(1, len_ref+1):
              #
              # 各処理のコストを計算する
              #
              # 斜め方向の遷移時，文字が一致しない場合は，
              # 置換処理により累積コストが1増加
              substitute_cost = \
                  cost_matrix[i-1][j-1]["total"] \
                  + (0 if hypothesis[i-1] == reference[j-1] else 1)
              # 縦方向の遷移時は，削除処理により累積コストが1増加
              delete_cost = cost_matrix[i-1][j]["total"] + 1
              # 横方向の遷移時は，挿入処理により累積コストが1増加
              insert_cost = cost_matrix[i][j-1]["total"] + 1
  
              # 置換処理，削除処理，挿入処理のうち，
              # どの処理を行えば累積コストが最も小さくなるかを計算
              cost = [substitute_cost, delete_cost, insert_cost]
              min_index = np.argmin(cost)
  
              if min_index == 0:
                  # 置換処理が累積コスト最小となる場合
  
                  # 遷移元の累積コスト情報をコピー
                  cost_matrix[i][j] = \
                      copy.copy(cost_matrix[i-1][j-1])
                  # 文字が一致しない場合は，
                  # 累積置換コストを1増加させる
                  cost_matrix[i][j]["substitute"] \
                      += (0 if hypothesis[i-1] \
                          == reference[j-1] else 1)
              elif min_index == 1:
                  # 削除処理が累積コスト最小となる場合
                  
                  # 遷移元の累積コスト情報をコピー
                  cost_matrix[i][j] = copy.copy(cost_matrix[i-1][j])
                  # 累積削除コストを1増加させる
                  cost_matrix[i][j]["delete"] += 1
              else:
                  # 置換処理が累積コスト最小となる場合
                  
                  # 遷移元の累積コスト情報をコピー
                  cost_matrix[i][j] = copy.copy(cost_matrix[i][j-1])
                  # 累積挿入コストを1増加させる
                  cost_matrix[i][j]["insert"] += 1
  
              # 累積トータルコスト(置換+削除+挿入コスト)を更新
              cost_matrix[i][j]["total"] = cost[min_index]
  
      #
      # エラーの数を出力する
      # このとき，削除コストは挿入誤り，
      # 挿入コストは削除誤りになる点に注意．
      # (削除コストが1である
      #    = 1文字削除しないと正解文にならない 
      #    = 認識結果は1文字分余計に挿入されている
      #    = 挿入誤りが1である)
      #
  
      # 累積コスト行列の右下の要素が最終的なコストとなる．
      total_error = cost_matrix[len_hyp][len_ref]["total"]
      substitute_error = cost_matrix[len_hyp][len_ref]["substitute"]
      # 削除誤り = 挿入コスト
      delete_error = cost_matrix[len_hyp][len_ref]["insert"]
      # 挿入誤り = 削除コスト
      insert_error = cost_matrix[len_hyp][len_ref]["delete"]
      
      # 各誤り数と，正解文の文字数
      # (誤り率を算出する際に分母として用いる)を出力
      return (total_error, 
              substitute_error,
              delete_error,
              insert_error,
              len_ref)
  
  
  if __name__ == "__main__":
      # ref: 正解文
      # hyp: 認識結果
      ref = "狼が犬に似ているようにおべっか使いは友達のように見える"
      hyp = "オオ狼みがい塗に似ているようにオッつ界は伴ちのように見える"
  
  
      # 各文字列を，1文字ずつ区切ってリストデータにする
      hyp_list = list(hyp)
      ref_list = list(ref)
  
      # 誤り数を計算する
      total, substitute, delete, insert, ref_length \
          = calculate_error(hyp_list, ref_list)
  
      # 誤りの数と，誤り率(100*誤り数/正解文の文字数)を出力する
      print("REF: %s" % ref)
      print("HYP: %s" % hyp)
      print("#TOKEN(REF): %d, #ERROR: %d, #SUB: %d, #DEL: %d, #INS: %d" \
          % (ref_length, total, substitute, delete, insert))
      print("UER: %.2f, SUBR: %.2f, DELR: %.2f, INSR: %.2f" \
          % (100.0*total/ref_length,
             100.0*substitute/ref_length,
             100.0*delete/ref_length,
             100.0*insert/ref_length))
  
  