動的計画法でレーベンシュタイン距離を計算する

calculate_levenshtein_distance.rb

require 'delegate'
# https://github.com/tj/terminal-table
require 'terminal-table'

class DpTable < DelegateClass(Array)
  def initialize(str1, str2)
    @str1 = str1
    @str2 = str2
    @table = initialize_table

    super(@table)
  end

  def to_s
    terminal_table.to_s
  end

  private

  def initialize_table
    table = Array.new(@str2.size + 1) { Array.new(@str1.size + 1, nil) }

    (@str2.size + 1).times { |i| table[i][0] = i }
    (@str1.size + 1).times { |j| table[0][j] = j }

    table
  end

  def terminal_table
    colum_chars = @str1.chars
    row_chars = @str2.chars

    Terminal::Table.new do |t|
      t.add_row([nil, '-', *colum_chars])
      @table.each_with_index do |row, i|
        char = i == 0 ? '-' : row_chars[i - 1]
        t.add_row([char, *row])
      end
      t.style = { all_separators: true }
    end
  end
end

def display_animation_of_levenshtein_distance_calculation(str1, str2, interval: 0.2)
  dp_table = DpTable.new(str1, str2)

  (1..str2.size).each do |i|
    (1..str1.size).each do |j|
      replace_cost = str1[j - 1] == str2[i - 1] ? 0 : 1
      dp_table[i][j] = [
        dp_table[i - 1][j] + 1, # Delete
        dp_table[i][j - 1] + 1, # Add
        dp_table[i - 1][j - 1] + replace_cost # Replace
      ].min

      puts("\e[H\e[2J") # clear
      puts(dp_table.to_s)

      sleep(interval)
    end
  end

  levenshtein_distance = dp_table[str2.size][str1.size]

  puts("\e[H\e[2J")
  puts(dp_table.to_s)
  puts("The Levenshtein distance between \"#{str1}\" and \"#{str2}\" is #{levenshtein_distance}.")

  levenshtein_distance
end