2020-1ν•™κΈ°, λŒ€ν•™μ—μ„œ β€˜μ•Œκ³ λ¦¬μ¦˜β€™ μˆ˜μ—…μ„ λ“£κ³  κ³΅λΆ€ν•œ λ°”λ₯Ό μ •λ¦¬ν•œ κΈ€μž…λ‹ˆλ‹€. 지적은 μ–Έμ œλ‚˜ ν™˜μ˜μž…λ‹ˆλ‹€ :) 전체 ν¬μŠ€νŠΈλŠ” Algorithm ν¬μŠ€νŠΈμ—μ„œ ν™•μΈν•˜μ‹€ 수 μžˆμŠ΅λ‹ˆλ‹€.

3 minute read

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

μΆ”μ²œ 문제

Categories:

Updated: