UI 작업을 하다보면 목록을 검색해야 할 때가 많다. 그런데 사람의 기억이라는 게 정확하지 않아서 혹은 전부 입력하기 귀찮아서 개떡같이 일부만 입력해도 찰떡같이 원하는 결과를 보여주는 UI가 필요하다. 예를 들어, 개발자들이 사용하는 여러 에디터에는 다음과 같이 대충 입력하면 일치하는 경로를 찾아서 보여주는 기능이 있다.
정확히 일치하지는 않더라도 대충 비슷한 느낌의 문자열을 찾아주는 방법, 즉 퍼지 문자열 매칭(fuzzy string matching)은 굳이 정규표현식으로 작성할 필요가 없을만큼 이미 다양한 방식으로 구현되어 있다. 대체로 입력한 문자열과 대상 문자열이 얼마나 일치하는지 거리를 반환하며 금방 검색해서 찾을 수 있는 것만 해도 Levenshtein, N-grams, Q-grams, Hamming, Jaro-Winkler, Jaccard 등 다양한 알고리듬이 존재한다. 이름을 알만한 언어에서는 이미 구현된 라이브러리가 존재할테니 관심있으면 코드를 살펴보는 것도 좋다.
그런데 만들고 싶었던 것은 검색을 위한 정규표현식이었다. 굳이 외부 패키지의 힘을 빌리지 않아도 될 것 같았고 알고리듬을 구현하는 것보다는 더 간단하게 내 요구사항인 '목록에서 퍼지 검색도 되는데 초성도 지원했으면 좋겠다'를 해결할 수 있을 것 같아서였다. 결론부터 말하면 세상일이 그렇게 호락호락하지는 않다.
영문 검색
일단 직관적으로도 골치가 아플 것 같은 한글 처리는 제쳐두고 영문자부터 시작해보자. 가장 간단하게는 '입력한 글자 사이에 어떤 문자든 올 수 있다'는 규칙만 세워두면 된다. 함수로 작성해보면 다음과 같을 것이다.
function createFuzzyMatcher(input) {
// escapeRegExp는 lodash에서 가져옴
const pattern = input.split('').map(escapeRegExp).join('.*?');
return new RegExp(pattern);
}
const regex = createFuzzyMatcher('ct');
regex.test('fact'); // true
regex.test('cats'); // true
regex.test('bats'); // false위 예시에서 createFuzzyMatcher는 /c.*?t/라는 정규표현식을 반환하고 그 결과 fact와 cats가 일치하는 문자열이 된다. 단순하고 이해하기에도 어렵지 않다. 심지어 이 함수는 한글에 이대로 적용해도 잘 동작한다. 다만 원래 의도했던 초성 검색이나 부분 글자 검색('가'를 입력하면 '간'도 보여주는 기능)도 안되고 글자 간 거리에 따른 가중치도 없지만 말이다. 그렇다면 이제 두 가지 기능을 더 추가해보도록 하자.
한글 검색
'한글'이라는 글자를 입력하는 과정을 생각해보자. 한글 입력 체계에서는 1글자를 작성하려면 보통 몇 단계의 조합 과정을 거치는데, '한'의 경우에는 'ㅎ' → '하' → '한'의 과정을 거치게 된다. 그리고 나를 비롯해 성격 급한 다수의 한국어 사용자는 'ㅎ'만 입력해도 '한'이 검색되기를 바란다.
유니코드 체계에서 한글 문자는 일정한 규칙에 따라 나열되어 있고 각 자음의 시작 문자는 언제나 'ㅏ' 모음과 합쳐진 글자가 되고 각 자음의 마지막 문자는 언제나 'ㅣ' 모음과 'ㅎ' 받침이 합쳐진 글자가 된다. 예를 들어 'ㄷ'이라면 첫 문자가 '다'이고, 마지막 문자는 '딯'이 된다. 두 문자 사이에 있는 글자의 갯수는 동일하기 때문에 각 자음의 첫 문자와 마지막 문자의 코드 번호 차이는 항상 587로 동일하다.
const diff1 = '깋'.charCodeAt(0) - '가'.charCodeAt(0)
const diff2 = '딯'.charCodeAt(0) - '다'.charCodeAt(0)
console.assert(diff1 === diff2)자바스크립트에서 임의의 온전한 한 음절, 다시 말해 초성과 모음을 갖춘 글자의 코드는 다음과 같이 정해진다.
( 자음번호 * 588 + 모음번호 * 28 + 종성번호 ) + 44032
자음번호는 'ㄱ' = 0 부터 시작해서 순차적으로 증가하고 모음번호는 'ㅏ' = 0부터 시작해서 순차적으로 증가한다. 종성번호는 종성이 없을 때는 0, 'ㄱ' = 1 순으로 증가한다. 아래는 위키피디아에서 발췌한 각 모음과 자음의 인덱스 번호이다.
이 규칙을 숙지하면 임의 음절과 초성과 중성이 같은 첫 번째 글자를 쉽게 구할 수 있다. 임의 음절의 문자 코드를 구한다 → 44032를 뺀다 → 28로 나누어 소숫점 아래는 버린다 → 다시 28을 곱한다 → 44032를 더한다의 과정만 거치면 되는 것이다. 마찬가지로 초/중성이 같은 마지막 글자도 구할 수 있는데 앞서 구한 코드에 27을 더하기만 하면 된다. 나누는 숫자를 28 대신 588로 바꾸고 더하는 숫자를 27 대신 587로 각각 조절한다면 초성이 같은 첫 번째 글자와 마지막 글자를 구할 수 있다. 이를 코드로 표현해보면, 임의의 음절을 ch라고 했을 때 이 글자에 해당하는 정규식 패턴은 다음과 같이 구한다.
const begin = Math.floor((ch.charCodeAt(0) - offset) / 28) * 28 + offset;
const end = begin + 27;
const pattern = `[\\u${begin.toString(16)}-\\u${end.toString(16)}]`;예를 들어 ch의 값이 '장'일 때 pattern의 값은 [\uc790-\uc7ab]가 된다. 여기서 더 나아가 ch의 값이 한글 자음인 경우에는 해당 자음은 물론 해당 자음이 초성인 모든 글자를 포함하도록 해보자. 이 지점에서 간단한 퀴즈를 하나 내보겠다. 문자 'ㄱ'의 코드는 12593이다. 그렇다면 문자 'ㅁ'의 코드는 무엇일까? 코딩이나 검색을 사용하지 말고 잠시 멈추어 생각해보자.
. . .
. . .
언뜻 생각하기에 위에 있는 표의 인덱스 번호 규칙에 따라 ㄱ과 ㅁ의 거리는 6이고 따라서 문자 'ㅁ'의 코드는 12593 + 6 = 12599라고 생각할 수 있다. 하지만 실상 12599에 해당하는 문자는 'ㄷ'이다. 이상하다. 'ㄱ'과 겨우 2 만큼 떨어져있어야 할 'ㄷ'이 왜 여기에 나타나는 걸까?
음절과 달리 유니코드의 한글 자음 파트에는 종성에만 사용할 수 있는 문자가 섞여 있다. 예를 들어, 음절 초성의 인덱스는 'ㄲ' 다음에 'ㄴ'이 나오지만 자음 파트에서는 'ㄳ'가 'ㄴ' 앞에 있다. 다음 표를 살펴보자.
다행히 그래도 'ㅅ'부터는 음절 초성의 인덱스와 순서가 일치한다. 어쩔 수 없이 'ㄱ'부터 'ㅃ'까지는 예외로 두고 'ㅅ'부터는 순서를 계산하면 된다. 각 초성에 해당하는 첫 음절, 즉 'ㄱ'이라면 '가', 'ㄴ'이라면 '나'를 구한 후, 마지막 문자까지 범위 계산을 하도록 한다. 당연히 초성 자체도 검색이 되어야 한다. 이를 코드로 구현하면 다음과 같다. ch에는 자음만 입력된다고 가정한다.
const con2syl = {
'ㄱ': '가'.charCodeAt(0),
'ㄲ': '까'.charCodeAt(0),
'ㄴ': '나'.charCodeAt(0),
'ㄷ': '다'.charCodeAt(0),
'ㄸ': '따'.charCodeAt(0),
'ㄹ': '라'.charCodeAt(0),
'ㅁ': '마'.charCodeAt(0),
'ㅂ': '바'.charCodeAt(0),
'ㅃ': '빠'.charCodeAt(0),
'ㅅ': '사'.charCodeAt(0),
};
const begin = con2syl[ch] || ( ( ch.charCodeAt(0) - 12613 /* 'ㅅ'의 코드 */ ) * 588 + con2syl['ㅅ'] );
const end = begin + 587;
const pattern = `[${ch}\\u${begin.toString(16)}-\\u${end.toString(16)}]`;예컨대 ch의 값이 'ㄹ'이라면 pattern의 값은 [ㄹ\ub77c-\ub9c7]이 된다. 자음 'ㄹ'은 물론이고 초성이 'ㄹ'인 모든 음절에 일치하는 패턴이다. 이제 이 두 코드를 합쳐서 하나의 함수로 만들어보자. 자음이 입력되도, 음절이 입력되도 일치하는 문자열을 찾을 수 있게 된다. 단, 종성까지 완성된 음절은 범위로 찾지 않고 해당 글자만 찾도록 한다.
function ch2pattern(ch) {
const offset = 44032; /* '가'의 코드 */
// 한국어 음절
if (/[가-힣]/.test(ch)) {
const chCode = ch.charCodeAt(0) - offset;
// 종성이 있으면 문자 그대로를 찾는다.
if (chCode % 28 > 0) {
return ch;
}
const begin = Math.floor(chCode / 28) * 28 + offset;
const end = begin + 27;
return `[\\u${begin.toString(16)}-\\u${end.toString(16)}]`;
}
// 한글 자음
if (/[ㄱ-ㅎ]/.test(ch)) {
const con2syl = {
'ㄱ': '가'.charCodeAt(0),
'ㄲ': '까'.charCodeAt(0),
'ㄴ': '나'.charCodeAt(0),
'ㄷ': '다'.charCodeAt(0),
'ㄸ': '따'.charCodeAt(0),
'ㄹ': '라'.charCodeAt(0),
'ㅁ': '마'.charCodeAt(0),
'ㅂ': '바'.charCodeAt(0),
'ㅃ': '빠'.charCodeAt(0),
'ㅅ': '사'.charCodeAt(0),
};
const begin = con2syl[ch] || ( ( ch.charCodeAt(0) - 12613 /* 'ㅅ'의 코드 */ ) * 588 + con2syl['ㅅ'] );
const end = begin + 587;
return `[${ch}\\u${begin.toString(16)}-\\u${end.toString(16)}]`;
}
// 그 외엔 그대로 내보냄
// escapeRegExp는 lodash에서 가져옴
return escapeRegExp(ch);
}
function createFuzzyMatcher(input) {
const pattern = input.split('').map(ch2pattern).join('.*?');
return new RegExp(pattern);
}
createFuzzyMatcher('ㅋㅁㅅ').test('크리스마스'); // true
createFuzzyMatcher('ㅋㅁㅅ').test('크리스'); // false
createFuzzyMatcher('고라').test('골라'); // true
createFuzzyMatcher('고라').test('가라'); // false
createFuzzyMatcher('군ㄱㅁ').test('군고구마'); // true
createFuzzyMatcher('군ㄱㅁ').test('궁고구마'); // false이렇게 완성한 정규표현식을 사용해서 우리나라의 도시 이름을 검색할 수 있는 간단한 애플리케이션을 데모용으로 작성해보았다.
데모에 사용된 데이터셋은 위키피디아 "대한민국의 인구순 도시 목록" 문서에서 발췌한 데이터를 JSON으로 작성했으며 다음과 같이 구성되어 있다.
[
{
"순위": 1,
"행정구역": "서울특별시",
"지역": "수도권",
"행정구분": "광역단체",
"인구": 9741383,
"남자": 4757643,
"여자": 4984230,
"성비": "95.5 : 100"
},
{
"순위": 2,
"행정구역": "부산광역시",
"지역": "영남권",
"행정구분": "광역단체",
"인구": 3416918,
"남자": 1680933,
"여자": 1735985,
"성비": "96.8 : 100"
},
...
]퍼지 검색 부분을 제외한 애플리케이션의 소스 코드는 다음과 같다.
function emptyResult(result) {
result.innerHTML = '<em class="no-result">검색 결과가 없습니다.</em>';
}
function setup() {
const input = document.getElementById("text");
const result = document.getElementById("result");
input.addEventListener(
"keyup",
() => {
if (!input.value) {
return emptyResult(result);
}
const regex = createFuzzyMatcher(input.value);
const resultData = cityNames
.filter((row) => {
return regex.test(row["행정구역"]);
})
.map((row) => {
return row["행정구역"];
});
result.innerHTML = resultData.join("\n");
},
false
);
}
setup();색상 강조
이 글 제일 앞에 나온 이미지를 다시 보자. 입력한 검색어와 일치하는 문자는 색상을 넣어 더 강조하고 있다. 이제 이 기능도 추가해보자. 글자 색상을 추가하려면 정규표현식에서 일치하는 문자를 캡쳐해야 한다. 간단하게 ch2pattern 함수에서 반환하는 패턴을 괄호로 감싸주자.
function createFuzzyMatcher(input) {
const pattern = input
.split('')
.map(ch2pattern)
.map(pattern => '(' + pattern + ')')
.join('.*?');
return new RegExp(pattern);
}패턴이 괄호로 감싸졌으므로 캡쳐가 가능하고 따라서 치환도 가능하다. 앞서 행정구역 이름만 텍스트로 반환하던 부분을 조금 변경해서 일치하는 문자를 <mark> 태그로 감싸주고 CSS를 추가해서 이 태그를 꾸며주자.
const resultData = cityNames
.filter((row) => {
return regex.test(row["행정구역"]);
})
.map((row) => {
return row["행정구역"].replace(regex, (match, ...groups) => {
const letters = groups.slice(0, val.length);
let lastIndex = 0;
let highlited = [];
for(let i=0,l=letters.length; i < l; i++) {
const idx = match.indexOf(letters[i], lastIndex);
highlighted.push(match.substring(lastIndex, idx));
highlighted.push(`<mark>${letters[i]}</mark>`);
lastIndex = idx + 1;
}
return highlited.join('');
});
});여기까지 작성하고 나면 입력한 패턴이 어떤 글자에 일치했는지 보여줄 수 있다.
이제 쓸만해진 것 같다. 그런데 만들고 보니 조금 욕심이 났다. 여기서 개선할 점은 더 없을까?
가중치
사실 퍼지 검색의 핵심은 이 가중치를 어떻게 처리하는가에 있다. 대충 검색해서 결과를 얻되 가장 관련성 높은 것을 먼저 보여주어야 한다. 이해를 돕기 위해 간단한 사례를 들어보자.
위 이미지는 검색어를 'ㅈㅅㄱ'으로 입력했을 때 결과 화면이다. 그런데 해당 검색어를 입력한 사람이 가장 보고 싶어한 결과는 무엇이었을까? 아마 이 사용자는 정선군이라는 결과를 보고 싶었을 확률이 크다. '제주특별자치도 서귀포시'라는 결과를 보자고 ㅈㅅㄱ이라고 입력할 확률은 아마 적지 않을까. 조금 더 관련성있는 결과를 먼저 배치하는 것이 중요하다는 말이다. 퍼지 검색 알고리듬은 이를 위해 두 문자열 간의 유사도를 측정할 방법을 제시한다.
이 글의 목적은 퍼지 문자열 검색을 정규식으로 간단하게 만드는 게 목표이므로 두 문자열 간의 유사도 측정을 위한 복잡한 알고리듬을 구현하지는 않겠다. 대신 '그럭저럭' 쓸만한 아주 간단한 방법을 하나 적용해보기로 하자. 목표는 위의 사례처럼 ㅈㅅㄱ을 입력했을 때 정선군이라는 결과를 먼저 보여주는 것이다. 적용할 수 있는 방법이 몇 가지 있겠지만 가장 손쉬운 방법으로는 "각 글자간 거리가 짧은 결과" 순으로 배열하는 방법이 있다.
앞 섹션에서 글자의 색상을 강조하기 위해 아래와 같이 일치하는 문자의 인덱스를 구했다.
const idx = match.indexOf(letters[i], lastIndex);여기서 이전 인덱스에서 다음 인덱스까지의 거리를 모두 더하면 글자간 거리의 총합이 나온다. 이 중 글자간 거리의 총합이 가장 작은 결과를 먼저 배치하도록 결과를 정렬하면 된다. 수정된 코드는 다음과 같다.
const resultData = cityNames
.filter((row) => {
return regex.test(row["행정구역"]);
})
.map((row) => {
let totalDistance = 0;
const city = row["행정구역"].replace(regex, (match, ...groups) => {
const letters = groups.slice(0, val.length);
let lastIndex = 0;
let highlighted = [];
for (let i = 0, l = letters.length; i < l; i++) {
const idx = match.indexOf(letters[i], lastIndex);
highlighted.push(match.substring(lastIndex, idx));
highlighted.push(`<mark>${letters[i]}</mark>`);
if (lastIndex > 0) {
totalDistance += idx - lastIndex;
}
lastIndex = idx + 1;
}
return highlighted.join("");
});
return { city, totalDistance };
});
resultData.sort((a, b) => {
return a.totalDistance - b.totalDistance;
});
result.innerHTML = resultData.map(({ city }) => city).join("\n");이 코드를 실행하여 같은 검색어를 입력하면 다음과 같이 결과가 달라져있는 것을 알 수 있다. 단순하게 글자간 거리만 계산한 결과이므로 간혹 의도와 맞지 않는 결과가 나타날 수는 있으나 적어도 아무런 정렬을 하지 않았을 때보다는 더 나은 결과를 보여주었다.
가중치 - 최대 거리순 정렬
이 섹션은 2021년 2월 16일에 추가되었습니다.
글을 공개하고 나서 실무에 적용해보신 Hika Maeng님이 전체 거리보다는 각 글자간 거리에서 가장 긴 걸 기준으로 정렬하는 편이 더 나은 결과를 보여주더라는 의견을 주셨다. 그래서 해당 내용까지 본문에 포함해보기로 했다.
위 코드에서 가중치를 설정하는 루프만 떼어놓고 보자.
let totalDistance = 0;
const city = row["행정구역"].replace(regex, (match, ...groups) => {
const letters = groups.slice(0, val.length);
let lastIndex = 0;
let highlighted = [];
for (let i = 0, l = letters.length; i < l; i++) {
const idx = match.indexOf(letters[i], lastIndex);
highlighted.push(match.substring(lastIndex, idx));
highlighted.push(`<mark>${letters[i]}</mark>`);
if (lastIndex > 0) {
totalDistance += idx - lastIndex;
}
lastIndex = idx + 1;
}
return highlighted.join("");
});
return { city, totalDistance };여기서 전체 길이를 구하는 대신 가장 긴 거리를 구하도록 수정한다. 위 코드에서 일치하는 글자 사이의 거리는 idx - lastIndex로 구하고 있는데, 이 값을 모두 더하는 대신 가장 큰 값만 남기도록 하면 된다. 또한 변수의 이름도 의미에 맞게 totalDistance가 아닌 longestDistance로 바꾸어 보자. 완성된 코드는 다음과 같을 것이다.
let longestDistance = 0;
const city = row["행정구역"].replace(regex, (match, ...groups) => {
const letters = groups.slice(0, val.length);
let lastIndex = 0;
let highlighted = [];
for (let i = 0, l = letters.length; i < l; i++) {
const idx = match.indexOf(letters[i], lastIndex);
highlighted.push(match.substring(lastIndex, idx));
highlighted.push(`<mark>${letters[i]}</mark>`);
if (lastIndex > 0) {
longestDistance = Math.max(longestDistance, idx - lastIndex);
}
lastIndex = idx + 1;
}
return highlighted.join("");
});
return { city, longestDistance };당연히 resultData의 정렬 또한 longestDistance를 기준으로 바뀌어야 한다. 완성된 코드는 다음에서 확인하고 실행해 볼 수 있다.
마치며
지금까지 자바스크립트와 정규표현식을 사용해 간단하게 퍼지 문자열 검색을 구현해보았다. 그리 효율적인 코드는 아니지만 클라이언트에서 크지 않은 데이터셋을 검색하기에는 충분할 것이라 생각한다.
너무 잘보았습니다.^^b 최고!!
와~ 멋있네요~!
결과도 멋있지만 점점 더 발전해 가는 부분이 더 멋있어요~
잘 보았습니다.
저도 비슷한 니즈가 있어서 라이브러리를 만들어보았는데요. 부끄럽지만 공유해봅니다.
https://bluewings.github.io/unobstructed-hangul-regular-expression/
정말 좋은 내용 감사합니다. 굉장히 유용하게 많이 사용할 수 있을 것 같네요!
[…] [JS] 한글도 지원하는 퍼지 문자열 검색 […]
안녕하세요. 포스팅 너무 재미있고 인상 깊게 읽었습니다.
혹시 실례가 되지 않는다면, 출처를 남기고 작성해주신 코드를 Swift로 포팅해서 gist에 기고해도 될까요?
자유롭게 사용하셔도 좋습니다. 많은 분들이 보실 수 있게 가능하다면 작성하신 코드를 여기에도 링크해주세요 ^^
먼저 좋은 코드 공유해주셔서 감사합니다~
현재 코드를 참고하여 공부해보는 중인데
여주시를 검색시 영주시와 같이 결과가 뜨는데 어떻게 수정할 수 있을까요 ?
본문의 코드는 초성 검색이 아니라 퍼지 검색이라 비슷한 글자도 찾아주는 걸 목표로 하고 있습니다. 그래서 "여주"를 검색했을 때 "영주"가 같이 결과에 잡히는 건 의도한 동작입니다. 초성 검색이면 오히려 본문에 있는 코드에서 몇 줄 빼기만 하면 되는 거라 더 간단합니다.
ch2pattern함수를 잘 살펴보시면 될 것 같습니다그렇군요 ~ 정말 좋은 코드를 공유해주셔서 감사드립니다~
리액트 사용하면서 퍼지검색 기능을 구현하는데 정말 많은 도움이 되었습니다
감사합니다~
안녕하세요~~ 정말 공부가 많이 되었습니다~ 실례가 되지 않는다면, 이 코드를 응용해보고 싶은데, 괜찮으신지요?~
댓글을 남겼는데...지워져 버린 것 같아서 다시 남깁니다~ ^^ 멋진 내용 감사합니다. 공부가 많이 되었는데요~ 실례가 되지 않는다면, 이 코드를 응용해 보고 싶은데, 사용해도 될런지요?~
당연히 사용하셔도 괜찮습니다. 가능하다면 이 글을 출처로 남겨주시면 좋겠지만 강제 사항은 아닙니다. 문의하시는 분들이 종종 있어서 다음에 코드 팁을 올릴 때는 사용 라이선스까지 명시해두어야겠네요. ^^;
만들고 있는 앱에 유용하게 사용했습니다! 멋진 코드 감사합니다!
짧은 코드인데 잘 사용하셨다니 기쁘네요. 🙂