레벤슈타인 거리:단어 교환 위치를 더 잘 처리하는 방법은 무엇입니까?

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

문제

PHP를 사용하여 문자열을 비교하는 데 성공했습니다. 레벤슈타인 기능.

그러나 위치가 바뀐 부분 문자열을 포함하는 두 문자열의 경우 알고리즘은 이를 완전히 새로운 부분 문자열로 계산합니다.

예를 들어:

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

가지고 있는 것으로 취급된다 덜 공통점 보다:

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

나는 다음을 본 알고리즘을 선호합니다. 처음 두 개 더 비슷했어요.

위치가 변경된 하위 문자열을 편집 내용과 구별되는 것으로 식별할 수 있는 비교 기능을 어떻게 만들 수 있습니까?

내가 생각한 한 가지 가능한 접근 방식은 비교 전에 문자열의 모든 단어를 알파벳 순서로 배치하는 것입니다.그러면 단어의 원래 순서가 비교에서 완전히 제외됩니다.그러나 이 방법의 단점은 단어의 첫 글자만 바꾸는 것이 글자 하나를 바꾸는 것보다 훨씬 더 큰 혼란을 야기할 수 있다는 것입니다.

내가 달성하려는 것은 자유 텍스트 문자열인 사람들에 대한 두 가지 사실을 비교하고 이러한 사실이 동일한 사실을 나타낼 가능성을 결정하는 것입니다.예를 들어, 사실은 누군가가 다녔던 학교, 고용주 또는 출판사의 이름일 수 있습니다.두 개의 기록이 동일한 학교의 철자가 다르거나, 단어의 순서가 다르거나, 추가 단어 등이 있을 수 있으므로 동일한 학교를 참조한다고 추측하려면 일치가 다소 모호해야 합니다.지금까지는 철자 오류에 대해 매우 잘 작동하지만(이 모든 것 외에도 메타폰과 유사한 음성 알고리즘을 사용하고 있습니다) 학교에서 일반적으로 보이는 단어의 순서를 바꾸면 매우 제대로 작동하지 않습니다."xxx 대학" 대 "xxx 대학".

도움이 되었습니까?

해결책

n- 그램

사용 n- 그램, 어떤 지원 전체 텍스트에 걸쳐 다중 특성 전치.

일반적인 아이디어는 문제의 두 줄을 가능한 모든 2-3 문자 하위 문자 (N- 그램)로 나누고 두 문자열 사이의 공유 N- 그램의 수를 유사성 메트릭으로 취급한다는 것입니다. 그런 다음 공유 숫자를 더 긴 문자열에서 총 n 그램 수로 나누어 정규화 할 수 있습니다. 이것은 계산하기가 사소하지만 상당히 강력합니다.

예제 문장의 경우 :

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

A 및 B 공유 18 2 그램

A와 C는 만 공유합니다 8 2 그램

밖으로 20 총 가능.

이것은 더 자세히 논의되었습니다 Gravano et al. 종이.

TF-IDF 및 코사인 유사성

그렇게 사소한 대안은 아니지만 정보 이론에 근거한 것은 용어를 사용하는 것입니다. 기간 주파수-반대 문서 주파수 (TF-IDF) 토큰의 무게를 측정하려면 문장 벡터를 구성한 다음 사용하십시오. 코사인 유사성 유사성 메트릭으로.

알고리즘은 다음과 같습니다.

  1. 문장 당 2 자 토큰 주파수 (TF)를 계산하십시오.
  2. 코퍼스 (이 경우 3)의 모든 문장 수의 지수의 로그 인 IDF (역 문장 주파수)를 계산합니다. (이 경우 3) 특정 토큰이 모든 문장에 나타나는 횟수로 나뉩니다. 이 경우 th 모든 문장에 있으므로 정보 내용이 0이 없습니다 (log (3/3) = 0).idf formula
  3. TF 및 IDF 테이블에 해당 셀을 곱하여 TF-IDF 매트릭스를 생성합니다.tfidf
  4. 마지막으로, 모든 문장 쌍에 대한 코사인 유사성 행렬을 계산합니다. 여기서 A와 B는 해당 토큰의 TF-IDF 테이블의 가중치입니다. 범위는 0 (유사하지 않음)에서 1 (동일)입니다.
    cosine similarity
    similarity matrix

