문서의 문장 단위 변경 추적

주말에 git의 diff 알고리즘에 학습을 하고 오늘은 코드 작성을 해보았다.

git의 diff 알고리즘은 공개되지 않아 레퍼런스가 거의 없다시피 한 상태다.

그래서 개념적인 부분만 적용 해서 코드를 작성해보았다.

무비위키 프로젝트에서 기존의 문서 비교 부분에 적용되어있던 diff 알고리즘과 다른점은

원본 문서와 수정된 문서의 비교를 글자 단위가 아니라 문장 단위로 끊어서 진행한다는 것이다.

 

문장 단위 변경 사항 추적 알고리즘

사용자가 특정 영화의 post를 등록하면 html 태그가 달린 문자열 형태로 db에 저장된다.

그래서 문자열을 문장 단위로 끊어서 비교를 해주기 위해 p태그를 이용하여 split해준다.

원본 문서와 수정된 문서를 각각 배열로 바꿔준 다음 인덱스를 이용해 비교한다.

추가된 문장과 삭제된 문장을 분류한 데이터를 저장해준다.

function diffArticleToSentence(originalArticle, modifiedArticle) {
  const originalSentences = originalArticle.split('</p>'); // originalArticle을 문장으로 분리
  const modifiedSentences = modifiedArticle.split('</p>'); // modifiedArticle을 문장으로 분리

  const diff = [];

  let i = 0;
  let j = 0;

  // 문장 단위로 비교
  while (i < originalSentences.length || j < modifiedSentences.length) {
    if (originalSentences[i] === modifiedSentences[j]) {
      // 문장이 동일한 경우
      i++;
      j++;
    } else {
      if (i < originalSentences.length) {
        // 삭제된 문장
        diff.push({ type: 'remove', value: originalSentences[i], idx: i });
        i++;
      }

      if (j < modifiedSentences.length) {
        // 추가된 문장
        diff.push({ type: 'add', value: modifiedSentences[j], idx: j });
        j++;
      }
    }
  }

  return diff;
};

 

 

변경 사항 추적 함수의 출력 값

아래와 같이 변경 사항들이 객체 배열 형태로 출력된다.

이 데이터를 가지고 원본 문서에 더해서 새로운 버전의 문서를 생성하면 되는 것이다.

[
  { type: 'remove', value: '<p>이 영화는 2023년 5월에 개봉했습니다.', idx: 0 },
  { type: 'add', value: '<p>이 영화는 2023년 5월에 18일 개봉했습니다.', idx: 0 },
  { type: 'remove', value: '<p>현재 누적 관객수는 850만명 입니다.', idx: 1 },
  { type: 'add', value: '<p>칸 영화제 경쟁 부문에 노미네이트되었습니다.', idx: 1 },
  { type: 'remove', value: '<p>강력추천합니다!', idx: 2 },
  {
    type: 'add',
    value: '<p>2023년 6월 12일 기준 누적 관객수는 900만명 입니다.',
    idx: 2
  },
  { type: 'remove', value: '', idx: 3 },
  { type: 'add', value: '<p>강력추천합니다!', idx: 3 },
  { type: 'add', value: '', idx: 4 }
]

 

 

그런데 변경 사항에 대한 데이터가 생각보다 많았다.

그래서 diff 알고리즘 학습 초기에 기록했던 최소 편집 거리 계산 알고리즘을 적용해보았다.

 

 

변경 사항 추적 함수에 최소 편집 거리 계산 적용

function diffArticleToSentence(originalArticle, modifiedArticle) {
  const originalSentences = originalArticle.split('</p>');
  const modifiedSentences = modifiedArticle.split('</p>');

  const diff = [];

  const m = originalSentences.length;
  const n = modifiedSentences.length;

  // 최소 편집 거리 계산을 위한 2차원 배열 초기화
  const dp = new Array(m + 1);
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1);
    dp[i][0] = i;
  }
  for (let j = 0; j <= n; j++) {
    dp[0][j] = j;
  }

  // 최소 편집 거리 계산
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (originalSentences[i - 1] === modifiedSentences[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1, // 삭제
          dp[i][j - 1] + 1, // 삽입
          dp[i - 1][j - 1] + 1 // 대체
        );
      }
    }
  }

  // 수정된 문장 정보 추출
  let i = m;
  let j = n;
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && originalSentences[i - 1] === modifiedSentences[j - 1]) {
      i--;
      j--;
    } else {
      if (j > 0 && (i === 0 || dp[i][j - 1] <= dp[i - 1][j])) {
        diff.push({ type: 'add', value: modifiedSentences[j - 1], idx: j - 1 });
        j--;
      } else if (i > 0 && (j === 0 || dp[i][j - 1] > dp[i - 1][j])) {
        diff.push({ type: 'remove', value: originalSentences[i - 1], idx: i - 1 });
        i--;
      }
    }
  }

  return diff.reverse(); // 역순으로 반환하여 원래 순서대로 출력
}

 

변경 사항 추적 함수에 최소 편집 거리 계산 적용 후 출력 값

최소 편집 거리 계산 알고리즘 적용 전과 후의 출력 값에 변화가 있었다.

