퍼지 검색(fuzzy search) 구현법, 편집 거리와 트라이그램 비교

게시 2026.07.15 · 약 6분 분량

퍼지 검색(fuzzy search)은 입력한 검색어와 글자가 정확히 맞지 않아도 오타나 표기 차이를 감안해 충분히 비슷한 문자열을 찾아 주는 검색이다. 핵심 원리는 두 갈래로 나뉜다. 한 문자열을 다른 문자열로 바꾸는 데 필요한 편집 횟수를 세는 편집 거리(edit distance), 그리고 문자열을 세 글자 조각으로 쪼개 겹치는 비율을 재는 트라이그램(trigram)이다. 2026년 7월 기준 Elasticsearch·PostgreSQL·Fuse.js·RapidFuzz의 공식 문서에 정의된 기본 동작을 바탕으로 정리한다. 이 글은 특정 서비스의 사용법이 아니라 네 도구의 알고리즘과 기본 임계값, 실행 위치를 비교해 상황에 맞게 고르는 것을 다룬다.

퍼지 검색이란 무엇인가

퍼지 검색은 검색어와 글자가 정확히 맞지 않아도 충분히 비슷한 문자열을 찾아 주는 검색이다. 사용자가 검색창에 kuvernetes라고 잘못 쳐도 kubernetes 문서를 돌려주는 동작이 대표적이다. 정확 일치(exact match)만 지원하는 검색은 오타 한 글자에 결과가 0건이 되지만, 퍼지 검색은 그 차이를 수치로 재서 감안한다.

실무에서 쓰이는 자리는 분명하다. 검색창의 오타 허용, 입력 중 자동완성, 이름·주소가 조금씩 다르게 적힌 레코드를 하나로 묶는 중복 제거(record linkage), 로그나 코드에서 근사 문자열을 찾는 작업이 여기에 해당한다. 반대로 정확성이 생명인 식별자 조회(주문번호·계좌번호)나 완전 일치가 요구되는 곳에는 쓰지 않는다.

편집 거리로 오타를 숫자로 재기

편집 거리는 문자열 A를 B로 바꾸는 데 필요한 최소 편집 횟수다. 가장 널리 쓰이는 레벤슈타인 거리(Levenshtein distance)는 글자 삽입·삭제·치환 세 가지를 각 1회로 센다. 예를 들어 book을 back으로 바꾸려면 가운데 두 글자를 치환해야 하므로 거리는 2다. 여기에 인접한 두 글자의 자리 바꿈까지 1회로 세는 변형이 다메라우-레벤슈타인 거리다.

Elasticsearch의 fuzzy 쿼리가 이 편집 거리를 쓴다. Elastic 공식 문서에 따르면 fuzziness 값을 AUTO로 두면 검색어 길이에 따라 허용 거리를 자동으로 정한다. 길이가 0~2자면 편집 거리 0(정확 일치), 3~5자면 1, 6자 이상이면 2까지 허용한다. 내부 엔진인 Lucene의 제약으로 최대 편집 거리는 2를 넘지 못한다.

GET /docs/_search
{
 "query": {
  "match": {
   "title": { "query": "kuvernetes", "fuzziness": "AUTO" }
  }
 }
}

편집 거리는 사람이 내는 오타, 즉 한 글자를 빠뜨리거나 잘못 누르거나 자리를 바꾼 실수를 직관적으로 잡는다. 다만 검색어가 짧을수록 허용 범위가 좁아지고, 거리 계산 자체가 후보 문자열마다 필요해 대상이 많으면 비용이 커진다.

트라이그램은 편집 거리와 어떻게 다른가

편집 거리가 몇 번 고쳐야 같아지나를 센다면, 트라이그램은 문자 조각을 얼마나 공유하나를 잰다. 트라이그램은 문자열을 연속된 세 글자 단위로 쪼갠 조각이다. 두 문자열을 각각 조각 집합으로 만든 뒤 겹치는 조각의 비율로 닮은 정도를 계산한다. 오타 때문에 조각 몇 개가 어긋나도 나머지가 겹치면 여전히 비슷하다고 판정한다.

