Forum und email
문자열
PHP Manual

levenshtein

(PHP 4 >= 4.0.1, PHP 5)

levenshtein — 두 문자열 사이의 Levenshtein distance를 계산합니다.

설명

int levenshtein ( string $str1 , string $str2 )
int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )
int levenshtein ( string $str1 , string $str2 , function $cost )

이 함수는 두 문자열 인자 사이의 Levenshtein-Distance를 반환합니다. 문자열 인자 중 하나가 255 문자 제한을 넘어갈 경우에는 -1을 반환합니다. (255는 이름이나 사전 비교에 충분하며, 누구도 PHP로 복잡한 일반 분석을 행하지 않습니다)

Levenshtein distance는 str1 를 str2 로 변환할 때 필요한 치환, 삽입, 삭제할 최소 문자 수로 정의됩니다. O(m*n)의 복잡한 알고리즘입니다. 여기서 n과 m은 str1 과 str2 의 길이입니다. (similar_test()의 O(max(n,m)**3)과 비교하면 좋지만, 여전히 비쌉니다)

함수의 가장 간단한 형식은 두 문자열을 받아서, str1 을 str2 로 변환하는데 필요한 삽입, 치환, 삭제 시행 수를 계산합니다.

두번째 형식은 삽입, 치환, 삭제 시행의 비용을 정의하는 세개의 추가 인자를 줄 수 있습니다. 이는 더욱 일반적이고 적용성이 높지만, 효율적이지 않습니다.

세번째 형식은 (아직 사용할 수 없습니다) 가장 일반적이고 적용성이 높지만, 또한 가장 느린 방법입니다. 이는 모든 시행의 비용을 계산하는 사용자 제공 함수를 호출합니다.

사용자 제공 함수는 다음 인자로 호출합니다:

  • 적용하는 시행: 'I', 'R' or 'D'
  • 문자열 1의 해당 문자
  • 문자열 2의 해당 문자
  • 문자열 1의 위치
  • 문자열 2의 위치
  • 문자열 1의 나머지 문자
  • 문자열 2의 나머지 문자
사용자 제공 함수는 해당하는 시행의 비용을 나타내는 양의 정수를 반환해야 합니다. 제공한 인자의 일부만을 사용하여 결정하여도 됩니다.

The user-supplied function approach offers the possibility to take into account the relevance of and/or difference between certain symbols (characters) or even the context those symbols appear in to determine the cost of insert, replace and delete operations, but at the cost of losing all optimizations done regarding cpu register utilization and cache misses that have been worked into the other two variants.

참고: soundex(), similar_text(), metaphone().

문자열
PHP Manual