두 개의 텍스트 사이에 차이 백분율을 계산하는 알고리즘

Question

저는이 문제에 대한 효율적인 해결책을 찾기 위해 연구했습니다. diffing 엔진 (Google의 diff-match-patch, python의 diff)과 가장 긴 공통 체인 알고리즘을 살펴 보았습니다.

이 문제를 해결하는 방법에 대한 제안을 받고 싶습니다. 특히 추천하고 싶은 알고리즘이나 라이브러리는 무엇입니까?

감사합니다.

Answer 1

"가장 긴 [[chain? substring?]]"이 "퍼센트 차이"와 어떤 관련이 있는지 알지 못합니다. 특히 다른 두 문자열 사이의 차이가 매우 작을 것으로 예상되는 경우 가운데에서 한 문자 씩 (따라서 가장 긴 공통 부분 문자열은 문자열 길이의 약 절반에 해당).

은 "긴 일반적인"낯선 무시하고 최대 길이로 나눈 문자열 (배 물론 100 ;-) 대해 사이의 편집 거리로 "%의 차이를"정의 :

def levenshtein_distance(first, second): 
    """Find the Levenshtein distance between two strings.""" 
    if len(first) > len(second): 
     first, second = second, first 
    if len(second) == 0: 
     return len(first) 
    first_length = len(first) + 1 
    second_length = len(second) + 1 
    distance_matrix = [[0] * second_length for x in range(first_length)] 
    for i in range(first_length): 
     distance_matrix[i][0] = i 
    for j in range(second_length): 
     distance_matrix[0][j]=j 
    for i in xrange(1, first_length): 
     for j in range(1, second_length): 
      deletion = distance_matrix[i-1][j] + 1 
      insertion = distance_matrix[i][j-1] + 1 
      substitution = distance_matrix[i-1][j-1] 
      if first[i-1] != second[j-1]: 
       substitution += 1 
      distance_matrix[i][j] = min(insertion, deletion, substitution) 
    return distance_matrix[first_length-1][second_length-1] 

def percent_diff(first, second): 
    return 100*levenshtein_distance(a, b)/float(max(len(a), len(b))) 

a = "the quick brown fox" 
b = "the quick vrown fox" 
print '%.2f' % percent_diff(a, b) 

Levenshtein 함수는 Stavros' blog입니다. 이 경우 결과는 5.26 (차이 %)입니다.

Answer 2

가장 긴 공통 사슬? 아마도 이것은 다음을 도울 것입니다 : http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Answer 3

자연 언어 텍스트 인 경우 difflib 및 기타 일반적인 하위 시퀀스 라이브러리 외에도 단어를 루트 형태로 정규화하는 형태소 분석을 살펴볼 수 있습니다. Natural Language Toolkit (http://www.nltk.org/) 라이브러리에서 여러 가지 구현을 찾을 수 있습니다. N-Grams (http://en.wikipedia.org/wiki/N-gram)를 사용하여 자연어 텍스트의 얼룩을보다 의미 적으로 비교할 수도 있습니다.

Answer 4

link text 또 다른 관심 영역은 여기에 설명 된 Levenshtein 거리 일 수 있습니다.