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

n-Gram

n-gram에 대해 내가 쓴 글들

https://fullfish.tistory.com/109

n-Gram

https://fullfish.tistory.com/110

n-Gram 개선 및 고찰

위와 같은 고민을 거쳐서

최종적으로는 자음,모음단위로 쪼갠후 3-Gram을했다

그리고 여러 데이터를 넣어서 시뮬레이션 해본결과

0.27이상의 유사도만을 검색하기로 했다

 

또한 1-Gram이 1일 경우도 검색을 하게 했는데 1-Gram이 1인경우는 글자는 다 똑같은데

순서만 바뀐경우인 경우이다

'새우깡'과 '깡우새'인 경우

(그런데 현재는 자음 모음단위로 분해했기에 '새우깡'과 '꾸앗애'같은것도 검색이된다)

 

코드

// nGram.js
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;
};

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);
};

실행 예시

let a = "오늘 강남에서 맛있는 스파게티를 먹었다.";
let b = "강남에서 먹었던 오늘의 스파게티는 맛있었다.";
let a2 = "과자는 새우깡이지";
let b2 = "새우깡은 과자지";
let a3 = "과자중에 제일 맛있는건 새우깡";
let b3 = "제일 맛있는 과자는 무엇일까";
let a4 = "새우깡";
let b4 = "깡우새";
let a5 = "새우깡임";
let b5 = "새우깡은 과자다";
let a6 = "나는 새우깡을 먹고 있는데 너는 어떤 과자를 좋아하니?";
let b6 = "나는 새우깡은 안좋아하고 다른 과자가 좋아";
let a7 = "고구마깡은 맛있나?";
let b7 = "저녁 뭐먹지?";
console.log("___________________1");
console.log(this.diff_ngram(a, b, 1));
console.log(this.diff_ngram(a, b, 2));
console.log(this.diff_ngram(a, b, 3));
console.log("___________________2");
console.log(this.diff_ngram(a2, b2, 1));
console.log(this.diff_ngram(a2, b2, 2));
console.log(this.diff_ngram(a2, b2, 3));
console.log("___________________3");
console.log(this.diff_ngram(a3, b3, 1));
console.log(this.diff_ngram(a3, b3, 2));
console.log(this.diff_ngram(a3, b3, 3));
console.log("___________________4");
console.log(this.diff_ngram(a4, b4, 1));
console.log(this.diff_ngram(a4, b4, 2));
console.log(this.diff_ngram(a4, b4, 3));
console.log("___________________5");
console.log(this.diff_ngram(a5, b5, 1));
console.log(this.diff_ngram(a5, b5, 2));
console.log(this.diff_ngram(a5, b5, 3));
console.log("___________________6");
console.log(this.diff_ngram(a6, b6, 1));
console.log(this.diff_ngram(a6, b6, 2));
console.log(this.diff_ngram(a6, b6, 3));
console.log("___________________7");
console.log(this.diff_ngram(a7, b7, 1));
console.log(this.diff_ngram(a7, b7, 2));
console.log(this.diff_ngram(a7, b7, 3));

___________________1
0.8035714285714286
0.6779661016949152
0.5645161290322581
___________________2
0.8947368421052632
0.6190476190476191
0.391304347826087
___________________3
0.7073170731707317
0.4166666666666667
0.29411764705882354
___________________4
1
0.5
0.1111111111111111
___________________5
0.42105263157894735
0.3888888888888889
0.35294117647058826
___________________6
0.5942028985507246
0.4794520547945205
0.34177215189873417
___________________7
0.2857142857142857
0.030303030303030304
0

 

리벤슈타인 시간 복잡도, 공간 복잡도 개선

https://fullfish.tistory.com/108

레벤슈타인 거리 시간복잡도와 공간복잡도 개선