[js] 초성 자동완성 검색

개요

input박스에서 몇 글자 입력하기 시작하면 하단에 나오는 자동완성은 현재 웹에서 가장 흔한 UI입니다. 또한 개발자들에게는 IDE의 자동완성이나 관련 힌트처럼 익숙한 기능이기도 하죠.

이런 자동완성에서 초중종성의 한글은 그 특이한 구조를 갖고 있습니다. 바로 초성검색이란거죠. 강원도를 검색하기 위한 검색어가 ‘강’이나 ‘원’처럼 완전한 글자를 이루지 않아도 ‘ㄱㅇㄷ’ 같은 초성만으로도 매칭해주려는 것입니다.

한글은 유니코드구조에서 한글실러블이라는 영역에 속해있는데 이 코드는 일정한 계산 공식이 있어 초성만으로도 초성을 포함하는 다른 글자를 찾는 정규식을 구성할 수 있습니다. 이에 대해 제가 늘 스토킹하면서 좋아라하는 개발자이신 김태곤님이 다음의 포스팅에서 자세하게 원리를 정리해두셨습니다.

[JS] 한글도 지원하는 퍼지 문자열 검색

이 글에서는 자세하게 자동완성을 위한 기초 함수를 전부 제공해서 보여주고 있습니다.

글 자체가 원리 설명에 중점을 두고 작성된 것이라 입문자에게 지식을 공유하는 측면에서 굉장히 친절하고 공수가 많이 들어가있어 학습하기에 훌륭합니다.

이 글은 태곤님에게 직접 허락을 맡아 저 포스팅에 등장했던 코드를 실무에 사용할 수 있는 형태로 개조한 코드를 설명하는 글입니다.

따라서 원 글을 충분히 이해하신 뒤 읽으셔야하며 원 글과 중복된 내용은 다루지 않습니다. 주요 내용은 코드의 최적화와 실제 사용할 수 있는 코드 결과물이므로 그냥 소스코드만 가져다 쓰시기엔 좋을 수 있습니다. 또한 원 글에 등장하는 코드에 대한 설명도 생략합니다.

ch2pattern함수

이 함수 내부를 약간 정리할 필요가 있었습니다.

우선 코드를 살펴보면 매번 함수를 호출할 때마다 만들 필요가 없는 대상이 4개 있습니다.

