路径匹配之最长公共子序列LCSS算法简析

简述

LCSS算法其实就是我们熟悉的LCS算法（Longest Common Subsequence　最长公共子序列），一个非常基础的dp。以前一直以为LCS算法没啥用，完全就是为了应付比赛用的，现在才发现原来LCS算法竟然在路径匹配上也能有很大作用。

问题描述

LCSS算法解决的问题是，给定两个序列(A_1,A_2,A_3,A_4...A_n)和(B_1,B_2,B_3,B_4...B_m)，其中每一个元素可以都可以是一个二维坐标点或者是更高维度的坐标。现在我们需要分别从序列A,B中依次抽取出k个点构成序列SubA，SubB，使得SubA和SubB的点一一“相等”。这里“相等”的含义可以定义为两个点之间的距离（通常是欧式距离）小于一个阈值\varepsilon，如下图所示：

其中p_2,p^,_1 、p_4,p^,_3 便可以看成是匹配的两组。

我们用满足上述条件的最长的SubA(或SubB)的长度来衡量两个序列A,B的相似程度，这也是可以令人理解的。

有时候我们还会对这个定义加一个限制条件：A_i,B_j匹配需要满足|i-j|<\delta

简而言之，我们的LCSS需要做的事就是求出这个最长的序列长度。

算法

基础的dp，对于序列A[1...n],B[1...m]，令lcss[i][j]表示序列(A_1,A_2,A_3,A_4...A_i)和(B_1,B_2,B_3,B_4...B_j)的最长公共子序列，dis[i][j]表示A_i,B_j之间的距离，那么我们可以很容易得到下面的递推式：

for\ 1\leq i\leq n,1\leq j \leq m:

else:

最终求得的lcss[n][m]便是最长序列的长度，复杂度为O(\delta(m+n))。

后续处理

通过上面的方法，我们能够计算得到路径间的LCSS，但是这并不适合作为相似度的直接评判标准。毕竟较长的路径之间的LCSS在数值上可能比较大，但是事实上的符合程度却不是那么好。因此我们通常会将结果除以较短的路径的长度，即：

这样得到的值就有了较好的可度量性了。

总结

LCSS算法由于没有用到所有的点，所以能够较好的抵抗噪声。但是判断两点相等的阈值\varepsilon不太好确定，这是LCSS的最大弊端。

参考

VLACHOS, M., GUNOPULOS, D., AND KOLLIOS, G. Discovering similar multidimensional trajectories. ICDE 2002 Kevin Toohey, Matt Duckham Trajectory similarity measures.March 2015 Ke Deng, Kexin Xie, Kevin Zheng and Xiaofang Zhou ,Trajectory-Indexing-and-Retrieval 程序员编程艺术第十一章：最长公共子序列(LCS)问题