n-Gram 개선 및 고찰

자음 모음단위로 n-Gram

저번에 구현한 n-gram 

https://fullfish.tistory.com/109

n-Gram

에서는 글자를 음절 단위로 잘라서 썼었다

예를 들어 안녕하세요를

3-Gram으로 한다면 ['안녕하', '녕하세', '하세요']로 나눴는데

활용하기 나름이지만 이번에는 자음 모음단위로 나뉘어 봤다

['ㅇㅏㄴ', 'ㅏㄴㄴ', 'ㄴㄴㅕ' ...] 

해당 방법의 장점은 오타나 어미가 달라도 검색이 될 가능성이 높아지게끔 허들을 낮출 수 있다

 

우선은 문자열을 자음 모음으로 분해해야하므로

저번에 사용 했던 방법인

https://fullfish.tistory.com/99?category=1054038 

퍼지(fuzzy) 검색

를 참고해서

const chSplit = (ch) => {
  const rCho = [
    "ㄱ",
    "ㄲ",
    "ㄴ",
    "ㄷ",
    "ㄸ",
    "ㄹ",
    "ㅁ",
    "ㅂ",
    "ㅃ",
    "ㅅ",
    "ㅆ",
    "ㅇ",
    "ㅈ",
    "ㅉ",
    "ㅊ",
    "ㅋ",
    "ㅌ",
    "ㅍ",
    "ㅎ",
  ];
  const rJung = [
    "ㅏ",
    "ㅐ",
    "ㅑ",
    "ㅒ",
    "ㅓ",
    "ㅔ",
    "ㅕ",
    "ㅖ",
    "ㅗ",
    "ㅘ",
    "ㅙ",
    "ㅚ",
    "ㅛ",
    "ㅜ",
    "ㅝ",
    "ㅞ",
    "ㅟ",
    "ㅠ",
    "ㅡ",
    "ㅢ",
    "ㅣ",
  ];
  const rJong = [
    "",
    "ㄱ",
    "ㄲ",
    "ㄳ",
    "ㄴ",
    "ㄵ",
    "ㄶ",
    "ㄷ",
    "ㄹ",
    "ㄺ",
    "ㄻ",
    "ㄼ",
    "ㄽ",
    "ㄾ",
    "ㄿ",
    "ㅀ",
    "ㅁ",
    "ㅂ",
    "ㅄ",
    "ㅅ",
    "ㅆ",
    "ㅇ",
    "ㅈ",
    "ㅊ",
    "ㅋ",
    "ㅌ",
    "ㅍ",
    "ㅎ",
  ];
  let resultStr = "";
  for (let i = 0; i < ch.length; i++) {
    //만약 ch가 자음이 아닌 한글 문자일때만 이거 해당
    if (/[가-힣]/.test(ch[i])) {
      const nTmp = ch[i].charCodeAt(0) - 0xac00;
      const jong = nTmp % 28; // 종성
      const jung = ((nTmp - jong) / 28) % 21; // 중성
      const cho = ((nTmp - jong) / 28 - jung) / 21; // 초성

      resultStr += rCho[cho] + rJung[jung];
      if (rJong[jong] !== "") resultStr += rJong[jong];
    } else resultStr += ch[i];
  }
  return resultStr;
};

자음 모음으로 분해할 수 있다.

 

n-Gram 보완

저번 코드에서는 count++를 해줬다면 break로 for문 탈출하는것으로 보완이 다 됐다고 생각했는데

아직 보완할 점이 남아있었다

data와 search에서 일치하는 요소를 search에서 삭제해주지 않는다면 data에서는 같은 문자열을 가진 요소라면 계속 true가 나온다

예를들어

'가가가나'와 '가나'를 1-gram으로 비교해본다면 (자음 모음 분해전)

'가'가 일치해서 count++가 되는데 다음 '가'도 일치하게되고 다음 '가'도 일치한다

그래서 이 경우에 유사도가 2가 나온다

다른 예로 

diff_ngram("가나가나가나가나가나가나가나", "가나가마라라라라라라라라", 2) (자음 모음 분해전)의 결과가 1.18이 나오며 

두 문자열의 위치를 바꾸면 0.09가 나온다

처음에는 잘못생각해서 두 문자열의 길이를 비교해서 앞에가 길다면 문자열위치를 바꿔줬는데

이건 옳바르지 못한 방법이다

옳은 방법은

'가가가나'의 첫 문자인 '가'가 '가나'와 일치한다면

뒷 문자열에서 일치하는것을 삭제해주면된다 '가나' -> '나'로

그리고 결과를 보면 infinity가 나오는데 두번째 문자열의 길이가 0이됐기 때문이다

그러므로 원본 두번째 문자열의 길이를 따로 담아놨다가 사용하면 된다

 

최종 코드

const ngram = (str, num) => {
  let arr = [];
  const repeat = str.length - num + 1;
  for (let i = 0; i < repeat; i++) {
    const split = str.slice(i, i + num);
    arr.push(split);
  }
  return arr;
};

exports.diff_ngram = (data, search, num) => {
  if (search === undefined) return 0;
  data = chSplit(data);
  search = chSplit(search);
  let splitArrA = ngram(data, num);
  let splitArrB = ngram(search, num);
  const splitArrBLength = splitArrB.length;
  let count = 0;
  for (let i = 0; i < splitArrA.length; i++) {
    for (let j = 0; j < splitArrB.length; j++) {
      if (splitArrA[i] === splitArrB[j]) {
        count++;
        splitArrB.splice(j, 1);
        break;
      }
    }
  }
  return count / (splitArrA.length + splitArrBLength - count);
};

 

고찰

한 글자단위로 쪼개던것을 자음,모음단위로 쪼개서 허용도를 높여주었는데

현재 내가 하고있는 프로젝트에서는 문자열이 길지않아서 해당 방법이 좋다고 생각이든다

그러나 진짜 검색엔진과 같은 경우에는 이렇게 잘게 쪼개는것보다는

'안녕하세요 저는 배가 고픕니다' 와 같은 문장이 있다면

2-Gram일 경우

['안녕하세요 저는', '저는 배가', 배가 고픕니다']와 같이 띄어쓰기를 기준으로 쪼갠다면 더욱 더 활용도가 높아질것이다

예를들면 수많은 데이터를 학습시켜서

문장 자동완성 기능이나 오타 수정을 구현할 수 있을것이다.

 

n-gram 적용

17일차 / n-Gram구현 및 개선, 리벤슈타인 거리 시간,공간 복잡도 개선