[최종 프로젝트] Puppeteer 크롤링하기2<문자열 유사성 알고리즘>

진행 상황

저번에는 크롤링의 모든 뉴스를 가져오는것을 진행했다.

 

하지만 이번 프로젝트에서 해결해야하는 부분은 가져온 게시글들 중에서 중복된것들을 최대한 정리를 해야했다.

1  "강동구 살인예고 10대 남성, 구속영장 기각"
2  "여고 칼부림 협박글 10대 男 구속영장 기각…“사유 불충분”"
3  '"여고서 칼부림 한다" 글 작성한 10대 남학생 구속영장 기각'
4  "'여중·여고 칼부림 예고' 글 작성한 10대 구속영장 '기각'"
5  "여고 칼부림 협박글 10대 구속영장 기각…'사유 불충분'"
6  "'강동구 여중·여고 칼부림 예고' 10대 구속영장 기각"
7  "'코인 싸게 판매'로 유인…돈 받고 폭행·도주한 간 큰 20대 10명 검거"

위 7개는 1번째부터 7번째의 뉴스의 타이틀이다.

뉴스는 한 미디어에서만 게시하는것이 아니고 여러 미디어에서 같은 주제로 게시를 하기 때문에 비슷한 내용의 게시물이 올라 올수 밖에 없다.

 

우리는 이런 부분을 최대한 중복이 되지 않도록 해야 한다.

일단 제목을 기준으로 나누기로 정했다.

제목은 보통 그 뉴스에 대한 함축적인 내용이 들어간 것이라 가정을 하고 타이틀을 기준으로 뉴스를 필터링한다.

 

진행을 해보려 했던 방법

1. 타이틀을 띄어쓰기를 기준으로 배열형태로 만든다.

2. 띄어 쓰기로 서로 같은지 비교를 한 뒤 같은 단어가 3개 이상 있으면 동일한 뉴스라고 판단.

3. 동일한 뉴스이면 가장 최근 뉴스 하나만 게시.

이런식의 순서로 진행을 하려고 했다.

하지만 이렇게 하면 문제가 되는것이 있다.

