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

이전 게시물

레벤슈타인 거리 (Levenshtein Distance)

기존 코드

//레벤슈타인 거리 코드
exports.levenshteinDistance = (str, search) => {
  if (search === undefined) return 0;
  if (str === search) return 0;
  let aLen = str.length;
  let bLen = search.length;
  if (aLen === 0) return bLen;
  if (bLen === 0) return aLen;
  //배열 생성
  let matrix = new Array(aLen + 1).fill(0).map(() => new Array(bLen + 1).fill(0));
  //첫 행과 열 초기화 0,1,2,3,4,5... 왜냐하면 공집합인경우와 비교하는거라서
  for (let i = 0; i < aLen + 1; i++) {
    matrix[i][0] = i;
  }
  for (let i = 0; i < bLen + 1; i++) {
    matrix[0][i] = i;
  }

  for (let i = 1; i < aLen + 1; i++) {
    let aCh = str[i - 1];
    for (j = 1; j < bLen + 1; j++) {
      let bCh = search[j - 1];
      console.log("문자열 : ", aCh, bCh, i, j);
      if (aCh === bCh) cost = 0;
      else cost = 1;
      matrix[i][j] = Math.min(
        matrix[i - 1][j] + 1, //문자 제거
        matrix[i][j - 1] + 1, //문자 삽입
        matrix[i - 1][j - 1] + cost //문자 변경
      );
    }
  }
  console.log(matrix);
  return matrix[aLen][bLen];
};

레벤슈타인 거리는
시간복잡도 : O(mn)

공간복잡도 : O(mn)이다

 

메모리적 측면과 속도 측면에서 성능 향상을 해보고자 한다

 

공간복잡도 줄이기

처음에 matrix를 m,n 크기로 생성하므로 공간 복잡도가 O(mn)인 상태로 유지되는데

코드를 잘 보면 각 단계별로 행렬에서 최종 두 행만 사용해서 값을 구한다

이미지 1

예를 들어 M13인 5를 구할때 필요한 요소들은 노란색으로 색칠된

12,13행과 L,M열만이 필요하므로 해당 계산때는 그 외의 데이터가 필요없으므로 삭제해 줘도 된다

 

---

메모리 용량에대한 참고 사항 ( 출처 :https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jukrang&logNo=40162487264)

// 1번 경우
let arr = []
arr [0] = 1
arr [99] =100

// 2번 경우
let arr = new arr(100)
arr [0] = 1
arr [99] =100
각 경우를
for(let i = 0 ; arr.length ; i++){
  console.log(arr[i])
}

해보면
두 경우 모두
0번째 1,
99번째 100
그리고 1~98번째는 undefined가 나오지만

메모리 용량은 1번경우는 arr[0]과 arr[99]만 차지하지만

2번의 경우는 arr[0] ~ arr[99]까지 100개의 공간을 차지한다

---

 

이미지 1의 경우에서 처럼 최종 2행과 열을 제외하고 메모리확보를 하려면 해당 공간에 null값을 주면 가비지콜렉터가 알아서 삭제해준다

(undefined는 삭제 안해줌)

참고

https://hanamon.kr/javascript-undefined-null-%EC%B0%A8%EC%9D%B4%EC%A0%90/

[JavaScript] undefined 타입 & null 타입 차이점 - 하나몬

 

그러므로 메모리 개선을 위해서는

맨 처음에 전체 배열을 만들어 놓는것이 아니라

배열을 1줄씩 만들면서 안쓰는 데이터는 null로 만들어주면된다

코드

exports.levenshteinDistance2 = (str, search, target) => {
  if (search === undefined) return 0;
  if (str === search) return 0;
  let aLen = str.length;
  let bLen = search.length;
  if (aLen === 0) return bLen;
  if (bLen === 0) return aLen;

  let matrix = [[0]];

  const createAndInsert = (countA, countB, target) => {
    // 탈출 조건
    if (
      (countA > str.length && countB > search.length) ||
      matrix[matrix.length - 1][matrix[0].length - 1] > target
    ) {
      return matrix[matrix.length - 1][matrix[0].length - 1];
    }
    // matrix 확장
    if (countA <= str.length) matrix.push([countA]);
    if (countB <= search.length) matrix[0][countB] = countB;

    // 값생성
    for (let i = 1; i < matrix.length; i++) {
      const aCh = str[i - 1];
      if (i !== matrix.length - 1) {
        const colLength = matrix[0].length - 1;
        const bCh = search[colLength - 1];
        aCh === bCh ? (cost = 0) : (cost = 1);
        matrix[i][colLength] = selectMin(matrix, i, colLength, cost);
      } else {
        for (let j = 1; j < matrix[0].length; j++) {
          const bCh = search[j - 1];
          aCh === bCh ? (cost = 0) : (cost = 1);
          matrix[i][j] = selectMin(matrix, i, j, cost);
        }
      }
    }
    if (matrix.length >= 3 || matrix[0].length >= 3) {
      for (let i = 0; i < matrix.length - 2; i++) {
        if (i !== matrix.length - 3) {
          matrix[i][matrix[0].length - 3] = null;
        } else {
          for (let j = 0; j < matrix[0].length - 2; j++) {
            matrix[i][j] = null;
          }
        }
      }
    }
    return createAndInsert(countA + 1, countB + 1, target);
  };
  const selectMin = (matrix, row, col, cost) => {
    return Math.min(
      matrix[row - 1][col] + 1, //문자 제거
      matrix[row][col - 1] + 1, //문자 삽입
      matrix[row - 1][col - 1] + cost //문자 변경
    );
  };
  return createAndInsert(1, 1, target);
};

해당 코드는 

맨 처음 행렬이 [[0]]에서 부터 시작

-> 재귀함수를 통해 다음 글자가 존재하여서 행이나 열을 늘릴 수 있다면 행렬의 크기를 확장

-> 빈칸을 문자 제거,삽입,변경 로직에 따라 채움

-> 빈칸 채운 행과 열기준에서 2칸 이전행과 2칸 이전열의 데이터를 null로 바꿔줌

 

세부적으로 보면 빈칸을 생성해줄때 다시 i = 1, j = 1인 처음부터 실행하면 필요없는 연산이 길어지므로

i !== matrix.length 일때 j는 matrix.length 이전까지 빈칸을 채워주고

i === matrix.length 일때는 for문으로 j를 증가시켜서 mtrix[0].length 이전까지 빈칸을 채워준다

예를들어

위 이미지와 같은 상황일때

E5를 구하기위해서는 E2, E3, E4, B5, C5, D5를 구한후에 E5를 구한다

그리고나서 C2, B3, C3에 null값을 넣어준다 (B2는 이전에 이미 null이 들어갔다)

 

시간복잡도 줄이기

원래 코드는 O(mn)의 시간복잡도를 가지고 있다

즉 매트릭스 넓이 만큼을 계산했다

하지만 레벤슈타인거리를 쓰는 이유는 대개 유사 문자열을 찾기 위함이며

두 문자열간의 특정 오차값 이하를 원한다

그러므로 계산이 이루어질 수록 오차는 유지 및 증가되므로

본인이 오차값 2이하를 원한다면 오차값이 3이상이 되는 순간은 이미 유사도가 떨어지는 문자열로 판명났으므로

더 이상의 쓸데없는 계산은 멈추고 return하면 시간복잡도를 줄일 수 있다

 

참고

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

 

리벤트슈타인 거리 적용

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