串

字集

字集為一組有限集合，記為Σ，其元素稱為字；電腦中常見的字集為統一碼，其編碼長度為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

標記函數