라이브러리
[PHP] levenshtein - 두 문자열 사이의 Levenshtein 거리 계산
Levenshtein 거리란 무엇인가?
Levenshtein 거리는 두 문자열 사이의 편집 거리를 측정하는 알고리즘입니다. 편집 거리는 두 문자열을 하나의 문자열로 변환하는 데 필요한 최소한의 연산 수를 의미합니다. Levenshtein 거리는 다음과 같은 편집 연산을 수행할 수 있습니다.
- 삽입 (Insertion): 한 문자열에 문자를 추가합니다.
- 삭제 (Deletion): 한 문자열에서 문자를 삭제합니다.
- 교체 (Substitution): 한 문자열에서 문자를 다른 문자로 교체합니다.
Levenshtein 거리 계산 알고리즘
Levenshtein 거리 계산 알고리즘은 다음과 같이 수행됩니다.
1. 두 문자열의 길이를 비교합니다.
2. 두 문자열의 첫 번째 문자를 비교합니다. 만약 두 문자가 같다면, 두 문자열의 첫 번째 문자를 제거하고, 1을 더합니다.
3. 두 문자열의 첫 번째 문자를 비교합니다. 만약 두 문자가 같지 않다면, 두 문자열의 첫 번째 문자를 교체하고, 1을 더합니다.
4. 두 문자열의 첫 번째 문자를 삭제하고, 1을 더합니다.
5. 두 문자열의 첫 번째 문자를 삽입하고, 1을 더합니다.
6. 위의 과정을 반복합니다.
PHP에서 Levenshtein 거리 계산
PHP에서 Levenshtein 거리 계산을 위해, `levenshtein` 함수를 사용할 수 있습니다. 이 함수는 두 문자열의 Levenshtein 거리를 반환합니다.
#hostingforum.kr
php
function levenshtein($str1, $str2) {
$m = strlen($str1);
$n = strlen($str2);
$dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
for ($i = 0; $i <= $m; $i++) {
$dp[$i][0] = $i;
}
for ($j = 0; $j <= $n; $j++) {
$dp[0][$j] = $j;
}
for ($i = 1; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {
if ($str1[$i - 1] == $str2[$j - 1]) {
$dp[$i][$j] = $dp[$i - 1][$j - 1];
} else {
$dp[$i][$j] = 1 + min($dp[$i - 1][$j], $dp[$i][$j - 1], $dp[$i - 1][$j - 1]);
}
}
}
return $dp[$m][$n];
}
$str1 = "kitten";
$str2 = "sitting";
echo "Levenshtein 거리: " . levenshtein($str1, $str2);
이 예제에서는 `levenshtein` 함수를 사용하여 두 문자열 `"kitten"`과 `"sitting"`의 Levenshtein 거리를 계산합니다. 결과는 3입니다.
-
- 나우호스팅 @pcs8404
-
호스팅포럼 화이팅!
댓글목록
등록된 댓글이 없습니다.