JavaScript에서 문자열에 대해 느슨하게(loosely) 검색어를 확인하는 퍼지 검색 함수를 구현해 보겠습니다. 퍼지 검색은 검색어가 정확히 일치하지 않더라도, 검색어의 각 글자가 대상 문자열에 순서대로 포함되어 있으면 일치로 판단하는 방식입니다. 자동 완성 기능이나 빠른 필터링 UI를 만들 때 유용하게 활용됩니다.
퍼지 검색의 판정 조건
이 함수는 다음 기준을 충족해야 합니다.
- 검색어(query)의 각 문자를 앞에서부터 순서대로 순회하면서,
- 각 문자가 대상 문자열에서 동일한 순서로 등장하는지 확인합니다.
예를 들면 다음과 같습니다.
('a haystack with a needle').fuzzySearch('hay sucks'); // false
('a haystack with a needle').fuzzySearch('sack hand'); // true'hay sucks'는 false를 반환합니다. 'u'가 'hay' 뒤에서 순서대로 발견되지 않기 때문입니다. 반면 'sack hand'는 true를 반환하는데, s → a → c → k → h → a → n → d가 모두 원본 문자열에 순서를 유지한 채 존재하기 때문입니다.
구현 예제
const fuzzySearch = function (query) {
const str = this.toLowerCase();
let i = 0, n = -1, l;
query = query.toLowerCase();
for (; l = query[i++] ;){
if (!~(n = str.indexOf(l, n + 1))){
return false;
};
};
return true;
};
String.prototype.fuzzySearch = fuzzySearch;
console.log(('a haystack with a needle').fuzzySearch('hay sucks'));
console.log(('a haystack with a needle').fuzzySearch('sack hand'));코드 동작 원리
이 알고리즘의 핵심 로직을 단계별로 살펴보겠습니다.
- 대소문자 통일: 대상 문자열과 검색어를 모두
toLowerCase()로 소문자화하여, 대소문자 구분 없이 비교할 수 있도록 합니다. - 순차 탐색:
indexOf(l, n + 1)을 사용해 이전에 찾은 위치(n)의 다음 인덱스부터 해당 문자를 검색합니다. 이렇게 하면 각 문자가 항상 이전 문자보다 뒤에서 발견되므로, 전체적인 순서가 보장됩니다. - 비트 연산 활용:
!~는indexOf가 -1(문자 미발견)을 반환했는지 검사하는 간결한 방법입니다.~(-1)은 0이 되고,!0은 true가 되므로 문자를 찾지 못한 즉시 false를 반환합니다.
모든 문자를 순서대로 찾았다면 루프가 정상적으로 종료되고 최종적으로 true를 반환합니다.
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
false
true