Question

Approximate String Matching

http://en.wikipedia.org/wiki/Sequence_alignment

http://en.wikipedia.org/wiki/String_metric

Sequence Alignment: Dynamic Time Warping

Dynamic Time Warping

用途是比对两个字串（数列）的相似程度（距离）。

其实就是“ Longest Common Subsequence ”的 Dynamic Programming 演算法，唯一的差别就是 DTW 可以自行设定比对成功、比对失败分别要加多少数值，不一定是一和零。

各位可以让 DTW 的计算结果是一个距离函数，就能客观地衡量多个物品之间的差异程度，而不会导致 AB 很像、BC 很像，结果 AC 完全不像的情况。

特殊技巧

如果想要均匀比对，可以自行设定表格计算范围，甚至可以设定只算 i 与 j 很接近的格子、格子内数值太大太小就不算之类的。顺便加快计算速度，变成线性时间。

如果只取邻近格子满足不了你，可以一次多取几格，把递迴公式弄複杂。

如果觉得比对字元实在太琐碎，可以把字串重新分成一段一段，以段作为单位进行比对。表格中的每个大格子都可以自己再做一次 DTW，变成两层 DTW。

因为 DTW 发明很久了，所以方法天马行空、什麽都有。网路上可以找到一堆。

字串的 Edit Distance

一个字串（数列），新增、删除、修改一个字元算做一步，请问需要几步才能改成另一个已知字串（数列）？

这个问题一样可以用 LCS、DTW 的概念来解决。这裡定义的“步”也是一种距离函数；当然啦，实际运用时，各种操作不一定要刚好都是一。

UVa 164 526 10739 12351

树的 Edit Distance

树没有环，很容易设计多项式时间演算法，于是也有人把树拿来算个 Edit Distance。

网路上资料很多，这裡就不介绍了。

k-Difference String Matching（Under Construction!）

http://algnotes.wordpress.com/2014/01/10/

http://algnotes.wordpress.com/2014/02/01/k-palindrome-subsequence/

http://maskray.me/blog/2013-02-10-bk-tree

http://shygypsy.com/tools/BkTree.cpp

k-Mismatch String Matching（Under Construction!）

http://algnotes.wordpress.com/2014/01/09/

k-Mismatch Longest Common Substring（Under Construction!）

https://arxiv.org/abs/1409.1694