プログラムでタイプミスを修正する難しさ
以下のような変数があったとする
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]