レーベンシュタイン距離

levenshtein_distance.rb

# frozen_string_literal: true

# https://mathwords.net/hensyukyori
def levenshtein_distance(a, b)
  d = Array.new(b.size + 1) do
    Array.new(a.size + 1)
  end

  # 先頭の空文字分+1して確保して、
  # そこまでの文字列長さで初期化
  (b.size + 1).times do |i|
    d[i][0] = i
  end
  (a.size + 1).times do |j|
    d[0][j] = j
  end

  1.upto(b.size) do |i|
    1.upto(a.size) do |j|
      # 比較中の文字列(配列のindex上は-1される)が同じ場合0, 違う場合1
      c = b[i - 1] == a[j - 1] ? 0 : 1

      # 上 + 1
      # 左 + 1
      # 左上 + c
      # のうち最も小さいものを採用
      d[i][j] = [
        d[i - 1][j] + 1,
        d[i][j - 1] + 1,
        d[i - 1][j - 1] + c,
      ].min
    end
  end
  # puts d.map { |row| row.map { |e| format("%2d", e) }.join }.join("\n")
  d[b.size][a.size]
end

a = "すうがく"
b = "すがた"
puts "#{a} -> #{b} = #{levenshtein_distance(a, b)}"