Levenshtein 변형 및 은유

다른 답변에 관해. Damerau – Levenshtein 변형은 전치 만 지원합니다 인접한 두 개 캐릭터. 은유 유사성 일치가 아닌 동일하게 들리는 단어와 일치하도록 설계되었습니다.

다른 팁

그것은 간단합니다. 그냥 사용하십시오 Damerau-Levenshtein 글자 대신 단어의 거리.

공간에서 폭발하고, 배열을 정렬하고, 멸시 한 다음 Levenshtein을 수행하십시오.

당신은 또한 이것을 시도 할 수 있습니다. (추가 제안)

$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

이것은 첫 번째와 2nd가 1과 3과 2, 3과 더 유사하다는 것을 보여줍니다.

맞춤법 검사기에서 Levenshtein을 구현했습니다.

당신이 요구하는 것은 전치를 1 편집으로 계산하는 것입니다.

한 단어의 전치를 계산하려는 경우 쉽습니다. 그러나 2 개 이상의 단어의 전치의 경우 알고리즘에 추가되는 것은 최악의 시나리오입니다. !(max(wordorder1.length(), wordorder2.length())). 이미 2 차 알고리즘에 비선형 하위 계산을 추가하는 것은 좋은 생각이 아닙니다.

이것이 작동하는 방법입니다.

if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

전치를 터치하기 만하면됩니다. 모든 전치를 원한다면 모든 위치에 대해 해당 지점에서 뒤로 작업해야합니다.

1[n] == 2[n-2].... 1[n] == 2[0]....

따라서 왜 표준 방법에 이것을 포함시키지 않는지 알 수 있습니다.

가져가다 이 답변 다음과 같은 변경을 수행하십시오.

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

이것은 트리에서 사전 검색을위한 것이지만, 한 단어와 일치하는 것은 같은 아이디어입니다. 당신은 지점과 바운드를하고 있으며 언제든지 비용을 지불하는 한 원하는 변경을 할 수 있습니다.

두 줄 사이의 중복 단어를 제거한 다음 Levenshtein을 사용하십시오.

나는 이것이 벡터 공간 검색 엔진.

이 기술에서 각 문서는 본질적으로 전체 말뭉치에 있는 다양한 단어 수만큼 많은 차원을 가진 벡터가 됩니다.유사한 문서는 해당 벡터 공간에서 인접한 영역을 차지합니다.이 모델의 좋은 특성 중 하나는 쿼리가 문서일 수도 있다는 것입니다.쿼리에 답하려면 벡터 공간에서 해당 위치를 계산하면 됩니다. 결과는 찾을 수 있는 가장 가까운 문서입니다.나는 PHP를 위한 즉시 사용 가능한 솔루션이 있다고 확신합니다.

벡터 공간의 결과를 퍼지화하려면 형태소 분석/유사한 자연어 처리 기술을 수행하고 levenshtein을 사용하여 전체 어휘에서 발생하는 유사한 단어에 대한 보조 쿼리를 구성하는 것을 고려할 수 있습니다.

첫 번째 문자열이 A이고 두 번째 문자열이 B입니다.

  1. A와 B를 단어로 나눕니다
  2. A의 모든 단어에 대해 B에서 가장 잘 어울리는 단어를 찾으십시오 (Levenshtein 사용)
  3. B에서 그 단어를 제거하고 A의 일치하는 단어와 같은 색인으로 b*에 넣으십시오.
  4. 이제 A와 B*를 비교하십시오.

예시:

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

여러 패스로 수행하여 2 단계를 개선하고 처음에는 정확히 일치 만 찾은 다음 B*의 동반자가없는 A에서 단어에 대한 가까운 경기를 찾은 다음 덜 가까운 경기 등을 찾을 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top