やわらかテック

興味のあること。業務を通して得られた発見。個人的に試してみたことをアウトプットしています🍵

【実装コード有り】Elixirでタイポ発見器を最長共通部分列を使って作る

プログラムでタイプミスを修正する難しさ

以下のような変数があったとする
user_input_textは自身で入力したテキストで"apple"と入力したつもりが
間違えて"anpple"と入力してしまっている

user_input_text = "anpple"
answer_text = "apple"

他にもタイプミスはいろんなパターンが考えられる

"aple"
"aale"
"applue"
"apule"

少し大袈裟なものもあるが、人間視点でいえば
「あ、こいつはappleって打ちたかったんやな〜」ってことが何となく分かる
従って添削する場合にappleと修正してあげれば良い

しかし、機械視点ではタイプミスから共通のパターンを見つけて修正するのは難しい

"aple" => "apple"
"aale" => "apple"
"applue" => "apple"
"apule" => "apple"

こんな時に使えるのが最長共通部分列たるもの

最長共通部分列とは

説明するよりも結果見た方が早いので"apple"と"anpple"の最長共通部分列を求めてみる
まずはこんな感じのテーブルを用意

wrong/answer a n p p l e
a - - - - - -
p - - - - - -
p - - - - - -
l - - - - - -
e - - - - - -

まずはのanswerの"apple"の"a"から見ていく
"a"の視点で行に"a"があった場合に、"a"の行に1で埋め込む

wrong/answer a n p p l e
a 1 #発見 1 1 1 1 1
p - - - - - -
p - - - - - -
l - - - - - -
e - - - - - -

さらにwrongのa列を調査済みにするために1で埋め込む

wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 - - - - -
p 1 - - - - -
l 1 - - - - -
e 1 - - - - -

この作業を繰り返し行う
値が一致しない場合は現在の最大値(この場合では1)を埋め込む

wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 1 2 2 2 2
p 1 1 2 - - -
l 1 1 2 - - -
e 1 1 2 - - -
wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 1 2 2 2 2
p 1 1 2 3 3 3
l 1 1 2 3 - -
e 1 1 2 3 - -
wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 1 2 2 2 2
p 1 1 2 3 3 3
l 1 1 2 3 4 4
e 1 1 2 3 4 -
wrong/answer a n p p l e
a 1 1 1 1 1 1
p 1 1 2 2 2 2
p 1 1 2 3 3 3
l 1 1 2 3 4 4
e 1 1 2 3 4 5

これでテーブルの埋め込みは完了 テーブルの最大値が最長共通部分列となる
今回は最長共通部分列が5となった

正解テキストが"banana"の場合はどうなるか
埋め込み過程については同作業なので省略

text a n p p l e
b 0 0 0 0 0 0
a 0 0 0 0 0 0
n 0 0 0 0 0 0
a 0 0 0 0 0 0
n 0 0 0 0 0 0
a 0 0 0 0 0 0

こんな感じの算出をプログラムで行いたい

Elixirでの実装

先にコードと結果をお見せします
Enum.reduce使ってスマートに書けないなぁと色々と試行錯誤したものの断念
アキュムレーターを2つ持たせられたり、条件に一致したら列挙を中止するなどがEnumでできたら嬉しい

defmodule Sample do
  def main(input_val, ans_val) when input_val == ans_val, do: :good
  def main(input_val, ans_val), do: _main(String.graphemes(input_val), ans_val, 0)
  defp _main([], _, counter), do: counter
  defp _main([head | tail], ans_val, counter) do
    str_lst = String.graphemes(ans_val)
    [_n_head | n_tail] = str_lst
    case type_judge(str_lst, head) do
      :hit -> _main(tail, List.to_string(n_tail), counter+1)
      :empty -> _main(tail, List.to_string(n_tail), counter)
    end
  end
  
  def type_judge([], _), do: :empty
  def type_judge([head | tail], compare_str) do
    if String.contains?(compare_str, head) do
      :hit
    else
      type_judge(tail, compare_str)
    end
  end
end

簡単なテストの実行をしてみる

tests = [
  Checker.main("apple", "anpple") == 5,
  Checker.main("apple", "apple") == :good,
  Checker.main("banana", "anpple") == 0,
  Checker.main("banana", "anapple") == 1,
  Checker.main("fish", "fosh") == 3
]

IO.inspect(tests)
#result:
#[true, true, true, true, true]

良い感じですね
動作に関しては問題なさげだけど、もっとシンプルなコードにしたい

コードの解説

main関数

#入力と答えの候補が一致している場合は終了
def main(input_val, ans_val) when input_val == ans_val, do: :good

#文字列をリストに変換して_mainに渡す
def main(input_val, ans_val), do: _main(String.graphemes(input_val), ans_val, 0)
defp _main([], _, counter), do: counter
defp _main([head | tail], ans_val, counter) do
  #正解テキストをリストに変換
  str_lst = String.graphemes(ans_val)
  #次の再帰用に先頭文字列を削除(スライスでやれればいいが...)
  [_n_head | n_tail] = str_lst
  case type_judge(str_lst, head) do
    :hit -> _main(tail, List.to_string(n_tail), counter+1)
    :empty -> _main(tail, List.to_string(n_tail), counter)
  end
end

type_judge
コードに関しては説明することは特になし
貰った文字列同士が一致しているか調べてるのみ
一致した場合に再帰せずに終了

def type_judge([], _), do: :empty
def type_judge([head | tail], compare_str) do
  if String.contains?(compare_str, head) do
    :hit
  else
    type_judge(tail, compare_str)
  end
end

今思えばこれただの「==」でよかったなと
思った通り、普通に動いてる

def type_judge([], _), do: :empty
def type_judge([head | tail], compare_str) do
  if compare_str == head do
    :hit
  else
    type_judge(tail, compare_str)
  end
end

tests = [
  Checker.main("apple", "anpple") == 5,
  Checker.main("apple", "apple") == :good,
  Checker.main("banana", "anpple") == 0,
  Checker.main("banana", "anapple") == 1,
  Checker.main("fish", "fosh") == 3
]

IO.inspect(tests)
#result:
#[true, true, true, true, true]