Levenshtein 거리와 문자의 스크램블?

Question

문자열 비교 문자 메트릭 ala Levenshtein을 찾고 있는데,이 문자열은 문자열의 문자가 위로 스크램블 된 경우에도 작동합니다. 누구든지 그러한 척도를 알고 있습니까? 그러한 통계를 계산할 수있는 Python 모듈이 있다면 또한 좋을 것입니다. 감사합니다.

Answer 1

difflib 라이브러리를 사용해 보거나 pylevenshtein이라는 외부 라이브러리를 사용할 수도 있습니다.

Answer 2

(HashMap 또는 동등 물을 사용하여) 각 문자 유형의 수를 센 다음 결과 값을 빼고 각 빼기의 절대 값을 취합니다. 모두 함께 추가 한 다음 2로 나눕니다 (각 차이를 두 배로 계산했기 때문에).

예 : 따라서

banana 
batman 

a - 3 , 2 -> |1| -> 1 
b - 1 , 1 -> |0| -> 0 
m - 0 , 1 -> |-1| -> 1 
n - 2 , 1 -> |1| -> 1 
t - 0 , 1 -> |-1| -> 1 

당신이 1+1+1+1 = 4 -> 4/2 = 2

확인 : banana에서 변경 m (2 변경)에 t 한 a 한 n 당신은 batman

의 문자가

문자열 길이가 다른 경우 문자열 길이의 차이를 계산하고 차이 수 (위)의 수입니다. 그런 다음 2로 나누고 그 번호를 다시 추가하십시오.

예 : 그 문제로 많은 어려움이 당신에 대해 걱정하지 않는다 위치이기 때문에

는

nab 
banana 

total difference count: 3 
3 - 3 = 0 -> 0/2 = 0 -> 0 + 3 = 3 

또한 나는 전혀 여기 Levenshtein를 사용하지 않을 것입니다.

Answer 3

levenstien 거리의 동적 프로그래밍 솔루션은 예를 들어 delhi, dehli와 같은 pair wise scrambling을 catch하고 이에 상응하는 대체 또는 추가 또는 삭제와 비교할 때이 가중치를 줄이기 위해 간단히 편집 할 수 있습니다.

편집 :이 알고리즘은 이미 존재하며 이름은 Damerau–Levenshtein distance입니다. 이 알고리즘을 검색하면 Python package을 직접 사용할 수 있습니다.