function ch2pattern(ch) {
  const offset = 44032; // 1. 상수
  if (/[가-힣]/.test(ch)) { //2. 정규식1
    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)) { //3. 정규식2
    const con2syl = { //4. 확정참조맵
      'ㄱ': '가'.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)}]`;
  }
  return escapeRegExp(ch); //5. 함수 개조
}

위에 언급한 1~4번까지의 요소는 ch2pattern함수 내부에서 매번 만들어질 필요가 없는 부분으로 함수 밖에서 한 번만 선언해두면 됩니다. 그 외에 코드에서 if로 표현되어있는 부분은 각 if요소가 옵셔널하게 보이지만 가만히 살펴보면 3개의 케이스로 분리된 확정 케이스이므로 if, elseif, else 로 케이스가 확정된다는 것을 나타내는 편이 낫다고 보입니다. 이에 맞춰 마개조 하죠.

5번은 큰 문제는 없으나…있습니다. escapeRegExp함수가 로대쉬의존성을 만들어낸다는 것이죠. 그럼 실제 로대쉬의 저 함수 설명은..

https://github.com/lodash/lodash/blob/master/escapeRegExp.js

여기 코드를 보면 단순히 /[\\^$.*+?()[\]{}|]/g 정도의 정규식으로 replace해주는 것뿐이라는 것을 알 수 있습니다. 따라서 그냥 내부에 이 함수를 직접 정의하는 것으로 로대쉬 의존성을 제거하죠.

마지막으로 이 결과물을 나중에 캡쳐그룹전환을 위해 결과물에 ()괄호를 감싼 문자열로 바꿔줘야합니다. 아예 이를 내장합니다.

이상의 내용을 반영하면 다음과 같이 작성할 수 있습니다.

const reESC = /[\\^$.*+?()[\]{}|]/g;
const reChar = /[가-힣]/;
const reJa = /[ㄱ-ㅎ]/, offset = 44032;
const con2syl = Object.fromEntries('ㄱ:가,ㄲ:까,ㄴ:나,ㄷ:다,ㄸ:따,ㄹ:라,ㅁ:마,ㅂ:바,ㅃ:빠,ㅅ:사'.split(",").map(v=>{
	const entry = v.split(":");
	entry[1] = entry[1].charCodeAt(0);
	return entry;
}));

const pattern =ch=>{
	let r;
	if(reJa.test(ch)){
		const begin = con2syl[ch] || ((ch.charCodeAt(0) - 12613) * 588 + con2syl['ㅅ']);
		const end = begin + 587;
		r = `[${ch}\\u${begin.toString(16)}-\\u${end.toString(16)}]`;
	}else if(reChar.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;
		r = `[\\u${begin.toString(16)}-\\u${end.toString(16)}]`;
	}else r = ch.replace(reESC,'\\$&');
	return `(${r})`;
};

음. 일단 내부에 있던 정규식을 외부로 덜어내고 로대쉬 의존성을 제거하기 위해 추가적인 정규식을 하나 더 잡았습니다.
con2syl은 나열하지 않고 간단히 제네레이터를 구성했죠.
또한 if, else if, else 구조로 pattern함수가 무조건 이 세가지 케이스로 처리된다는 것을 보다 알기 쉽게 나타냈습니다.
마지막에 괄호를 처음부터 감싸 추가적인 작업을 제거합니다.

createFuzzyMatcher함수

아..이름이 너무 깁니다. 전 그냥 getReg정도로 줄였어요. 큰 건 없고 정리한거지만 실무적으로 영어의 경우 대소문을 가리지 않는 경우가 많아서 i를 추가했습니다.

(하지만 최종 소스에서는 map두번을 한번으로 줄이기 위해 pattern에서 괄호를 붙여주는 기능을 포함시키고 getReg자체가 함수가 아니라 코드로 병합될 것입니다)

const getReg=v=>new RegExp(v.split('').map(pattern).join('.*?'), "i");

최종 사용함수

map에서 태그를 입혀주던 함수를 살펴보기 전에 우선 최종적으로 제품에서 사용하게 될 함수를 먼저 생각해보죠.

const matchList = (search, arr, sTag = "", eTag = "", sort = sorter)=>{
	const reg = new RegExp(search.split('').map(pattern).join('.*?'), "i");
	const tagLen = sTag.length + eTag.length;
	return arr.reduce((acc, curr)=>{
		const matches = reg.exec(curr);
		if(matches) acc.push(matcher(curr, matches, sTag, eTag, tagLen));
		return acc;
	}, []).sort(sort);
};

matchList는

search: 검색어
arr: 대상이 되는 배열
sTag: 시작 태그
eTag: 끝 태그
sort: 소트용 함수

를 인자로 받고 있습니다.

함수 내부에서는 우선 getReg(원 글에서는 createFuzzyMatcher)를 대신해 직접 new RegExp를 만듭니다.
태그의 길이를 미리 계산한 뒤 reduce통해 받아온 데이터셋을 돌면서 matches를 계산하고
matcher를 이용해 배열원소를 구성합니다.
마지막으로 소팅하고 넘겨주는거죠. 최종 결과는 2차원 배열이 됩니다.

matcher

색깔도 표시하고 정렬 밑값을 주던 map의 인자용 함수가 있었죠. 저는 이걸 아예 matcher라는 함수로 정의했습니다. 근데 이 함수에서는 많은 변화가 있고 기능의 추가가 있습니다. 따라서 원 글의 map부분을 완전히 소화하신 후에 보시는걸 추천합니다. 또한 원 글에 보면 다음과 같은 코드가 등장합니다.

const letters = groups.slice(0, val.length);

근데 이 코드에서 val이라는 변수의 출처를 알 수가 없더라구요. 뭔가 코드의 일부일텐데.. 예상하건데 인자로 주어진 groups는 마지막에 카운트와 전체문자열을 포함하기 때문에 두 개를 잘라내야 하는데, 왜 val.length로 잘랐을까요. 걍 2개만 덜어내면 되는데..풀리지 않는 의문. 암튼 저는 완전히 다르게 reduce로 처리해버렸습니다. 또한 반환자체가 문자열이 아니라 배열입니다.

[변환된 문자열, 최소거리, 문자열길이, 최초로 등장한 위치]

위 형태를 반환하는 함수를 반환하는 함수입니다. 당연히 정렬할 때 써먹기 위해서입니다. 또한 matcher를 호출할 때 감쌀 태그와 속성도 보낼 수 있게 했습니다.

const matcher =(v, matches, sTag, eTag, tagLen)=>{
	let distance = Number.MAX_VALUE; //1-1. 최소거리 측정을 위해 최대값을 할당
	let vLast = 0; //1-2. 원본 문자열 기준 마지막 위치
	let vPrev = 0; //1-3. 원본 문자열 기준 직전 매칭 위치
	let last = 0; //2-1. 변형 문자열 기준 마지막 위치
	let first = -1; //3-1. 최초 등장 위치 
	let acc = v; //최종 문자열
	for(let i = 1, j = matches.length; i < j; i++){
		const curr = matches[i];
		vLast = v.indexOf(curr, vLast); //1-4. 원본 문자열 기준 현재 문자 일치 위치
		if(vLast && distance > vLast - vPrev) distance = vLast - vPrev; //1-5. 새 거리가 더 짧다면 갱신
		vPrev = vLast; //1-6. 이전 위치 갱신
		last = acc.indexOf(curr, last); //2-2. 변형 문자열 기준 현재 문자열 일치 위치
		acc = `${acc.substring(0, last)}${sTag}${curr}${eTag}${acc.substr(last + 1)}`; //최종 문자열 갱신
		last += tagLen; //2-5. 태그를 포함한 다음 인덱스 시작 위치
		if(first == -1) first = vLast; //3-2. 최초위치 갱신
	}
	return [acc, distance, v.length, first]; //[문자열, 최소길이, 원본길이, 최초위치]
};

코드설명은 주석으로 자세히 했습니다.

1- 로 시작하는 흐름은 최소거리를 얻기 위한 로직과 변수입니다.

2-로 시작하는 흐름은 문자열에 태그를 꾸며주는 부분이죠.

3-는 최초 위치를 계산하는 흐름입니다.

소팅함수

이미 matcher를 통해 map을 돌리면 각 엘리먼트가 원소 세개를 가진 배열로 변환되어 2차원 배열 상태가 됩니다. 이 2차원배열을 소팅하는 것으로 소팅전략은 다음과 같습니다.

우선 검색문자간 거리가 최소인 것으로 정렬. 즉 ㄱㅇㄷ검색한 경우 ‘강ㅇㅇㅇ원도’가 ‘강ㅇ원ㅇ도’ 보다 우선함. 왜냐면 앞에 문자열은 ‘원도’의 거리가 1이지만 뒤에 문자열은 ‘강ㅇ원’, ‘원ㅇ도’ 가 둘다 2의 거리를 갖고 있기 때문임
최소 거리로 동률이라면 누가 더 먼저 등장했냐를 우선시 함. 즉 ’11강원도’와 ‘1강원도1’이 있다면 ‘1강원도1’쪽의 강이 더 먼저 등장했기 때문에 우선됨.
2번도 동률을 이룬다면 문자열 길이가 짧은 것을 우선시 함. 즉 ‘강원도’와 ‘강원도 XXX’가 있다면 둘다 최소거리는 1로 동일하지만 ‘강원도’ 문자열의 길이가 짧기 때문에 선택됨.

이상의 전략과 앞서 matcher를 통한 map의 결과가 [문자열, 최소거리, 길이] 형태의 2차원 배열인걸 고려하면 다음과 같이 작성할 수 있습니다.

const sorter = ([, dA, lA, fA], [, dB, lB, fB])=>{ //d-거리, l-길이, f-최초위치
  if(dA > dB) return 1; //최소거리부터 평가
  else if(dA < dB) return -1;
  else{
    if(fA > fB) return 1; //최초위치 평가
    else if(fA < fB) return -1;
    else{
      if(lA > lB) return 1; //마지막으로 길이평가
      else if(lA < lB) return -1;
      else return 0;
    }
  }
};

결론

태곤님 덕분에 기존의 자동완성 정렬기를 재작성하면서 초성검색을 안정적으로 지원하게 되어 기쁩니다.

설명에 나왔던 내용을 좀 정리하여 완성된 코드와 사용예는 다음과 같습니다.

const matchList = (_=>{
	const reESC = /[\\^$.*+?()[\]{}|]/g, reChar = /[가-힣]/, reJa = /[ㄱ-ㅎ]/, offset = 44032;
	const con2syl = Object.fromEntries('ㄱ:가,ㄲ:까,ㄴ:나,ㄷ:다,ㄸ:따,ㄹ:라,ㅁ:마,ㅂ:바,ㅃ:빠,ㅅ:사'.split(",").map(v=>{
		const entry = v.split(":");
		entry[1] = entry[1].charCodeAt(0);
		return entry;
	}));
	const pattern =ch=>{
		let r;
		if(reJa.test(ch)){
			const begin = con2syl[ch] || ((ch.charCodeAt(0) - 12613) * 588 + con2syl['ㅅ']);
			const end = begin + 587;
			r = `[${ch}\\u${begin.toString(16)}-\\u${end.toString(16)}]`;
		}else if(reChar.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;
			r = `[\\u${begin.toString(16)}-\\u${end.toString(16)}]`;
		}else r = ch.replace(reESC,'\\$&');
		return `(${r})`;
	};
	const matcher =(v, matches, sTag, eTag, tagLen)=>{
		let distance = Number.MAX_VALUE, first = -1, last = 0, vLast = 0, vPrev = 0, acc = v;
		for(let i = 1, j = matches.length; i < j; i++){
			const curr = matches[i];
			vLast = v.indexOf(curr, vLast);
			if(first == -1) first = vLast;
			if(vLast && distance > vLast - vPrev) distance = vLast - vPrev;
			vPrev = vLast;
			last = acc.indexOf(curr, last);
			acc = `${acc.substring(0, last)}${sTag}${curr}${eTag}${acc.substr(last + 1)}`;
			last += tagLen;
		}
		return [acc, distance, v.length, first];
	};
	const sorter = ([, dA, lA, fA], [, dB, lB, fB])=>{
		if(dA > dB) return 1;
		else if(dA < dB) return -1;
		else{
			if(fA > fB) return 1;
			else if(fA < fB) return -1;
			else{
				if(lA > lB) return 1;
				else if(lA < lB) return -1;
				else return 0;
			}
		}
	};
	return (search, arr, sTag = "", eTag = "", sort = sorter)=>{
		const reg = new RegExp(search.split('').map(pattern).join('.*?'), "i");
		const tagLen = sTag.length + eTag.length;
		return arr.reduce((acc, curr)=>{
			const matches = reg.exec(curr);
			if(matches) acc.push(matcher(curr, matches, sTag, eTag, tagLen));
			return acc;
		}, []).sort(sort);
	};
})();

const arr = [
	"hika",
	"ㄴㄷ러홍ㅏㄴㅂㅓㅂ길ㅂㅏㄴㅂㅏㄴㅂㅓ동",
	"홍ㄴㄷㅂㅓㅂ길ㅂㅏㄴㅂㅓ동",
	"홍ㄴㄷㅓㅂ기ㅂㅓ동",
	"홍기동aaaaaa",
	"1홍길도",
	"홍길다1",
	"홍기동"
];
document.querySelector("#test").innerHTML = matchList("ㅎㄱㄷ", arr, '<span style="color:red">', '</span>').map(([v])=>`<li>${v}</li>`).join("");

위 실행결과는 다음과 같습니다.

[js] 초성 자동완성 검색

개요

ch2pattern함수

createFuzzyMatcher함수

최종 사용함수

matcher

소팅함수

결론

2 Responses

답글 남기기 응답 취소

[초보자들] S70 스터디 다섯번째 후기

[java] 인텔리제이 무료 버전으로 스프링5 MVC개발하기(Maven)

[책] 웹 개발자를 위한 대규모 서비스를 지탱하는 기술

[2018 상반기 워크숍 후기] Bsidesoft in Okinawa – 2

카테고리

recent comment