단어 비교 알고리즘

StackOverflow https://stackoverflow.com/questions/473522

문제

내가 작업중 인 프로젝트를 위해 CSV 가져 오기 도구를하고 있습니다. 클라이언트는 Excel에서 데이터를 입력하여 CSV로 내보내고 데이터베이스에 업로드 할 수 있어야합니다. 예를 들어이 CSV 레코드가 있습니다.

   1,   John Doe,     ACME Comapny   (the typo is on purpose)

물론 회사는 별도의 테이블에 보관되어 외국 키와 연결되어 있으므로 삽입하기 전에 올바른 회사 ID를 발견해야합니다. 데이터베이스의 회사 이름을 CSV의 회사 이름과 비교하여이를 수행 할 계획입니다. 문자열이 정확히 동일하면 비교는 0을 반환해야하며 문자열이 더 다르면 더 커지는 값을 반환하지만 strcmp는 다음과 같이 여기에서 잘리지 않습니다.

"Acme Company"및 "Acme Comapny"는 매우 작은 차이 지수를 가져야하지만 "Acme Company"및 "CMEA Mpnyaco"는 매우 큰 차이 지수 또는 "ACME Company"및 "ACME Comp"를 가져야합니다. 문자 수가 다르더라도 작은 차이 지수를 가져야합니다. 또한 "Acme Company"및 "Company Acme"는 0을 반환해야합니다.

따라서 클라이언트가 데이터를 입력하는 동안 유형을 만드는 경우 삽입하려는 이름을 선택하라는 메시지가 표시 될 수 있습니다.

이 작업을 수행 할 알려진 알고리즘이 있습니까? 아니면 하나를 발명 할 수 있습니까? :)?

도움이 되었습니까?

해결책

당신은 그것을 확인하고 싶을 수도 있습니다 Levenshtein 거리 시작점으로 알고리즘. 두 단어 사이의 "거리"를 평가합니다.

이 스레드 Google 스타일을 구현할 때 "당신은 ...?" 시스템은 몇 가지 아이디어를 제공 할 수 있습니다.

다른 팁

어떤 언어로 코딩하는지 모르겠지만 PHP 인 경우 다음 알고리즘을 고려해야합니다.

Levenshtein (): 하나의 문자열을 다른 문자열로 변환하려면 교체, 삽입 또는 삭제 해야하는 최소한의 문자 수를 반환합니다.
soundex (): 단어의 4 자 Soundex 키를 반환합니다.
은유 (): Soundex와 유사하며 아마도 더 효과적입니다. 영어 발음의 기본 규칙을 알고 있기 때문에 soundex ()보다 더 정확합니다. 은유 생성 키는 길이가 다양합니다.
유사 _text (): Levenshtein ()과 유사하지만 대신 백분율 값을 반환 할 수 있습니다.

나는 성공했다 Levenshtein 거리 알고리즘도 있습니다 Soundex.

어떤 언어를 구현하고 있습니까? 우리는 구체적인 예를 지적 할 수 있습니다

실제로 비슷한 시스템을 구현했습니다. 나는 Levenshtein 거리 (다른 포스터가 이미 제안한 것처럼)를 약간 수정하여 사용했습니다. 수정되지 않은 편집 거리 (전체 문자열에 적용)의 문제점은 단어 재정렬에 민감하다는 것입니다. 따라서 "ACME Digital Incorporated World Company"는 "Digital Incorporated World Company ACME"와 제대로 일치하지 않으며 이러한 재정렬은 내 데이터에서 매우 일반적이었습니다.

전체 문자열의 편집 거리가 너무 커지면 알고리즘이 서로 어울리는 단어로 돌아와서 좋은 단어 대 단어 일치 (2 차 비용이지만 너무 많은 경우 컷오프가있었습니다. 단어, 그래서 괜찮 았습니다).

Soundex, Levenshtein, PHP 유사성 및 이중 은유를 가져 와서 문자열의 한 세트의 확장 방법으로 C#에 포장했습니다.

전체 블로그 게시물.

이를 수행 할 여러 알고리즘이 있으며 대부분의 데이터베이스에는 기본적으로 하나도 포함됩니다. 실제로는 매우 일반적인 관심사입니다.

영어 단어에 관한 경우, SQL Server와 같은 SQL Server에는 SoundEx가 포함되어 있으며, 이는 단어의 결과 사운드를 비교하는 데 사용할 수 있습니다.

http://msdn.microsoft.com/en-us/library/aa259235%28sql.80%29.aspx

나는 PHP에서 그것을 구현하고 있으며, 이제 2 개의 문자열을 단어로 나누고 첫 번째 문자열의 각 단어를 Levenshtein을 사용하여 두 번째 문자열의 단어와 비교하고 가능한 값을 수락하는 코드를 작성하고 있습니다. . 내가 끝났을 때 게시 할게.

정말 감사합니다.

업데이트 : 다음은 다음과 같습니다.

function myLevenshtein( $str1, $str2 )
{
  // prepare the words
  $words1 = explode( " ",  preg_replace( "/\s+/", " ", trim($str1) ) );
  $words2 = explode( " ",  preg_replace( "/\s+/", " ", trim($str2) ) );

  $found = array(); // array that keeps the best matched words so we don't check them again
  $score = 0;       // total score
  // In my case, strings that have different amount of words can be good matches too
  // For example, Acme Company and International Acme Company Ltd. are the same thing
  // I will just add the wordcount differencre to the total score, and weigh it more later if needed
  $wordDiff = count( $words1 ) - count( $words2 );
  foreach( $words1 as $word1 )
  {
    $minlevWord = "";
    $minlev = 1000;
    $return = 0;
    foreach( $words2 as $word2 )
    {
      $return = 1;
      if( in_array( $word2, $found ) )
        continue;
      $lev = levenshtein( $word1, $word2 );
      if( $lev < $minlev )
      {
        $minlev = $lev;
        $minlevWord = $word2;
      }
    }
    if( !$return )
      break;
    $score += $minlev;
    array_push( $found, $minlevWord );
  }

  return $score + $wordDiff;
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top