Сходство между строками строки

Question

У меня есть несколько треков, записанных GPS, которые более формально можно описать как ряд строк.

Теперь, некоторые из записанных треков могут быть записями одного и того же маршрута, но из-за неточностей в системе GPS, того факта, что записи были сделаны в отдельных случаях и что они могли быть записаны, путешествуя на разных скоростях, они не будет совпадать идеально, но при просмотре человеком карты все равно будет смотреться достаточно близко, чтобы определить, что это фактически тот же маршрут, который был записан.

Я хочу найти алгоритм, который вычисляет сходство между двумя строковыми строками. Я придумал несколько методов для этого, но хотел бы знать, есть ли у этой проблемы хорошие алгоритмы для ее решения.

Как бы вы вычислили сходство, учитывая, что подобные средства представляют один и тот же путь на карте?

Редактировать: Для тех, кто не уверен в том, о чем я говорю, пожалуйста, посмотрите на эту ссылку для определения того, что такое строка: http://msdn.microsoft.com/en-us/library/bb895372.aspx - Я не спрашивать о символьных строках.

Answer 1

Вычисляет расстояние Фреше на каждой паре дорожек. Расстояние можно использовать для определения сходства ваших треков.

Математическое предупреждение: Фреше был пионером в области метрического пространства , которое имеет отношение к вашей проблеме.

Answer 2

Я бы добавил буфер вокруг первой строки на основе предполагаемой вероятной ошибки, а затем определил, вписывается ли вторая строка целиком в буфер.

Answer 3

Чтобы определить «тот же маршрут», создайте минимальный набор нормализованных векторов пути, рассчитайте общую разность мощностей и сравните общее с показателем качества.

1. Нормализация путевых точек GPS по общей длине пути,
2. объединяет векторы путей, создавая новый набор векторов путей для каждого пути на основе кратчайшего вектора в каждой точке пути,
3. рассчитывают разницу полной мощности между конечными точками каждого вектора в весах нормализованных трасс для длины вектора, и
4. сравните с показателем качества.

Визуально настройте мощность различий (начните, скажем, с разницы в квадратах) и показатель качества (скажем, как процент от общей разницы в мощности) Этот алгоритм производит непрерывный показатель качества соответствия пути, а также двоичный результат (одинаковые ли пути?)

Пол Томблин сказал: я бы добавил буфер вокруг первой строки на основе предполагаемая вероятная ошибка, а затем определить, подходит ли вторая строка полностью внутри буфера.

Вы можете изменить алгоритм при сравнении нормализованных векторных конечных точек. Вы можете определить, была ли какая-либо разница в конечной точке выше определенного размера (реализуя идею буфера Пола) или, возможно, если конечные точки были вне «буфера», использовать этот факт, чтобы игнорировать эту разницу в конечной точке, позволяя сравнение , игнорирующее побочные поездки .

Answer 4

Если вы считаете, что строка из одной строки представляет собой последовательность точек [x, y] (или точек [x, y, z]), то вы можете вычислить сходство между каждой парой строк строки, используя Алгоритм Нидлмана-Вунша . Как описано в ссылочной статье в Википедии, алгоритм Нидлмана-Вунша требует «матрицы сходства», которая определяет расстояние между парой точек. Однако было бы легко использовать функцию вместо матрицы. В вашем случае вы можете просто использовать функцию 2D Евклидово расстояние (или функцию 3D Евклида, если ваши точки имеют высоту), чтобы обеспечить расстояние между каждой парой точек.

Answer 5

Вы можете пройти по каждой точке (Па) в LineString A и измерить расстояние от Pa до ближайшего отрезка линии LineString B, усредняя каждое из этих расстояний.

Это не быстрый и не совершенный метод, но он должен быть в состоянии дать полезное число и его довольно быстро реализовать.

Строки строк начинаются и заканчиваются в одинаковых точках, или они очень разного размера?

Answer 6

Я на самом деле на стороне человека (Аарон Ф.), который сказал, что вас может заинтересовать проблема расстояния Левенштейна (и процитировал это ). Мне кажется, что его ответ пока лучший.

В частности, расстояние Левенштейна (также называемое расстоянием редактирования) не измеряет строго посимвольное расстояние, но также позволяет выполнять вставки и удаления. Лучший алгоритм для этой меры расстояния может быть вычислен в квадратичном времени (довольно медленный, если у вас длинные строки), но вычислительные биологи имеют для этого довольно хорошую эвристику, которая может представлять интерес для вас самих. Проверьте BLAST и FASTA .

В вашей проблеме кажется, что вы имеете дело с различиями между строками чисел, и вам небезразличны числа. Если вы дадите больше информации, я смогу направить вас к правильному варианту BLAST / FASTA / etc для ваших целей. В любом случае, вы можете рассмотреть возможность адаптации BLAST и FASTA для своих нужд. Они довольно простые.

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