JavaScript에서 두 문자열의 유사도를 백분율로 계산하는 방법

두 개의 문자열을 비교하여 서로 얼마나 유사한지를 백분율(%) 형태로 반환하는 JavaScript 함수를 작성해 보겠습니다. 여기서 백분율은 두 문자열이 공유하는 문자의 정도를 수치화한 값입니다.

두 문자열이 완전히 동일하다면 결과는 100이 되고, 공통된 문자가 하나도 없다면 결과는 0이 됩니다.

접근 방식: 레벤슈타인 거리(Levenshtein Distance)

문자열 유사도를 측정하는 가장 널리 쓰이는 방법은 레벤슈타인 거리입니다. 이는 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 횟수(문자의 삽입·삭제·치환)를 의미합니다. 편집 거리가 작을수록 두 문자열은 더 유사하며, 이 값을 전체 문자열 길이에 대한 비율로 환산하면 유사도 백분율을 손쉽게 구할 수 있습니다.

예제 코드

const calculateSimilarity = (str1 = '', str2 = '') => {
    let longer = str1;
    let shorter = str2;
    if (str1.length < str2.length) {
        longer = str2; shorter = str1;
    }
    let longerLength = longer.length;
    if (longerLength == 0) {
        return 1.0;
    }
    return +((longerLength - matchDestructively(longer, shorter)) / parseFloat(longerLength) * 100).toFixed(2);
};
const matchDestructively = (str1 = '', str2 = '') => {
    str1 = str1.toLowerCase();
    str2 = str2.toLowerCase();
    let arr = new Array();
    for (let i = 0; i <= str1.length; i++) {
        let lastValue = i;
        for (let j = 0; j <= str2.length; j++) {
            if (i == 0){
                arr[j] = j;
            } else if (j > 0){
                let newValue = arr[j - 1];
                if (str1.charAt(i - 1) != str2.charAt(j - 1))
                    newValue = Math.min(Math.min(newValue, lastValue), arr[j]) + 1;
                arr[j - 1] = lastValue; lastValue = newValue;
            }
        }
        if (i > 0) arr[str2.length] = lastValue;
    }
    return arr[str2.length];
};
console.log(calculateSimilarity('Mathematics', 'Mathamatecs'));

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

81.82

'Mathematics'와 'Mathamatecs'는 철자가 두 곳만 다르므로 약 81.82%의 유사도를 갖는다는 것을 확인할 수 있습니다.

코드 설명

calculateSimilarity 함수는 먼저 두 문자열 중 더 긴 쪽을 기준 문자열로 정합니다. 두 문자열이 모두 빈 문자열일 경우에는 1.0, 즉 100%를 반환합니다.

실질적인 유사도 계산은 matchDestructively 함수가 담당합니다. 이 함수는 두 문자열을 모두 소문자로 변환한 뒤, 동적 프로그래밍(Dynamic Programming) 기법으로 레벤슈타인 거리를 계산합니다. 특히 2차원 행렬 대신 1차원 배열을 사용하여 메모리 사용량을 줄인 점이 특징입니다.

마지막으로, 기준 문자열의 전체 길이에서 편집 거리를 뺀 값을 길이로 나누고 100을 곱해 백분율로 변환한 후, toFixed(2)를 통해 소수점 둘째 자리까지 반올림하여 반환합니다.