변경 사항 데이터가 2개 줄어든 것이다.

이제 이 데이터를 원본 문서와 더해서 수정된 문서 출력만 잘 된다면

db에 저장 공간도 줄어들 것이고 연산에 필요한 시간도 줄어들 것이다. 

[
  { type: 'remove', value: '<p>이 영화는 2023년 5월에 개봉했습니다.', idx: 0 },
  { type: 'add', value: '<p>이 영화는 2023년 5월에 18일 개봉했습니다.', idx: 0 },
  { type: 'remove', value: '<p>현재 누적 관객수는 850만명 입니다.', idx: 1 },
  { type: 'add', value: '<p>칸 영화제 경쟁 부문에 노미네이트되었습니다.', idx: 1 },
  {
    type: 'add',
    value: '<p>2023년 6월 12일 기준 누적 관객수는 900만명 입니다.',
    idx: 2
  }
]

 

 

변경 사항 데이터와 원본 데이터를 더해 문서 출력

function generateModifiedArticle(originalArticle, diff) {
  let modifiedArticle = originalArticle;

  for (const change of diff) {
    if (change.type === 'remove') {
      // 삭제된 문장
      const sentenceToRemove = change.value;
      modifiedArticle = modifiedArticle.replace(sentenceToRemove, '');
    } else if (change.type === 'add') {
      // 추가된 문장
      const sentenceToAdd = change.value;
      const insertIndex = change.idx;
      modifiedArticle = insertSentence(modifiedArticle, sentenceToAdd, insertIndex);
    }
  }

  return modifiedArticle;
};

function insertSentence(article, sentence, index) {
  const sentences = article.split('</p>');
  const modifiedSentences = [
    ...sentences.slice(0, index),
    sentence + (sentences[index] ? '</p>' : ''),
    ...sentences.slice(index)
  ].filter(Boolean);
  if (modifiedSentences.length > 0) {
    modifiedSentences[modifiedSentences.length - 1] += '</p>';
  }
  return modifiedSentences.join('</p>');
}

 

 

원본과 수정본 입력 후 변경 사항 출력

const originalArticle = '<p>이 영화는 2023년 5월에 개봉했습니다.</p><p>현재 누적 관객수는 850만명 입니다.</p><p>강력추천합니다!</p>';
const modifiedArticle = '<p>이 영화는 2023년 5월에 18일 개봉했습니다.</p><p>칸 영화제 경쟁 부문에 노미네이트되었습니다.</p><p>2023년 6월 12일 기준 누적 관객수는 900만명 입니다.</p><p>강력추천합니다!</p>';

console.log(diffArticleToSentence(originalArticle, modifiedArticle));


// 출력 결과
[
  { type: 'remove', value: '<p>이 영화는 2023년 5월에 개봉했습니다.', idx: 0 },
  { type: 'add', value: '<p>이 영화는 2023년 5월에 18일 개봉했습니다.', idx: 0 },
  { type: 'remove', value: '<p>현재 누적 관객수는 850만명 입니다.', idx: 1 },
  { type: 'add', value: '<p>칸 영화제 경쟁 부문에 노미네이트되었습니다.', idx: 1 },
  {
    type: 'add',
    value: '<p>2023년 6월 12일 기준 누적 관객수는 900만명 입니다.',
    idx: 2
  }
]

 

 

원본과 변경 사항 데이터 입력 후 결과 출력

const originalArticle = '<p>이 영화는 2023년 5월에 개봉했습니다.</p><p>현재 누적 관객수는 850만명 입니다.</p><p>강력추천합니다!</p>';
const diff = [
  { type: 'remove', value: '<p>이 영화는 2023년 5월에 개봉했습니다.', idx: 0 },
  { type: 'add', value: '<p>이 영화는 2023년 5월에 18일 개봉했습니다.', idx: 0 },
  { type: 'remove', value: '<p>현재 누적 관객수는 850만명 입니다.', idx: 1 },
  { type: 'add', value: '<p>칸 영화제 경쟁 부문에 노미네이트되었습니다.', idx: 1 },
  {
    type: 'add',
    value: '<p>2023년 6월 12일 기준 누적 관객수는 900만명 입니다.',
    idx: 2
  }
]

console.log(generateModifiedArticle(originalArticle, diff));

// 출력 결과
<p>이 영화는 2023년 5월에 18일 개봉했습니다.</p>
<p>칸 영화제 경쟁 부문에 노미네이트되었습니다.</p>
<p>2023년 6월 12일 기준 누적 관객수는 900만명 입니다.</p>
<p>강력추천합니다!</p>

 

 

최소 편집 거리 계산 알고리즘과 최단 편집 스크립트 알고리즘은 다른 개념이었다.

최소 편집 거리 계산(Minimum Edit Distance)은 두 문자열 간의 차이를 측정하는 메트릭이고,

최단 편집 스크립트(Shortest Edit Script)는 그 차이를 실제로 수행하는 편집 연산의 순서와 내용을 나타낸다.

이번주 안에 위 내용들에 대해서 Deep Dive해봐야겠다.