串
字集
字集為一組有限集合，記為Σ，其元素稱為字；電腦中常見的字集為統一碼，其編碼長度為16位元，即可表達65,536字元。
串
串即一條依序排列之字，串的字數為其長度。字於串中之排序稱為下標，排序最前稱字首，最末為字尾。
舉如：「道可道非常道」係長度為6的中文字串，其字首及字尾均為道。
電腦表示
串為同一字集元素之有限序列，可以連續記憶體區塊保存。
編輯距離
分別給定一個串 S 及目標串 T，反覆編輯 S 使其轉換成 T 所需最少編輯次數稱為編輯距離。編輯係對 S 字尾的操作，包含新增、刪除及替換，示例說明如次：
| 串 | 目標串 | 編輯 | 結果串 | 說明 |
|---|---|---|---|---|
| 道可道 | 非常道 | 相等 | 道可道 | 串與目標串字尾相等，無須編輯操作。 |
| 道可 | 非常道 | 新增 | 道可道 | 串字尾再新增目標串字尾 |
| 道可 | 非常 | 刪除 | 道 | 刪除字尾 |
| 道可 | 非常 | 替換 | 道 | 串字尾以目標串字尾替換，等同於刪除新增。 |
其可評價串間相似度，編輯距離越大，差異越大。
優化函數
d(i, j) 表\(S^i\)及\(T^j\)之編輯距離，其中\(S^i\)表示 S 自頭向尾取 i 個字之子串，即\(S^i=S_1S_2…S_i\)； \(T^j\) 為 T 自頭向尾漸次取 j 個字符之子串。
- 如\(S^i\)刪除字尾\(S_i\)得\(S^{i-1}\)，編輯距離為\(S^{i-1}\)與\(T^{j}\)之編輯距離加上本次操作；
- 如\(S^i\)新增\(T_j\)字尾，因\(S_{i+1}=T_j\)，故編輯距離為\(S^{i}\)與\(T^{j-1}\)之編輯距離加上本次操作；
- 如\(S^i\)以\(T_j\)替換字尾，因\(S_i=T_j\)，故編輯距離為\(S^{i-1}\)與\(T^{j-1}\)之編輯距離加上本次操作。
由上可知 d(i, j) 最優解僅依賴於子問題最優解，故 d(i, j) 遞推等式如次： \[ \begin{aligned} d(i, j) = &\begin{cases} i & d(i, 0) \\ j & d(0, j) \\ \begin{aligned} min&(d(i-1 &, &j &)&+1 \\ &,d( i &, &j-1&)&+1 \\ &,d( i &, &j-1&)&+t(i, j) \\ &) \\ \end{aligned} \end{cases} \\ t(i,j) = &\begin{cases} 0 &S_i = T_j \\ 1 &S_i \neq T_j \end{cases} \end{aligned} \]
| 非 | 常 | 道 | ||
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | |
| 道 | 1 | 1 | 2 | 3 |
| 可 | 2 | 2 | 2 | 3 |
| 道 | 3 | 2 | 3 | 2 |
留言