# HW5 - Q6
###### tags: `演算法`, `109-2`

:::success
https://hackmd.io/@Cing-Chen/rkL_GSaH_
:::

## Question

**Problems 15-5: Edit distance**
Given two sequences x[1..m] and y[1..n] and set of transformation-operation
costs, the edit distance from x to y is the cost of the least expensive operation
sequence that transforms x to y. Describe a dynamic-programming algorithm that
finds the edit distance from x[1..m] to y[1..n] and prints an optimal operation
sequence. Analyze the running time and space requirements of your algorithm.

- transformation-operations
- Insert a character into x
- Delete a character from x
- Replace a character from x by another character
- Twiddle two adjacent characters from x

## Mein Answer

### Understanding the Question
早安，我花了九九八十七個小時的時間才知道這題想要幹嘛
總之，我用例子來說明題目大概的意思
:::info
假設我們有一個英文單字x e.g. `starburst` ，我們想要把他變成另一個字y `stream`，而我們只能使用：
- 插入字母
- 刪除字母
- 取代字母
- 交換相鄰字母

以上每個操作都視為一次 move，我們用 DP 要找出最小可能的 move 數。

補充：此即是 Damerau-Levenshtein 距離
:::

### How to solve?

DP 的精髓... 先畫表格啦
因為第一個字母就要開始比了 所以我們在最前面加個假想(編號)格
<!-- | | - | S | T | A | R | B | U | R | S | T |
|:----- |:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| **S** | 1 | | | | | | | | | |
| **T** | 2 | | | | | | | | | |
| **R** | 3 | | | | | | | | | |
| **E** | 4 | | | | | | | | | |
| **A** | 5 | | | | | | | | | |
| **M** | 6 | | | | | | | | | | -->

畫完表格，來制定這表格的規則：
:::info
- 如果行列字母一樣 => 不需要 move => 複製左上的值
- 反之 => 需要一次 move => 比較左上、上方、左方的值看誰最低並+1
- 由左而右、由上而下填表
:::

處理到這裡，我們就解決了一般 Edit Distance，或是稱「Wagner-Fischer」距離，為最右下角的 6
然而，我們還沒解決「交換律」，要怎麼處理？
對於這張表，我們要找的是

目前直列的字母，所能找到最後一行(最下面)和這個字母相同
目前橫行的字母，所能找到最後一列(最下面)和這個字母相同

找到了，然後呢？ 照道理說，我們要交換兩個值，但這樣的話整張表等於就毀了
如何在步交換的情況算？我們可以計算這兩格之間的絕對距離

設目前掃到的格子為 A 與 符合條件、找到的格子 B
則我們可以把它改成

A.value = 
    abs(A.row - B.row - 1) + 1 + //
    abs(A.col - B.col - 1)

//TODO STARBURST範例

### References
- Another Approach
https://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm

- https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
- https://www.lemoda.net/text-fuzzy/damerau-levenshtein/index.html
- http://richardminerich.com/2012/09/levenshtein-distance-and-the-triangle-inequality/

以上。
晚安。