텍스트 유사 알고리즘

Question

두 개의 자막 파일이 있습니다. 나는 그들이

는 때때로 하나 개의 파일에 "바람이 ... 음악이 재생되는 불고있다"등의 의견이있는 유사한 텍스트를 같은 텍스트를 나타내는, 또는 여부를 알려주는 기능이 필요합니다. 하지만 내용의 80 %가 동일합니다. 이 함수는 TRUE를 반환해야합니다 (파일은 동일한 텍스트를 나타냅니다). 때때로 l (1 - L) 대신에 1과 같은 맞춤법 오류가 있습니다. 수하물 1 개는입니다. 물론 함수는 TRUE를 반환해야 함을 의미합니다.

내 의견 :
텍스트의 유사성의 비율을 반환해야 기능 - 여기로 간주 될 거라고 -

"모든 사람들이 행복하지 않았다", "모든 사람들이 행복했다"및 동의 철자가 틀리면 같은 텍스트로 간주됩니다. 정확히 말하면, 함수가 반환하는 백분율은 낮지 만 문구가 비슷하다고 말할만큼 충분히 높습니다.

Levenshtein을 전체 파일에 적용 할 것인지 아니면 검색 문자열에만 적용 할 것인지 고려하십시오. 알고리즘은 파일 전체에 적용되어야합니다. 그래도 아주 긴 문자열이 될 것입니다.

Answer 1

Levenshtein 알고리즘 : 0의 결과 이외 http://en.wikipedia.org/wiki/Levenshtein_distance

뭐든지 텍스트 "동일"하지 않은 것을 의미한다. "유사"는 그들이 얼마나 멀리/가까이 있는지 측정합니다. 결과는 정수입니다.

Answer 2

approximate grep을 살펴보십시오. 그것은 당신에게 말하고있는 것처럼 텍스트의 큰 덩어리에서 무언가를 수행하는 것이 거의 확실하지만 포인터를 줄 수 있습니다.

편집 : 당신이 함수를 작성해야 할 것이다 것 같습니다, agrep이의 원래 버전은 오픈 소스되지 않습니다, 그래서 당신은 당신이 너무 여기에 기대하고 http://en.wikipedia.org/wiki/Agrep

Answer 3

에서 OSS 버전에 대한 링크를 얻을 수 있습니다 귀하의 구체적인 요구. 기존 파일 비교 응용 프로그램 (아마도 diff은 이미 필요한 모든 것을 갖추고 있습니다)으로 시작하여 입력에 대한 좋은 결과를 제공하도록 개선하는 것이 좋습니다.

Answer 4

설명한 문제 (즉, 큰 문자열 편집)의 경우 term frequency 벡터에서 0 (완전히 다른)에서 1 (동일)까지의 숫자를 반환하는 Cosine Similarity을 사용할 수 있습니다.

당신은 여기에 설명 된 몇 가지 구현을보고 할 수 있습니다 : Cosine Similarity

Answer 5

가 Levenshtein 거리에 많은 대안이있다. 예 : Jaro-Winkler distance.

같은 알고리즘의 선택은, 단어의 언어, 종류에 따라 한 인간에 의해 입력 된 단어와는 많은 ...

Here you find a helpful implementation of several algorithms within one library