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

Question

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

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

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

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

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

Answer 1

Вычислить Fréchet distance на каждой паре дорожек.Расстояние может быть использовано для оценки сходства ваших следов.

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

Более конкретно, расстояние Левенштейна (также называемое расстоянием редактирования) не измеряет строго межсимвольное расстояние, но также позволяет выполнять вставки и удаления.Лучший алгоритм для этой меры расстояния может быть вычислен за квадратичное время (довольно медленно, если ваши строки длинные), но у вычислительных биологов есть довольно хорошая эвристика для этого, которая может заинтересовать вас сама по себе.Проверьте ВЗРЫВ и БЫСТРАЯ.

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

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