비슷한 두 문자열이 얼마나 유사한 지 비교하기위한 알고리즘은 무엇입니까?

Question

문자열을 비교하여 동일한 것을 나타내는 지 여부를 결정해야합니다. 이것은 약어 및 기타 작은 세부 사항이 다를 수있는 인간이 입력 한 사례 제목과 관련됩니다. 예를 들어, 다음 두 타이틀을 고려해

std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP"; 

반대로 : 빨리이 가장 가능성이 하나의 동일한 것을 측정 할 수

std::string second = "Harper v. The Law Offices of Huey & Luey, LLP"; 

인간.

std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp"; 

: 그리고 내가 촬영 한 현재의 접근 방식은 모든 문자를 lowercasing 모든 문장 부호를 제거하고 공간을 제공하여 문자열을 정상화하는 것입니다,이 경우 비교

std::string secondNormalized = "harpervthelawofficesofhueylueyllp"; 

을, 하나는 서브 순서는 다른 것의 더 복잡한 변이를 상상할 수도 있지만 반드시 그런 것은 아니지만 중요한 하위 서열은 공통적입니다. 문자가 바뀌거나 맞춤법 오류가있는 경우와 같이 사람이 입력 할 때가끔 오류가있을 수도 있습니다.

아마도 어떤 종류의 문자 diff 프로그램이 도움이 될 수 있습니까? 체크 인 할 코드의 차이를 비교하기위한 좋은 회선 diff 프로그램을 보았습니다. 문자 기반으로 비슷한 것이 있습니까? 연속되는 문자의 수를 세 어서 비공유 문자에 비유 할 수 있다면 아마도 좋은 경험 일 것입니다.

결국, 나는 그것들을 동일하게 간주 할 것인지 아닌지에 관해서 부울 결정이 필요합니다. 완벽 할 필요는 없지만 이상적이지는 않습니다.

어떤 알고리즘을 사용하면 2 개의 문자열이 서로 얼마나 유사한 지에 대한 몇 가지 종류의 양을 제공 할 수 있습니다. 그러면 어떤 추론을 통해 예/아니오 응답으로 변환 할 수 있습니까?

Answer 1

찾고있는 것은 String Metric 알고리즘입니다. 그곳에는 상당의 개의 숫자가 있으며, 많은 숫자가 비슷한 특성을 가지고 있습니다. 더 인기있는 중 :

• Levenshtein Distance : 다른에 한 단어를 변경하는 데 필요한 단일 문자 편집의 최소 수. 문자열의 길이는 동일하지 않아도됩니다.
• Hamming Distance : 두 개의 동일한 길이의 문자열에서 다른 문자 수입니다.
• Smith–Waterman : 가변 서브 시퀀스 유사성을 계산하기위한 알고리즘 패밀리.
• Sørensen–Dice Coefficient : 인접한 문자 쌍의 차이 계수를 계산하는 유사도 알고리즘입니다.

주제에 대한 wiki page에서 다른 사람과 함께 살펴보십시오.

Answer 2

Damerau Levenshtein distance은 두 문자열을 비교하는 또 다른 알고리즘이며 Levenshtein 거리 알고리즘과 유사합니다. 차이점은 두 문자 사이의 전치를 검사 할 수 있으므로 오류 수정에 더 나은 결과를 줄 수 있다는 것입니다.예를 들어

: night 및 nigth Levenshtein 사이의 거리가 2 이지만 문자 쌍의 단지 스왑 때문에 night 및 nigth Damerau Levenshtein 간의 거리가 1이 될 것이다.

Answer 3

당신은 ngrams를 사용할 수 있습니다. 예를 들어 두 문자열을 단어 trigrams (일반적으로 소문자)로 변환하고 서로 같은 비율을 비교합니다.

귀하의 도전 과제는 유사성의 최소 비율을 정의하는 것입니다.

http://en.wikipedia.org/wiki/N-gram