퍼지(fuzzy) 검색 (정규표현식이용)

fuzzy logic : 불분명한 상태, 모호한 상태를 참 혹은 거짓의 이진 논리에서 벗어난 다치성으로 표현하는 논리개념 (위키백과)

 

확률론과 근본적으로 다른것이 부엌과 침실사이에 서 있을때 50%확률로 부엌에 있고 50%확률로 침실에있다고 말하는것과

양자역학처럼 50%는 부엌 50%는 침실에있다라고 말하는것은 다름

 

fuzzy 검색 : 완전히 일치하지않아도 검색하는것 (유사성 검색 알고리즘)

 

fuzzy 검색이란 유사해도 검색하는 방법론이므로 딱 정해진 방법이 존재하는것은 아니다

다양한 방법들이 있는데

 

• 레펜슈타인 거리(Levenshtein distance)
• 다메라우-레펜슈타인 거리(Damerau-Levenshtein)
• 우(Wu)와 만버(Manber)씨에 의한 비탭 알고리즘과 변형
• 철자 검사 기법
• N-그램 기법
• 시그니처 해싱 기법
• BK-트리

와 같은 방법이 있다 - 출처 : https://juggernaut.tistory.com/14

퍼지 문자열 검색(Fuzzy string search)

 

그러나 나는 저 정도로 정밀한 퍼지검색이 필요한만큼 데이터가 많지않기에 우선적으로 정규식을 통한 간단한 퍼지검색을 하고자한다

 

참고한 블로그 (사실 코드 복붙... 이해는 했음)

https://kipid.tistory.com/entry/%ED%95%9C%EA%B8%80-%EC%B4%88%EC%84%B1%EA%B2%80%EC%83%89-in-Javascript

한글 초성검색 in Javascript

https://taegon.kim/archives/9919

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

 

내가 쓴 정규식에대해 : https://fullfish.tistory.com/66?category=1054038 

정규표현식 (Regular Expression: Regex)

영어의 fuzzy

영어는 정규식을 이용한 fuzzy가 한글에 비해 쉽다

"hello"를 검색하기위해

"he", "hl" ,"ho", "hlo"를 검색한다고 가정한다면 검색하는 문자열의 사이마다 .*?를 넣어주면 될것이다

.*를 넣어도 되는데 .*?이 '0회 이상 연속으로 반복되는 문자와 가능한 적게 일치'이므로 검색속도가 더 빨라지지 않을까 싶다

hlo를 예로 들자면

const pattern = 'hlo'.split('').join('.*?');
const regex = new RegExp(pattern) //regex === /h.*?l.*?o/
regex.test('hello') //true

인데 문자열에 특수문자들이 입력될때를 대비하여

const _ = require("lodash");

const pattern = 'hlo'.split('').map(_.escapeRegExp).join('.*?');
const regex = new RegExp(pattern) //regex === /h.*?l.*?o/
regex.test('hello') //true

lodash를 install해준다음 escapeRegExp메소드를 써주는게 좋다

해당 메소드는 정규식에서 특수한 문자들 앞에 \\를 써서 문자열로 인식되게끔 해주는 메소드이다

 

한글의 fuzzy

한글역시 위의 코드와 똑같이 짜면 "안녕하세요"를 "안하"로 검색하면 "안녕하세요"를 찾을 수 있다

하지만 초성검색으로 검색을 하기위해서는 복잡해지는데 왜냐하면

한글은 영어와달리 1글자가 초성 + 중성 + (종성)의 조합으로 이루어져있기 때문이다

그러므로 해당 글자에서 초성, 중성, 종성을 분리해 내야 한다

한글 유니코드 값 === 0xAC00 + ((초성 * 21) + 중성) * 28 + 종성
// 0xAC00은 '가'의 유니코드번호이며 44032이다

위 코드를 보면 알 수 있듯이

기본적으로 주어진 글자에 0xAC00을 빼는것을 최우선적으로하고

28로 나눴을떄 나머지가 없으면 종성이 없는것이며 나머지가 있다면 몇이냐에따라 종성이 정해짐을 알 수 있다

마찬가지 방법으로

nTmp = ch.charCodeAt(0) = 0xAC00

jong=nTmp % 28; // 종성
jung=((nTmp - jong) / 28) % 21; // 중성
cho=(((nTmp - jong) / 28) - jung) / 21; // 초성

이렇게하면 각각의 초성 중성 종성의 순서(나눴을때 나머지값)를 알 수 있으며

순서는 아래와 같다

const choArr = ["ㄱ", "ㄲ", "ㄴ", "ㄷ", "ㄸ", "ㄹ", "ㅁ", "ㅂ", "ㅃ", "ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅉ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"];
const jungArr = ["ㅏ", "ㅐ", "ㅑ", "ㅒ", "ㅓ", "ㅔ", "ㅕ", "ㅖ", "ㅗ", "ㅘ", "ㅙ", "ㅚ", "ㅛ", "ㅜ", "ㅝ", "ㅞ", "ㅟ", "ㅠ", "ㅡ", "ㅢ", "ㅣ"];
const jongArr = ["", "ㄱ", "ㄲ", "ㄳ", "ㄴ", "ㄵ", "ㄶ", "ㄷ", "ㄹ", "ㄺ", "ㄻ", "ㄼ", "ㄽ", "ㄾ", "ㄿ", "ㅀ", "ㅁ", "ㅂ", "ㅄ", "ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"];

