문서의 색인을 만드는데 중복문서 제거는 항상 이슈가 되는 사항이다.
물론 이 부분은 문서를 수집하는 시기부터 웹로봇이 주로 행하는 작업이기도 하고 로봇을 지나 온 문서도 마찬가지로 중복 문서가 존재하고 있는게 사실이다.

중복을 어느정도를 중복으로 봐야 되는지도 상당히 중요한 이슈 사항이여서 exact duplicate 와 유사도를 측정해 중복을 판단하는 방법이 존재하고 있다.

exact duplicate는 구현자체는 그리 어렵지 않지만 문서의 작은 공백 하나만 달라져도 다른 문서로 판단하기 때문에 애로사항이 많다.

문서 자체를 md5 해쉬나 sha 계열의 해싱 함수로 해시 문자열을 만들어 이를 문서의 지문(fingerprint)로 저장해서 문서의 고유값으로 유지하는 것이다. md5 해쉬 알고리즘을 분석 해본 필자의 생각을 빌리자면 웹문서의 counter 값이 1만 증가한 상태라도 그 문서는 이전에 방문한  counter 1이 적은 페이지와 판이하게 다르게 나온다.  (알고리즘 내부에 쓰이는 bit 연산의 강력함 덕분이다.)
그래서 웹로봇에서는 편법으로 tag와 숫자를 제거한 문자열만을 해싱해서 저장하기도 한다. (실제 이렇게 하면 상당히 성능이 개선된다. 게다가 공백까지 제거해서 저장한다면?)

그럼 부분적으로 비슷한 문서들은 어떻게 판단을 할까?

예를 들어 어느 블로그의 글을 훔쳐서 앞 뒤의 글만 다르게 입력해서 자기 글인양 하는 포스팅은 어떻게 제거를 하거나 랭킹을 낮춰 버릴것인가?

한 가지 방법을 소개한다.

Shingles라는 방법으로 전에 mining the web 이라는 책에 소개가 되었던 개념인데 그냥 그당시 이런게 있구나 하고 생각하고 있다가 요즘에 정리를 해보려고 접근해 봤다.

하나의 shingle은 하나의 문서에서 나타나는 연속된 텀의 집합하나를 의미한다.

예를 들어 “a rose is a rose is a rose” 라는 문자열은 아래와 같이 토큰화 되고

(a,rose,is,a,rose,is,a,rose)

하나의 shingle을 4개의 텀이라고 지칭한다면,
{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) }
위와 같이 shingle들이 나올것이다.

여기서 중복 제거를 하면
{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }
이와 같은 shinge들이 최종 결과로 나오게 될 것이다.

이런 shingle들과 아래의 식을 이용해서 문서의 similarity를 검사하게 된다.

두개의 문서가 있다고 하자.
각 문서는 10개의  shingle을 가지고 있고 , 같은 shingle은 5개라고 한다면
5/15 = 0.33의 유사도를 가지고 있게 된다.
1에 가까운 값이 된다면 같은 문서를 의미하겠다.

여기서 문제는 이 r이라는 값을 어떻게 이용하느냐 인데 그러니까 중복의 임계치는 얼마로 둘것인가의 문제가 나오고, 수많은 문서 집단에서 이 작업을 하기위한 효율성의 문제가 제기 된다.

효율성의 문제 그러니까 복잡도의 문제를 해결하기 위해 여러 알고리즘이 제시되었는데.
DSC 알고리즘의 경우는 빈번히 나오는 shingle들을 제거하여서 속도를 높이는 알고리즘이 되겠고 또한 매 25번째 shingle을 저장해서 그것을 문서의 비교 shingle로 해서 비교 횟수를 줄이는 등의 여러 방법들이 제시되고 있다.
물론 이런 shingle들은 md5 같은 해쉬값으로 저장이 되어서 문자열 비교의 비효율성을 줄이기도 한다.

그리고 DSC-SS같은 알고리즘은 shingle 여러개를 조합해 super shingle을 만들어서 효율성을 개선하고자 하기도 했다. 하지만 이 알고리즘은 짧은 문서에서는 성능이 좋지 않음이 알려져 있다.

이 shingles 방법 이외에도 상당히 좋은 I-Match 방법이 있는데 이 방법은 싸이오블레이드 형님이 아주 잘 알고 있는 방법이니 내일 술자리에서 상세한 설명을 부탁드려 봐야 겠다. (빨리 이거 정리한 ppt문서 공개하시오! ㅋㅋ)

중복 문서 제거에 대한 : 주로 Shingle 방법 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.