关于sql server：行字符串之间的相似性

我有许多GPS记录的轨迹，在形式上可以用许多线串来描述。

现在，某些记录的轨迹可能是同一路线的记录，但是由于GPS系统的不准确性，这些记录是在不同的场合进行的，并且它们可能以不同的速度行进，所以不会完美匹配，但当人类在地图上查看时仍然看起来足够接近，以确定其实际上与所记录的路线相同。

我想找到一种计算两个线串之间相似度的算法。我想出了一些自行开发的方法来执行此操作，但是想知道这是否已经有好的算法可以解决。

假设相似的均值表示地图上的相同路径，您将如何计算相似度？

编辑：对于那些不确定我在说什么的人，请查看此链接以获取什么是行字符串的定义：http://msdn.microsoft.com/zh-cn/library/bb895372.aspx-我我不问字符串。

---

计算每对轨道上的Fréchet距离。距离可用于评估轨迹的相似性。

数学警报：Fréchet是与您的问题相关的度量空间领域的先驱。

---

我会根据估计的可能误差在第一行周围添加一个缓冲区，然后确定第二行是否完全适合缓冲区。

---

要确定"相同路线"，请创建最小化的标准化路径矢量集，计算总功率差，然后将总功率差与质量度量进行比较。

将GPS航路点归一化为总路径长度，

沿着路径的矢量走在一起，根据每个航路点上的最短矢量为每个路径创建一组新的路径矢量，

计算归一化路径中矢量长度加权的每个矢量端点之间的总功率差，以及

与质量度量进行比较。

视觉上调整差异的功效(以平方差异开头)和质量度量(例如占总功效差异的百分比)。该算法可对路径匹配以及二进制结果进行连续的质量度量(路径是否相同？)

Paul Tomblin said: I would add a buffer
around the first line based on the
estimated probable error, and then
determine if the second line fits
entirely within the buffer.

您可以在比较归一化向量端点时修改算法。您可以确定是否有任何端点差异超出一定大小(实施Paul的缓冲区思想)，或者，如果端点在"缓冲区"之外，则可以使用该事实忽略该端点差异，从而进行比较，而忽略边路。

---

如果您将单个线串视为[x，y]点(或[x，y，z]点)的序列，则可以使用Needleman-Wunsch算法计算每对线串之间的相似度。如参考的Wikipedia文章中所述，Needleman-Wunsch算法需要一个"相似度矩阵"，该矩阵定义一对点之间的距离。但是，使用函数而不是矩阵会很容易。在您的情况下，您可以简单地使用2D欧式距离函数(如果您的点具有高程，则使用3D欧式函数)来提供每对点之间的距离。

---

您可以沿着LineString A的每个点(Pa)行走，并测量从Pa到LineString B的最近的线段的距离，取每个这些距离的平均值。

这不是一个快速或完美的方法，但是应该能够使用一个有用的数字并且实现起来非常迅速。

线串是在相似的点处开始还是结束，还是程度不同？

---

我实际上与那个人(亚伦·F)在一起，他说您可能对Levenshtein距离问题感兴趣(并引用了这个观点)。在我看来，他的回答是迄今为止最好的。

更具体地说，Levenshtein距离(也称为编辑距离)并不严格测量每个字符的距离，但允许您执行插入和删除操作。可以在二次时间内计算出这种距离测量的最佳算法(如果您的弦长，则算起来会很慢)，但是计算生物学家对此颇有启发，您可能会对自己感兴趣。查看BLAST和FASTA。

在您的问题中，似乎您正在处理数字字符串之间的差异，并且您在乎数字。如果您提供更多信息，我可能会根据您的需要将您定向到BLAST / FASTA / etc的正确变体。无论如何，您都可以考虑根据需要调整BLAST和FASTA。他们很简单。

1：http：//en.wikipedia.org/wiki/Levenshtein_distance，http：//www.nist.gov/dads/HTML/Levenshtein.html

---