n-Gram

n-Gram이란 문장의 유사도를 비교하는 방법중 하나로 문장을 쪼개서 비교한다

 

예를 들어

3-gram으로

'과자중에 제일 맛있는건 새우깡'

'제일 맛있는 과자는 무엇일까'

이 두문장을 비교한다면

각 문장을 3글자씩 자른다.

"과자중에 제일 맛있는건 새우깡"
[
  '과자중', '자중에',
  '중에 ',  '에 제',
  ' 제일',  '제일 ',
  '일 맛',  ' 맛있',
  '맛있는', '있는건',
  '는건 ',  '건 새',
  ' 새우',  '새우깡'
]

"제일 맛있는 과자는 무엇일까"
[
  '제일 ',  '일 맛',
  ' 맛있',  '맛있는',
  '있는 ',  '는 과',
  ' 과자',  '과자는',
  '자는 ',  '는 무',
  ' 무엇',  '무엇일',
  '엇일까'
]

그리고 각 요소를 비교해서 유사도를 측정한다

 

https://too-march.tistory.com/20

[5] 문장의 유사도 분석하기 - 레벤슈타인 거리, N-gram

해당 블로그를 참고했는데 해당 블로그 코드에는 2가지 큰 문제가 있다

해당 블로그의 설명을 토대로 코드를 짜보면

exports.diff_ngram = (data, search, num) => {
  if (search === undefined) return 0;
  let splitArrA = ngram(data, num);
  let splitArrB = ngram(search, num);
  arr = [];
  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++;
        arr.push(splitArrA[i]);
      }
    }
  }
  return count / splitArrA.length;
};

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

이러한데

1번문제점

이중 for문에 break가 없어서 

첫 문장 요소와 일치 하는 값을 두번째 문장 요소에서 찾고 count++를 했을때 for문을 탈출하지 않아서

count가 또 오를 수 있다

즉, 1번문장과 2번문장의 길이보다도 count가 더 커질 수 있으므로 (유사도가 100%이상이 나올 수 있으므로)

for문안 if문에 break를 넣어줘야한다

 

2번문제점

마지막 리턴을 count / splitArrA.length로 줬는데

이러면 data값과 search값의 위치가 바꼈을때 즉, 두 문장의 위치를 바꿨을때 결과가 다르게 나온다

data값이 짧을 경우

data가 '새우깡'이고 search가 '새우깡은 과자다'인 경우

새우깡이 들어가기만 한다면 search가 아무리 길어도 유사도가 최고치인 1이 나온다

그러면 검색을 길게하면 할수록 많은 데이터들이 검색되는, 검색의 문장 성분들이 모두 or검색이 된다

data값이 길 경우

data가 '새우깡은 과자다'이고 search가 '새우깡'이라면 data 길이가 길어질 수록 유사도가 떨어지며

search가 '새우깡'이든 '새우깡임'이든 '새우깡ㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇ'이든 일치하지 않은 문자열이 아무리 길어도 같은 유사도가 나온다

그래서 return해주는 값을

 

자카드 지수(Jaccard index)를 이용했다

해당 공식을 이용하면 최대 유사도 1, 최저 유사도 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;
  let splitArrA = ngram(data, num);
  let splitArrB = ngram(search, num);
  arr = [];
  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++;
        arr.push(splitArrA[i]);
        break;
      }
    }
  }
  return count / (splitArrA.length + splitArrB.length - count);
};

 

응용할 수 있는 방법으로

1-Gram을 하면 글자의 순서만 뒤엉켰을 경우

'안녕하세요'와 '하녕요세안'과 같은경우 정확도 1이 나와서 검색가능하게 만들 수 있다

 

n-Gram 개선 

n-Gram 개선 및 고찰

 

n-gram 적용

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