행 문자열 간의 유사성

Question

나는 GPS에 의해 기록된 많은 트랙을 가지고 있는데, 이는 더 공식적으로는 라인 스트링의 숫자로 설명될 수 있습니다.

이제 기록된 트랙 중 일부는 동일한 경로의 녹음일 수 있지만 GPS 시스템의 부정확성으로 인해 녹음이 별도의 경우에 이루어졌고 서로 다른 속도로 이동하는 것으로 기록되었을 수 있다는 사실은 그렇지 않습니다. 완벽하게 일치하지만 사람이 지도에서 볼 때 실제로 기록된 경로와 동일한 경로인지 판단할 수 있을 만큼 충분히 가까이 보입니다.

두 줄 문자열 간의 유사성을 계산하는 알고리즘을 찾고 싶습니다.나는 이 작업을 수행하기 위해 자체적으로 개발한 몇 가지 방법을 생각해 냈지만 이것이 문제를 해결할 수 있는 좋은 알고리즘이 이미 있는지 알고 싶습니다.

유사한 수단이 지도에서 동일한 경로를 나타내는 경우 유사성을 어떻게 계산합니까?

편집하다: 제가 말하는 내용이 무엇인지 잘 모르시는 분들은 다음 링크에서 행 문자열이 무엇인지 정의해 보시기 바랍니다. http://msdn.microsoft.com/en-us/library/bb895372.aspx - 나는 ~ 아니다 문자열에 대해 질문합니다.

Answer 1

계산하다 프레셰 거리 각 트랙 쌍에.거리는 트랙의 유사성을 측정하는 데 사용될 수 있습니다.

수학 경고: 프레셰는 이 분야의 선구자였습니다. 미터법 공간 이는 귀하의 문제와 관련이 있습니다.

Answer 2

추정된 예상 오류를 기반으로 첫 번째 줄 주위에 버퍼를 추가한 다음 두 번째 줄이 버퍼 내에 완전히 맞는지 확인합니다.

Answer 3

"동일한 경로"를 결정하려면 정규화된 경로 벡터의 최소 집합을 만들고 총 전력 차이를 계산한 다음 총계를 품질 측정값과 비교합니다.

1. 전체 경로 길이에 대한 GPS 웨이포인트를 표준화하고,
2. 경로의 벡터를 함께 걷고, 각 웨이포인트에서 가장 짧은 벡터를 기반으로 각 경로에 대한 새로운 경로 벡터 세트를 생성합니다.
3. 벡터 길이에 대한 정규화된 경로 가중치에서 각 벡터의 끝점 간의 총 전력 차이를 계산하고,
4. 품질 측정과 비교하십시오.

차이의 검정력(예: 제곱 차이로 시작)과 품질 측정값(예: 총 검정력 차이의 백분율)을 시각적으로 조정합니다.이 알고리즘은 경로 일치에 대한 지속적인 품질 측정과 이진 결과를 생성합니다(경로가 동일한가요?).

폴 톰블린은 이렇게 말했습니다.예상 가능한 오류에 따라 첫 번째 줄 주위에 버퍼를 추가 한 다음 두 번째 줄이 버퍼에 완전히 적합한 지 확인합니다.

정규화된 벡터 끝점을 비교할 때 알고리즘을 수정할 수 있습니다.엔드포인트 차이가 특정 크기(Paul의 버퍼 아이디어 구현) 이상인지 확인할 수 있습니다. 또는 엔드포인트가 "버퍼" 외부에 있는 경우 해당 사실을 사용하여 해당 엔드포인트 차이를 무시하고 비교할 수 있습니다. 옆길을 무시하다.

Answer 4

유도선 A의 각 지점(Pa)을 따라 걷고 Pa에서 유도선 B의 가장 가까운 선분까지의 거리를 측정하여 각 거리의 평균을 계산할 수 있습니다.

이는 빠르거나 완벽한 방법은 아니지만 유용한 숫자를 사용할 수 있어야 하며 구현이 매우 빠릅니다.

라인 스트링은 유사한 지점에서 시작하고 끝나나요, 아니면 범위가 매우 다른가요?

Answer 5

단일 행 문자열을 [x,y] 점(또는 [x,y,z] 점)의 시퀀스로 간주하는 경우 다음을 사용하여 각 행 문자열 쌍 간의 유사성을 계산할 수 있습니다. 니들만-분쉬 연산.참조된 Wikipedia 기사에 설명된 대로 Needleman-Wunsch 알고리즘에는 한 쌍의 점 사이의 거리를 정의하는 "유사성 행렬"이 필요합니다.그러나 행렬 대신 함수를 사용하는 것이 더 쉬울 것입니다.귀하의 경우에는 단순히 2D를 사용할 수 있습니다 유클리드 거리 함수(또는 포인트에 표고가 있는 경우 3D 유클리드 함수)를 사용하여 각 포인트 쌍 사이의 거리를 제공합니다.

Answer 6

나는 실제로 당신이 Levenshtein 거리 문제에 관심이 있을 것이라고 말한 사람(Aaron F)의 편입니다. 이것).그의 대답은 지금까지 최고인 것 같습니다.

보다 구체적으로 Levenshtein 거리(편집 거리라고도 함)는 문자별 거리를 엄격하게 측정하지 않지만 삽입 및 삭제를 수행할 수도 있습니다.이 거리 측정에 가장 적합한 알고리즘은 2차 시간(문자열이 길면 꽤 느림)으로 계산할 수 있지만, 계산 생물학자들은 이에 대해 꽤 좋은 휴리스틱을 가지고 있으므로 여러분이 스스로 관심을 가질 수도 있습니다.확인해 보세요 폭발 그리고 파스타.

귀하의 문제에서는 숫자 문자열 간의 차이점을 다루고 있으며 숫자에 관심이 있는 것 같습니다.더 많은 정보를 제공해 주시면 귀하의 목적에 맞는 BLAST/FASTA/etc의 올바른 변형을 안내해 드릴 수 있습니다.어떤 경우든 필요에 따라 BLAST 및 FASTA를 적용하는 것을 고려할 수 있습니다.그것들은 아주 간단합니다.

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