-
路径匹配之单向距离OWD算法
简述 ** OWD(One Way Distance)**算法也是一种描述两个路径之间相似度的方法，最早大概提出于06年左右。最朴素的OWD算法的思路也非常简单，就是把路径之间的距离转化为点到路径的距离再加以处理。这里只对这种算法做简要介绍，至于深层次的理论有空再研究论文。 定义 在定义路径间的距离$D_{owd}$之前，我们先定义点到路径的距离$D_{point}$： 对于点$p$和一个由多个点组成的路径$T$，定义他们之间的距离为$$D_{point}(p,T)=min_{q \i…
-
路径匹配之编辑距离ED算法
简述 编辑距离（Edit Distance），又称Levenshtein距离，原本是用来描述指两个字串之间，由一个转成另一个所需的最少编辑操作次数。这里的”编辑操作“是指“插入”、“删除”和“修改”。是由俄罗斯科学家Vladimir Levenshtein在1965年提出的概念。他通常就被用作一种相似度计算函数，尤其在自然语言处理方面。 问题描述 具体的讲，用编辑距离来描述处理路径相似度问题需要解决的是如下的问题，这个问题又叫”Edit Distance on Real sequence…
-
路径匹配之距离归并MD算法简析
简述 距离归并算法（Merge Distance）也是一种计算路径相似度的算法（其实“路径归并”是我自己瞎翻译的，因为没有找到更加官方的中文翻译）。跟DTW，LCSS之类不同，他提出来时间不算长，但是思想也是十分简单的。计算方便理解容易，也是进行路径相似度匹配的不错的思路。 问题描述 MD算法解决的问题是，给定两个序列$(A_1,A_2,A_3,A_4...A_n)$和$(B_1,B_2,B_3,B_4...B_m)$，其中每一个元素可以都可以是一个二维坐标点或者是更高维度的坐标。现在我…
-
路径匹配之最长公共子序列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)$，其中每一个元素可以都可以是一个二维坐标点或者是更高维度的坐标。现在我们需要分别从序列$…
-
路径匹配之动态时间规整DTW算法简析
简述 DTW算法又叫动态时间规整（ Dynamic Time Warping），是一个比较简单的dp算法。常用于不等长的离散的路径点的匹配问题，在孤立词语音识别、手势识别、数据挖掘和信息检索等领域有着很不错的表现。 问题描述 DTW解决的问题是，给定两个序列$(A_1,A_2,A_3,A_4...A_n)$和$(B_1,B_2,B_3,B_4...B_m)$，其中每一个元素可以都是一个二维坐标点或者是更高维度的坐标。我们现在需要求出一个“距离”，使得他能够表示这两个路径的相似度。 很…