하지만 이 방법에는 문제가 있는데 초성, 중성, 종성의 순서만을 파악하는것이지 정확한 코드값을 가져오는것이 아니며

초성만 입력한다면 초성을 찾기위해 필요한 중성과 종성이 없어서 초성을 찾지못한다는것이다 즉, 초성검색이 안된다

그렇기에 좀더 세밀한 방법을 쓰자면

//input이 "반가워"일 때
function createFuzzyMatcher(input) {
  const pattern = input
    .split("")
    .map(chageUnicode) // .map((ele)=>ch2pattern(ele)) 와 같음
    .join(".*?");
  let data = new RegExp(pattern);
  //data === /반.*?[\uac00-\uac1b].*?[\uc6cc-\uc6e7]/

이런식으로 나오게 되는데

구문을 해석해보자면

.split("")으로 인해 ["반", "가", "워"] 가 되며

.join(".*?")를 통해 /반.*?가.*?워/ 가 된다

그리고 중간에 chageUnicode부분은

function chageUnicode(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 choArr = {
      ㄱ: "가".charCodeAt(0),
      ㄲ: "까".charCodeAt(0),
      ㄴ: "나".charCodeAt(0),
      ㄷ: "다".charCodeAt(0),
      ㄸ: "따".charCodeAt(0),
      ㄹ: "라".charCodeAt(0),
      ㅁ: "마".charCodeAt(0),
      ㅂ: "바".charCodeAt(0),
      ㅃ: "빠".charCodeAt(0),
      ㅅ: "사".charCodeAt(0),
    };
    const begin = choArr[ch] || (ch.charCodeAt(0) - 12613) /* 'ㅅ'의 코드 */ * 588 + choArr["ㅅ"];
    const end = begin + 587;
    return `[${ch}\\u${begin.toString(16)}-\\u${end.toString(16)}]`;
  }
  // 그 외엔 그대로 내보냄
  return _.escapeRegExp(ch); // 정규식에서 의미있는 와일드카드들을 문자열로 바꿔주는거
}

크게 3가지 경우로 나눈다

1. 초성 + 중성 + (종성) 까지있는 완성된 글자일 때

  1-1. 종성까지 있을때

    한글 유니코드값을 구하는 공식에서 알 수 있듯이 28로 나눠서 나머지가 없다면 종성이 있는것이므로

    받아온 문자 그대로를 return 한다

  1-2. 종성이 없을 때

    "반가워"를 검색할때 "바가"를 검색해도 검색이 되어야하므로 

    "바"만을 검색하는것이 아닌 "바" ~ "밯"까지 모든 종성을 염두에 둬야한다

    그러므로    

임의 음절의 문자코드 -> 44032 뺌 -> 28로 나누어 소숫점 아래는 버림 -> 28을 곱함 -> 44302를 더함
// 이러면 해당 음절의 처음을 구할 수 있다
// 마지막은 종성의 갯수가 28개 이므로(공란포함) 27을 더하면 마지막 글자를 구할 수 있다
// 예를들어 "박"의 처음과 끝은 "바"와 "밯"
// 하지만 위에서처럼 종성까지 있는 글자라면 굳이 처음과 끝을 구할 필요는 없다

return `[\\u${begin.toString(16)}-\\u${end.toString(16)}]` 
// 리턴값은 처음과 끝의 범위를 지정해주면된다
// \u는 유니코드 문자에 일치함을 보는것이다 ( /\u0061/은 a에 일치 )
// \\u로 \를 두개쓴이유는 첫 \는 뒤에 \가 의미가 있는것이 아닌 문자열로서 작성한다는 의미 (아직 정규식으로 변환안한 문자열임)

2. 자음일 때

임의 자음의 문자코드 -> 12613 뺌("ㅅ"의 코드) -> 588을 곱함 -> 49324를 더함 ("사"의 코드)
// 아까는 28나누고 28곱했는데 이번에는 곱하기만 하는 이유는 자음을 받았고 출력은 중성(+종성)까지있는 완성된 글자로 해야하기에
// "ㅅ"의코드를 빼고 "사"의 코드를 더하는 이유역시 자음만을 받고 완성된 글자를 반환해야하기 때문이며
// 또한 ㄱ~ㅅ까지는 인덱스상 "ㄱ", "ㄲ", "ㄴ", "ㄷ", "ㄸ", "ㄹ", "ㅁ", "ㅂ", "ㅃ", "ㅅ"순으로 증가하지만
// 유니코드 자음파트상에는 종성에만 사용할 수 있는 "ㄳ"값이 들어있으므로 예외처리를 해줘야함 ㅅ부터는 인덱스상과 순서 일치

3. 한글이 아닐 때

  그대로 리턴을하는데 lodash에서 지원하는 escapRegExp(https://www.geeksforgeeks.org/lodash-_-escaperegexp-method/)를 사용해서 리턴해준다

  해당 메소드는 특수한 의미가 있는 특수문자들을 문자열로서 인식되게끔 앞에 \\를 붙여주는 용도이다  

  문자열에서 \가 2개 붙어있아야지 즉 "\\?"이여야지 정규식 변환을 할때 /\?/가 되어서 ?가 문자열 취급을 받을 수 있다

 

기본적인 퍼지검색은 구현이 됐으며

검색시 해당 글자 하이라이트기능과 가중치검색을 그 다음에 해보고싶고

더 나가아가서 알고리즘을 사용한 더 효율적인 퍼지검색을 구현하고싶다

 

fuzzy 검색 적용

13일차 / fuzzy검색 구현