[강동구, 살인예고, 10대, 남성,, 구속영장, 기각"]
["여고, 칼부림, 협박글, 10대, 男, 구속영장, 기각…“사유, 불충분”",]

단지 1번과 2번뉴스 타이틀을 비교함에 있어서도

강동구를 비교 한다면 8개의 배열화된 단어들을 다 비교해야 했다.

만약에 같은 단어가 있다고 할 때 break로 탈출 한다고 해도

없는 단어라면? 단어가 제일 끝에 있다면? 계속해서 비교를 해야했다.

아직 빅오 표기법에대해서 잘 알진 못하지만 적어도 이방법이 시간도 오래 걸리면서 메모리도 많이 잡아 먹을것이라는건 

알고리즘 문제를 풀면서 자연스레 알게 되었다.

그래서 방법을 찾아보았다.

---

 

문자열 유사도 알고리즘

두 문자가 얼마나 비슷한지 측정하는 알고리즘.

문자열 유사성 알고리즘은 거리값을 출력하는데 

만약 출력한 거리값이 0이라면 전혀 다른 문자열이라는것을 의미, 1이라면 완전히 같은 문자열이라는 것을 의미 한다.

텍스트 분석, 검색 엔진, 정보 검색, 자연어 처리 등 다양한 분야에서 활용된다.

 

문자열 유사성 알고리즘 종류

Levenshtein Distance - 레벤슈타인 거리

두 문자열 사이의 최소 편집 거리를 계산하여 문자열의 유사도를 측정.

삽입, 삭제, 대체 등의 연산으로 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 연산 횟수를 계산한다.

  |   | s | i | t | t | i | n | g |
--+---+---+---+---+---+---+---+---+
  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
k | 1 |   |   |   |   |   |   |   |
i | 2 |   |   |   |   |   |   |   |
t | 3 |   |   |   |   |   |   |   |
t | 4 |   |   |   |   |   |   |   |
e | 5 |   |   |   |   |   |   |   |
n | 6 |   |   |   |   |   |   |   |

kitten과 sitting을 비교 하면

각 문자열을 행과 열로 나타냄.

행렬의 크기는 (m+1) × (n+1)이다. => (7+1) × (6+1) = 56

m - 첫번째 문자열의 길이, n - 두번째 문자열의 길이, +1은 인덱스 0을 벗어나기 위함.

각 셀을 채워 넣을대 사용되는 연산에 따라 적절한 값을 할당.

• 삽입 (Insertion): 왼쪽 셀 값에 1을 더한다.

• 삭제 (Deletion): 위쪽 셀 값에 1을 더한다. 

• 대체 (Substitution): 대각선 위쪽 셀 값에 1을 더한다. 이 경우, 비교하는 두 문자가 다른 경우에만 대체가 이루어짐.

오른쪽 하단의 셀에 도달하면 그 값이 두 문자열 간의 Levenshtein Distance

적으면 적을수록 두 문자열이 유사한것.

    |   | s | i | t | t | i | n | g |
----+---+---+---+---+---+---+---+---+
    | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
k   | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
i   | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
t   | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
t   | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
e   | 5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
n   | 6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |

 

 

Jaccard Similarity - 자카드 유사도

두 집합 간의 유사도를 측정하는 방법 중 하나.

두 집합의 교집합을 두 집합의 합집합으로 나눈 값.

이를 통해 두 문자열의 유사성을 측정한다.

 

 

Cosine Similarity - 코사인 유사도

두 벡터 간의 각도를 사용하여 유사도를 측정.

텍스트 문서나 문장을 벡터로 표현한 후, 벡터 간의 각도를 계산하여 유사도를 측정한다.

 

 

Hamming Distance - 해밍 거리

같은 길이의 두 문자열 간의 다른 문자의 개수를 측정하여 유사도를 평가 한다.

coriny
corory
   ^^

위와 같이 문자열의 낱말끼리 비교하여 같은 위치의 낱말이 같은지를 비교한다.

여기에서 Hamming Distance는 2이며 서로 다른 문자열의 수를 나타낸다.

또한 Hamming Distance는 0일때 완전히 같은 단어이다.

 

 

N-Gram

문자열을 n개의 연속된 문자 또는 단어로 분할아혀, 두 문자열 간에 공통된 n-gram의 개수를 계산하여 유사도를 측정.

문자열이 유사할수록 공통된 n-gram의 개수가 많아진다.

원본 문자열: "Hello, world!"

2-gram (bigram) 추출:
["He", "el", "ll", "lo", "o,", ", ", " w", "wo", "or", "rl", "ld", "d!"]

문자열을 2개씩 나누어 n-gram 배열을 만든다음

상대 문자열의 n-gram 배열과 같은 위치에 있는지 비교하며 틀리면 패널티 줌.

 

 

Jaro-Winkler Distance 

Levenshtein Distance같이 편집 거리의 개념을 사용하지만 

같은 낱말이 문자열 내 특정한 거리 내에 있는 경우와

문자열의 시작점부터 a와 b의 문자열이 일치하기 시작하는 경우 에 더욱 높은 관련도 점수를 할당함.

출처:&nbsp; h-go-getter블로그

위에 나와 있는 식대로 계산을 해보면

coriny
corair

|s1|, |s2| = 비교하는 두 문자열의 길이 : 6,6

m = 일치하는 문자수 : 4 ( c,o,r,i )

t = 일치하지만 순서가 다른 문자수 : 1/2 ( i )

1/3 * ( 4/6 + 4/6 + 4 - 1/2 / 4 ) = 0.73

1에 근접하므로 유사하다고 볼수가 있다.

 

 

Jaro-Winkler similarity

Jaro similarity와 비슷하지만 두 문자열의 시작 부분에 있는 문자가 동일한 경우 높은 점수를 할당.

문자열에 정의된 최대 길이 L까지 공통으로 시작할 때 더 정확한 답을 제공하는 Scaling Factor 'P'를 사용

출처:&nbsp; h-go-getter블로그

coriny
corair

Sj = jaro 유사도 : 0.73

L = 두 분자열의 시작 부분에서 동일한 문자 수 (최대 4) : 3

P = 고정된 scaling factor ( 0.1 )

0.73 + 3 * 0.1 * ( 1 - 0.73 ) = 0.81

두 문자열이 더욱이 유사하단걸 알수가 있다.

 

 

문자열 유사도 알고리즘 적용 시키기

Levenshtein Distance - 레벤슈타인 거리 적용 - Node.js

function areSimilarStrings(str1, str2, threshold) {
  const words1 = str1.split(/\s+/);
  const words2 = str2.split(/\s+/);

  let similarWordCount = 0;

  for (const word1 of words1) {
    for (const word2 of words2) {
      if (calculateLevenshteinDistance(word1, word2) <= threshold) {
        similarWordCount++;
        break;
      }
    }
  }

  return similarWordCount >= 3;
}

function calculateLevenshteinDistance(a, b) {
  const matrix = [];

  for (let i = 0; i <= b.length; i++) {
    matrix[i] = [i];
  }

  for (let j = 0; j <= a.length; j++) {
    matrix[0][j] = j;
  }

  for (let i = 1; i <= b.length; i++) {
    for (let j = 1; j <= a.length; j++) {
      if (b.charAt(i - 1) == a.charAt(j - 1)) {
        matrix[i][j] = matrix[i - 1][j - 1];
      } else {
        matrix[i][j] = Math.min(
          matrix[i - 1][j - 1] + 1, // 대체
          matrix[i][j - 1] + 1, // 삽입
          matrix[i - 1][j] + 1 // 삭제
        );
      }
    }
  }

  return matrix[b.length][a.length];
}

const str1 = "여고 칼부림 협박글 10대 男 구속영장 기각…“사유 불충분”";
const str2 = "강동구 살인예고 10대 남성, 구속영장 기각";

const threshold = 1; // 허용되는 최대 편집 거리

if (areSimilarStrings(str1, str2, threshold)) {
  console.log("두 문자열은 유사한 내용을 가지고 있습니다.");
} else {
  console.log("두 문자열은 다른 내용을 가지고 있습니다.");
}

Levenshtein Distance가 3이상이면 같은 문자라고 가정한뒤 테스트를 해보았다.

"강동구 살인예고 10대 남성, 구속영장 기각"
"여고 칼부림 협박글 10대 男 구속영장 기각…“사유 불충분”" - x 
""여고서 칼부림 한다" 글 작성한 10대 남학생 구속영장 기각" - o 
"'여중·여고 칼부림 예고' 글 작성한 10대 구속영장 '기각'" - x 
"여고 칼부림 협박글 10대 구속영장 기각…"사유 불충분"" - x 
"'강동구 여중·여고 칼부림 예고' 10대 구속영장 기각" - o

모두 같은 내용의 제목임에도 불구하고 첫번째 타이틀과 비교 했을때 유사한 내용을 가졌다고 판단하는것이 2개밖에 없었다.

이렇게 되면 생기는 문제가 가공을 한다고 할 때

중복이라고 나와 있던 게시글을 지운다고 하면

중복이 아니라고 판단한 게시글은 같은 내용의 뉴스도 서로 다른 내용을 가졌다고 판단하여 그대로 저장하게 된다.

그렇게 되면 첫번 째 게시글, 두번 째, 네번 째, 다섯번 째 총 4개의 게시글이 나오게 된다.

일단 중복은 최대한 제외 시키는게 목적이다.

 

 

Jaro-Winkler similarity 적용 - Node.js

import jarowinkler_similarity from "jaro-winkler";

const str1 = "강동구 살인예고 10대 남성 구속영장 기각";
const str2 = "여고 칼부림 협박글 10대 男 구속영장 기각…“사유 불충분”";
const str3 = '"여고서 칼부림 한다" 글 작성한 10대 남학생 구속영장 기각';
const str4 = "'여중·여고 칼부림 예고' 글 작성한 10대 구속영장 '기각'";
const str5 = '여고 칼부림 협박글 10대 구속영장 기각…"사유 불충분"';
const str6 = "'강동구 여중·여고 칼부림 예고' 10대 구속영장 기각";
const str7 = '"코인 싸게 판매"로 유인…돈 받고 폭행·도주한 간 큰 20대 10명 검거';

const newArr = [str1, str2, str3, str4, str5, str6, str7, str8];
let copyArr = [...newArr];

    let score = jarowinkler_similarity(copyArr[i], copyArr[j]);

console.log("남은 배열 : " + copyArr);

    1   2   3   4   5   6   7
1   1  0.6 0.6 0.5 0.6 0.7 0.3
2       1  0.6 0.6 0.9 0.6 0.4
3           1  0.7 0.6 0.6 0.4  
4               1  0.6 0.6 0.4
5                   1  0.6 0.4

str1부터 5번까지 돌아가면서 확인한결과 위와 같은 점수가 나왔다.

 

여기서 스스로 테스트 해보면서 내린 결론은

0.5이상은 그래도 같은 내용에 가깝고 0.5이하는 다른 내용에 가깝다.

 

이제 논리를 짜야 한다.

이 테스트에서 내가 원하는 올바른 값이 나오려면
str1~6은 같은 내용이니 하나만 나와야 하고 str7은 다른 내용이니 추가되어야 한다.
배열로 치면 newArr=[str1, str7] 이렇게 있어야함.

그러면 기준이 되는 것 1개를 제외 하고는 검색을 하면 안되는데

성능 관련해서 생각을 안해보고 일단 논리를 구현해 보았다.
이중 for문으로 값이 구해지긴 한다. 근데 시간은 0.097초가 걸린다. 이게 오래 걸리는건지는 잘 모르겠다.
일단 카피배열 하나 만든다음 카피 배열은 배열의 요소가 바껴도 되니 splice로 배열을 지워준다.

그렇게 하나씩 비교를 해가며 동일하지 않은 애들만 남겼다.

for (let i = 0; i < copyArr.length; i++) {
  for (let j = i + 1; j < copyArr.length; j++) {
    let score = jarowinkler_similarity(copyArr[i], copyArr[j]);
    if (score > 0.5) {
      copyArr.splice(j, 1);
      j--; // 만약에 배열을 지운다면 해당 자리에서 다시 시작한다.
    }
  }
}

0.5점이 넘는 배열은 없애고 남은 배열을 조회 해보니 중복되지 않는 게시글만 남게 되었다.

더 많은 부분을 비교하여 점수로 표현한뒤 중복된 게시물을 최소한으로 줄일수 있는 Jaro-Winkler similarity을 적용 하였다.

 

 

맞이한 문제

nest.js에서 사용하기위해 import한 뒤 에러가 뜨지 않았고 크롤링을 진행중에 

      for (let i = 0; i < result.length; i++) {
        for (let j = i + 1; j < result.length; j++) {
          let score = jarowinkler_similarity(result[i].title, result[j].title);
          if (score > 0.5) {
            result.splice(j, 1);
            j--;
          }
        }
      }

node에서 작동 되었던 로직을 그대로 가져와 사용 하는 이 코드에서 문제가 발생하였다.

함수 호출 또는 모듈을 잘못 가져왔을 때 발생할수 있는 에러 였다.

jaro-winkler모듈을 설치해서 문제인가 싶어서 @types/jaro-winkler를 적용 시켜 보았다.

여전히 같은 에러가 발생 했다.

String distance

NestJs에서 Jaro-Winkler유사도를 계산 할수 있는 라이브러리인 natural을 설치했다.

이 라이브러리 안에 jaro-wickler유사도를 계산할수 있는 JaroWinklerDistance메서드를 사용하여 문자열의 유사도를 계산할 수 있었다.

 

 

문자열 유사도 구하여 중복 게시물 제외 하기 - NestJs

import { Injectable } from '@nestjs/common';
import puppeteer, { executablePath } from 'puppeteer-core';
import * as natural from 'natural';

@Injectable()
export class NewsService {
  async getNews(board: string) {
    let browser = await puppeteer.launch({
      headless: false,
      executablePath: executablePath('chrome'),
    });
    try {
      const page = await browser.newPage();

      page.setDefaultNavigationTimeout(2 * 60 * 1000); // 최대 탐색시간 밀리초
      await Promise.all([
        // await page.waitForNavigation(), //페이지가 다음 탐색을 완료할 때까지 대기하는 Puppeteer의 메서드, but 이 메서드 사용하면 "chrome이 자동화된 테스트 소프트웨어에 의해 제어되고 있습니다." 문구가 뜨면서 페이지 안뜸.
        await page.goto('https://news.naver.com/breakingnews/section/102/249'),
        await page.click('._CALENDAR_LAYER_TOGGLE'),
        await page.click(`.calendar .calendar-day-2024-04-01`),
        // await page.click(`.calendar .calendar-day-${today()}`),
      ]);
      await clickMorePageEnd(page);

      // 페이지 내의 여러 요소를 선택하고 해당 요소들에 대해 사용자가 제공한 함수를 실행;
      const result = await page.$$eval(
        '.section_latest_article .section_article >ul >li .sa_item_inner .sa_item_flex .sa_text',
        (resultItems) => {
          return resultItems
            .filter((resultItem) => {
              const title = resultItem.querySelector('a').innerText;
              const textElement = resultItem.querySelector('.sa_text_lede');

              const text = textElement ? textElement.textContent.trim() : ''; // 텍스트가 있는 경우에만 가져오고, 없는 경우 빈 문자열 반환

              return title.includes('서울') || text.includes('서울');
            })
            .filter((resultItem) => {
              const keywords = [
                '사고','폭행','화재','낙뢰','지진',
                '재난','홍수','폭발','둔기','살인',
                '절도','충돌','칼부림','묻지마',
              ];
              const title = resultItem.querySelector('a').innerText;
              return keywords.some((keyword) => title.includes(keyword));
            })
            .map((resultItem) => {
              const titleElement = resultItem.querySelector('a');
              const textElement = resultItem.querySelector('.sa_text_lede');
              const newsCompanyElement =
                resultItem.querySelector('.sa_text_press');

              const url = titleElement.href;
              const title = titleElement.innerText;
              const text = textElement ? textElement.textContent.trim() : ''; // 텍스트가 있는 경우에만 가져오고, 없는 경우 빈 문자열 반환
              const newsCompany = newsCompanyElement
                ? newsCompanyElement.textContent.trim()
                : '';
              return { url, title, text, newsCompany };
            });
        },
      );

      for (let i = 0; i < result.length; i++) {
        for (let j = i + 1; j < result.length; j++) {
          let score = natural.JaroWinklerDistance(
            result[i].title,
            result[j].title,
            undefined,
          );
          if (score > 0.5) {
            result.splice(j, 1);
            j--;
          }
        }
      }

      console.log(result);
    } finally {
      // await browser.close();
    }
  }
}
const today = () => {
  const today = new Date();

  const year = today.getFullYear();
  const month = today.getMonth() + 1;
  const strMonth = month < 10 ? '0' + month : month; // 한 자리 수의 월인 경우 앞에 0을 추가하여 두 자리로 만듭니다.
  const day = today.getDate();
  const strDay = day < 10 ? '0' + day : day; // 한 자리 수의 날짜인 경우 앞에 0을 추가하여 두 자리로 만듭니다.

  const formattedDate = `${year}-${strMonth}-${strDay}`;

  return formattedDate;
};
async function clickMorePageEnd(page) {
  while (true) {
    await page.waitForSelector(
      '.section_latest .section_more .section_more_inner',
    ); // 더보기 버튼이 로드될 때까지 기다림.
    const moreButton = await page.$(
      '.section_latest .section_more .section_more_inner',
    ); // 더보기 버튼 요소를 가져옴.
    const endpoint = await page.$(
      '.section_latest .section_more a[style="display: none;"]',
    ); // 화면에 보이지 않는 더보기 버튼 요소를 가져옴.
    if (endpoint) break; // 화면에 보이지 않는 더보기 버튼이 있다면 제일 끝이므로 while문 벗어나기

    await moreButton.evaluate((b) => b.click()); // 더보기 버튼을 클릭.
  }
}

 

 

 

참고 자료 -  h-go-getter,