PostgreSQL의 pg_trgm 확장이 이 방식이다. PostgreSQL 공식 문서 기준 유사도 임계값 파라미터 pg_trgm.similarity_threshold의 기본값은 0.3이고, 두 문자열이 이 값보다 비슷하면 참을 돌려주는 % 연산자가 이 기준을 쓴다. 대량 데이터에서 빠르게 찾으려면 GIN 또는 GiST 인덱스를 걸어야 한다.

CREATE EXTENSION pg_trgm;
CREATE INDEX ON docs USING GIN (title gin_trgm_ops);

SELECT title, similarity(title, 'postgres') AS sml
FROM docs
WHERE title % 'postgres'
ORDER BY sml DESC;

트라이그램은 단어 순서가 조금 바뀌거나 부분 문자열이 섞여도 견디는 편이라, 이름·주소처럼 표기가 들쭉날쭉한 데이터의 근사 매칭에 잘 맞는다.

구현 도구 네 가지 비교

퍼지 검색은 검색 엔진, 데이터베이스, 클라이언트 라이브러리 어디에나 넣을 수 있다. 데이터가 어디 있고 검색을 어디서 실행하느냐에 따라 선택이 갈린다. 아래는 대표 도구 네 가지를 알고리즘·실행 위치·기본 기준값으로 비교한 표다.

이미 Elasticsearch나 PostgreSQL에 데이터가 있다면 별도 라이브러리 없이 위 기능만으로 끝나는 경우가 많다. 반면 목록이 작고 브라우저 안에서 즉시 걸러야 하면 Fuse.js가 맞는다. Fuse.js는 Bitap 알고리즘으로 편집 거리를 근사 계산하는 자바스크립트 라이브러리다. Fuse.js 공식 문서에 따르면 threshold 기본값은 0.6이며, 0에 가까울수록 정확한 일치를 요구하고 1이면 무엇이든 매치한다.

import Fuse from 'fuse.js'

const fuse = new Fuse(list, { keys: ['title'], threshold: 0.3 })
const results = fuse.search('kuvernetes')

파이썬에서 목록 대 목록을 배치로 대조하거나 점수를 직접 다루고 싶다면 RapidFuzz가 있다. RapidFuzz 저장소 설명에 따르면 이 라이브러리는 기존 fuzzywuzzy의 대체재로 쓸 수 있고, 대부분 C++로 작성됐으며 MIT 라이선스로 공개돼 있다. fuzz.ratio 같은 점수 함수는 0~100 사이 유사도를 돌려준다.

성능과 정확도의 균형 잡기

임계값을 낮추면 더 많이 걸리지만 엉뚱한 결과(오탐)가 늘고, 높이면 정확해지는 대신 진짜 오타를 놓친다. 정답은 데이터와 용도마다 다르므로 실제 검색어로 맞춰 가는 수밖에 없다. Fuse.js 공식 문서는 입력 중 실시간 검색에는 threshold를 0.3~0.4로 두기를 권한다.

속도는 인덱스가 좌우한다. pg_trgm은 GIN·GiST 인덱스 없이 쓰면 매 행을 훑어 느려지므로, 운영에서는 인덱스가 사실상 필수다. Elasticsearch는 역색인 위에서 편집 거리 확장을 돌려 대량 문서에서도 견딘다. 반대로 Fuse.js는 클라이언트 메모리에서 도는 만큼 목록이 수천 건을 넘으면 부담이 된다.

도구별 제약도 미리 알아 두면 좋다. Fuse.js 공식 문서에 따르면 Bitap 구현의 검색어 길이는 32자로 제한되고, 기본 설정은 문자열 앞 60자 안에서만 매치를 찾는다. 문서 뒤쪽까지 보려면 ignoreLocation 옵션을 켜야 한다.

선택 기준은 단순하다. 서버에 이미 검색 엔진이나 PostgreSQL이 있으면 그 안의 퍼지 기능을 먼저 쓰고, 목록이 작고 프런트에서 즉시 걸러야 하면 Fuse.js, 파이썬 배치 대조에는 RapidFuzz다. 어느 쪽이든 기본 임계값에서 시작해 실제 오타 사례로 조정하는 과정을 거쳐야 원하는 결과에 닿는다.