我有许多由 GPS 记录的轨迹，更正式地可以描述为许多线串。
现在，一些记录的轨迹可能是同一条路线的记录，但由于 GPS 系统的不准确，记录是在不同的场合进行的，而且它们可能是以不同的速度记录的，所以它们不会完美匹配，但当人类在地图上查看时仍然看起来足够近，以确定它实际上是已记录的同一条路线。
我想找到一种算法来计算两个线串之间的相似度。我想出了一些自制的方法来做到这一点，但想知道这是否是一个已经有很好的算法来解决的问题。
考虑到相似的平均值代表地图上的相同路径，您将如何计算相似度？
编辑：对于那些不确定我在说什么的人，请查看此链接以了解行字符串的定义：http: //msdn.microsoft.com/en-us/library/bb895372.aspx - I' m不询问字符串。
计算每对轨道上的Fréchet 距离。距离可用于衡量轨道的相似性。
数学警报： Fréchet 是与您的问题相关的度量空间领域的先驱。
我会根据估计的可能错误在第一行周围添加一个缓冲区，然后确定第二行是否完全适合缓冲区。
为了确定“相同的路线”，创建最小的归一化路径向量集，计算总功率差并将总功率差与质量测量值进行比较。
直观地调整差异的力量（例如，平方差异）和质量度量（例如总功率差异的百分比）。该算法产生路径匹配的连续质量测量以及二进制结果（路径相同吗？）
Paul Tomblin 说：我会根据估计的可能错误在第一行周围添加一个缓冲区，然后确定第二行是否完全适合缓冲区。
您可以在比较归一化矢量端点时修改算法。您可以确定是否有任何端点差异超过了某个大小（实现 Paul 的缓冲区思想），或者如果端点在“缓冲区”之外，则可以使用该事实来忽略该端点差异，从而允许比较忽略边程。
您可以沿着 LineString A 的每个点 (Pa) 走，并测量从 Pa 到 LineString B 的最近线段的距离，平均每个距离。
这不是一个快速或完美的方法，但应该能够给出一个有用的数字并且可以很快实现。
线串是否在相似的点开始和结束，或者它们的范围非常不同？
If you consider a single line string to be a sequence of [x,y] points (or [x,y,z] points), then you could compute the similarity between each pair of line strings using the Needleman-Wunsch algorithm. As described in the referenced Wikipedia article, the Needleman-Wunsch algorithm requires a "similarity matrix" which defines the distance between a pair of points. However, it would be easy to use a function instead of a matrix. In your case you could simply use the 2D Euclidean distance function (or a 3D Euclidean function if your points have elevation) to provide the distance between each pair of points.
我实际上支持那个人 (Aaron 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