Fuzzy Deduplication와 Exact Deduplication, URL Deduplication
Fuzzy Deduplication
Fuzzy Deduplication은 완전히 일치하지 않아도 유사한 문서들을 찾아 제거해주는 기법이다. 예를 들어, 한국에서 연합뉴스 같은 통신사가 기사를 발행하면, KBS나 MBC 같은 언론사들이 이를 받아 뉴스로 제작하는 경우가 있다. 이처럼 동일한 뉴스 정보가 여러 언론사에 의해 배포되는 상황이 발생할 수 있다. 그러나 이런 정보는 Exact Match(EM)처럼 완전히 일치하지 않고, 일부 단어가 다르게 구성된 형태로 배포되곤 한다.
이를 방지하기 위해 Fuzzy Deduplication과 MinHash라는 해싱 알고리즘을 사용하여 문서 간 유사도가 일정 수준 이상일 경우 해당 문서를 제거할 수 있다.
하지만 이렇게 Fuzzy Deduplication을 사용한다고 해서 모든 유사 문서가 제거되는 것은 아니다. 그 이유는 MinHash 과정에서 전체 데이터셋의 100%와 비교하지 않기 때문이다. 만약 모든 데이터를 비교한다면, O(N^2)에 달하는 막대한 연산량이 필요하다. 예를 들어, 데이터가 1000개라면 4개의 버킷으로 나눠서 각 버킷 내 250개 문서끼리 비교하는 방식으로 처리한다. 다른 버킷에 있는 문서들은 중복 여부를 따지지 않고 그대로 두기 때문에 완벽한 중복 제거는 어렵다. 이러한 남은 중복 처리는 Exact Deduplication으로 해결한다.
Exact Deduplication
Exact Deduplication에서는 문장을 일부 단위로 나누어 중복을 처리한다. 예를 들어, 시퀀스 레벨에서 Suffix Array를 사용한다. 문장의 시작 부분을 검사하면서 일정 부분까지 Suffix Array로 두고, 이 부분이 일치하면 전체 문장을 검사한다. 특정 개수 이상의 연속된 토큰이 일치하는 경우, 해당 문장을 중복된 것으로 간주하고 제거할 수 있다. 또한, 이 문장이 특정 문서에 포함되어 있다면 해당 부분을 제거하게 된다.
예시:
- 철수는 다리가 아팠지만 자리를 양보했다.
- 철수는 다리가 튼튼해서 오래 달려도 아프지 않았다.
- 영희는 손이 아팠고, 철수는 머리가 아팠다.
위와 같은 문장이 있을 때, 첫 번째 문장에서 "철수는 다리가"라는 부분으로 Suffix Array를 생성했다고 가정해 보자. 두 번째 문장에 동일한 구절이 포함되어 있고, 이때 두 문장에서 지정한 개수 이상의 연속된 토큰이 겹친다면, 중복된 내용으로 판단하여 해당 문장을 제거할 수 있다. 이렇게 Suffix Array로 일치하는 부분이 일정 길이 이상일 경우 이를 중복으로 보고 제거하는 것이다.
URL Deduplication
URL Deduplication은 URL이 완전히 일치하는지를 확인하는 방식이다. 예를 들어, 웹사이트 크롤링 모델을 만들 때 어떤 뉴스 사이트에 들어가면 추천 링크가 표시된다. 이 추천 링크를 타고 가면 원래 봤던 페이지가 추천 링크로 다시 나타날 수 있다. 이처럼 크롤러가 사이트를 가져올 때 중복된 URL을 여러 번 방문하게 되어 Revisited URL로 처리되고, 중복된 내용이 상당히 많아진다.