[PHP] levenshtein로 유사 검색어 추천 기능 만들기

안녕하세요. 

오늘은 levenshtein로 유사 검색어 추천 기능을 만들어보겠습니다. 

 

사용자가 검색창에 '오랜지'라고 오타를 쳤을 때, "혹시 '오렌지'를 찾으셨나요?"라고 되물어보는 기능을  levenshtein()과 similar_text() 함수로 만들어보겠습니다.

levenshtein(string1, string2)
- '편집 거리(Edit Distance)'를 계산하는 함수입니다.
- 한 문자열을 다른 문자열로 바꾸기 위해 몇 글자를 수정(추가, 삭제, 변경)해야 하는지 그 횟수를 정수로 반환합니다.
- 이 함수는 글자(character) 단위가 아닌 바이트(byte) 단위로 계산합니다.

   - levenshtein('apple', 'apply') (영어) -> 1 (e -> y)
   - levenshtein('오랜지', '오렌지') (한글) -> 2
   - UTF-8 환경에서 '랜'과 '렌'은 우리 눈에는 한 글자 차이지만, 내부적으로는 각각 3바이트로 표현되며 이 중 2개의 바이트가 다르기 때문입니다.
- 값이 0에 가까울수록 두 문자열은 매우 유사합니다.

similar_text(string1, string2, &$percent)
- 두 문자열이 얼마나 유사한지 바이트(byte) 단위로 비교합니다.
- 세 번째 인자에 변수를 넣으면, 그 변수에 유사도를 퍼센트(%)로 담아줍니다.
- 값이 100에 가까울수록 매우 유사합니다.

 

예제

<?php

// 사용자의 오타 검색어
$userInput = '오랜지';

// 검색어 추천을 위한 키워드 목록 (DB에 저장되어 있다고 가정)
$keywords = ['사과', '바나나', '포도', '오렌지', '딸기'];

// 가장 가까운 단어를 찾기 위한 변수
$shortestDistance = -1; // -1은 아직 아무것도 비교하지 않았다는 의미
$bestMatch = '';

// 모든 키워드를 순회하며 사용자의 입력과 비교
foreach ($keywords as $keyword) {
    // Levenshtein 편집 거리를 계산
    $distance = levenshtein($userInput, $keyword);

    // 가장 거리가 짧은 단어를 찾는다 (최초이거나, 더 짧은 거리를 찾았을 때)
    if ($shortestDistance == -1 || $distance < $shortestDistance) {
        $shortestDistance = $distance;
        $bestMatch = $keyword;
    }
}

// 추천 임계값 설정 (편집 거리가 2 이하일 때만 추천)
$threshold = 2;

echo "사용자 입력: " . $userInput . "\n\n";

if ($shortestDistance <= $threshold && $shortestDistance != 0) {
    echo "가장 유사한 단어: $bestMatch (편집 거리: $shortestDistance)\n";
    echo ">> 혹시 '$bestMatch'을(를) 찾으셨나요?\n";
} else {
    echo "유사한 검색어를 찾지 못했습니다.\n";
}


// --- 보너스: similar_text() 비교 ---
similar_text('오랜지', '오렌지', $percent);
echo "\n--- similar_text() 비교 ---\n";
echo "'오랜지'와 '오렌지'의 유사도: " . round($percent, 2) . "%\n";

?>

 

사용자 입력: 오랜지 

가장 유사한 단어: 오렌지 (편집 거리: 2) 
>> 혹시 '오렌지'을(를) 찾으셨나요? 

--- similar_text() 비교 ---
'오랜지'와 '오렌지'의 유사도: 77.78%