Edit Distance
2020-1νκΈ°, λνμμ βμκ³ λ¦¬μ¦β μμ μ λ£κ³ 곡λΆν λ°λ₯Ό μ 리ν κΈμ λλ€. μ§μ μ μΈμ λ νμμ λλ€ :) μ 체 ν¬μ€νΈλ Algorithm ν¬μ€νΈμμ νμΈνμ€ μ μμ΅λλ€.
λ string μ¬μ΄μ 거리λ₯Ό μΈ‘μ νλ λ°©λ²μ΄ μμκΉ? κ°μ₯ μ¬μ΄ λ°©λ²μ λ stringμ΄ κ°μ λ¬Έμλ‘ aligned λλλ‘ λ§€μΉν΄ μ΄κΈλλ λ¬Έμμ μ«μλ‘ κ±°λ¦¬λ₯Ό 맀길 μ μλ€.

μ΄λ, align νλ λ°©μμ λ°λΌ, λ string μ¬μ΄μ κ±°λ¦¬κ° λ¬λΌμ§ μ μλ€. κ·Έλμ κ°λ₯ν λͺ¨λ align λ°©μ μ€ κ°μ₯ μμ <cost>λ₯Ό <edit distance>λΌκ³ μ μνλ€.
μ£Όμ΄μ§ λ string μ¬μ΄μ <edit distance>λ₯Ό μ΄λ»κ² μΈ‘μ ν μ μμκΉ? DPλ₯Ό μ¬μ©νλ©΄, μ λ§ μ½κ² <edit distance>λ₯Ό ꡬν μ μλ€!!
DPλ‘ μ κ·ΌνκΈ° μν΄ λ¨Όμ λ¬Έμ λ₯Ό subproblemμΌλ‘ λΆν ν΄μΌ νλ€. μ΄λ, μ°λ¦¬κ° κ°μ₯ μμ°μ€λ½κ² μκ°ν΄λ³Ό μ μλ λΆν λ°©μμ λ stringμ prefixλ‘ λΆν νλ λ°©λ²μ΄λ€.
Given two strings, $x[1, \dots, m]$ and $y[1, \dots, n]$. A good subproblem would be to compute the optimal edit distance btw some prefixes, $x[1, \dots, i]$ and $y[1, \dots, j]$.
Let $E(i, j)$ be the optimal edit distance btw two prefixes. Then
\[E(i, j) = \min \begin{cases} E(i-1, j) + 1 \\ E(i, j-1) + 1 \\ E(i, j) + \texttt{diff}(i, j) \end{cases}\]
μμ΄λμ΄λ κ°λ¨νλ€. λ prefixμ λν΄, λ§μ§λ§ λ¬Έμκ° κ³΅λ°±μΌ λμ λ κ²½μ°μ λ§μ§λ§ λ¬Έμλ₯Ό λ§μ·μ λμ κ²½μ°λ₯Ό μ’ ν©ν΄ μ΅μ edit distanceμ κ²½μ°λ₯Ό μ·¨νλ μμ΄λμ΄λ€!
// initialization
for $i=0, 1, 2, \dots, m$
ββ$E(i, 0) = i$
for $j=0, 1, 2, \dots, n$
ββ$E(0, j) = j$
// dp process
for $i=1, 2, \dots, m$
ββfor $j=1, 2, \dots, n$
ββββ$E(i, j) = \min \{ E(i-1, j) + 1, \; E(i, j-1) + 1, \; E(i-1, j-1) + \texttt{diff}(i, j)\}$
return $E(m, n)$

<Edit Distance> λ¬Έμ λ λ stringμ idxλ₯Ό μ¬μ©νκΈ° λλ¬Έμ 2μ°¨μ DPλ₯Ό μ¬μ©νλ€. κ·Έλ¦¬κ³ μμ κ·Έλ¦Όμμλ λ³Ό μ μλ― <Edit Distance>μμλ DAG κ΅¬μ‘°κ° μλ€!
<edit distance>λ λ¬Έμμ΄ μ¬μ΄μ 거리λ₯Ό μ μνλ μ’μ κΈ°μ€μ΄ λλ€. κ·Έλ κΈ° λλ¬Έμ λ¬Έμμ΄ λ¬Έμ κ° μμ£Ό λ±μ₯νλ μ½λ© ν μ€νΈμμλ λΉμΆμ΄ λλ μ£Όμ μ΄λ―λ‘ λ μμ§ν΄λ¬μΌ νλ μκ³ λ¦¬μ¦μ΄λΌκ³ μκ°νλ€ π
<edit distance>λ βμ½μ β, βμμ β, βκ΅μ²΄βμ μΈ κ°μ§ μ°μ°μ ν΅ν΄ μ΅μ νΈμ§ 거리λ₯Ό κ³μ°νλ€. μ΄λ, μΈμ ν λ κΈμλΌλ¦¬ κ΅ννλ βκ΅ν(transposition)β μ°μ°μ΄ μΆκ°λλ κ²½μ°κ° <Damerau-Levenshtein distance>λ€. λ΄μ©κ³Ό μ½λλ₯Ό ν¬μ€νΈλ‘ μ 리νμΌλ, λ¬Έμμ΄ κ±°λ¦¬μ λν΄ λ κ΄μ¬μ΄ μλ€λ©΄, μλμ ν¬μ€νΈλ₯Ό μΆμ²νλ€! π
π Damerau-Levenshtein distance