문서 중복에 대해서 예전에 Shingle 방법에 대한글을 쓴 경험이 있다.
주로 중복문서의 제거의 Key Issue는 검색 복잡도를 해결하는것이라고 할 수 있다.
md5 hash를 이용하는 방법은 O(n)의 복잡도를, Shingle 계열의 방법을 사용하는것은 O(n^2)의 복잡도를 자랑한다.
어느글과 비슷한 글을 찾기 위한 기능을 검색엔진에서 제공한다면 아마도 주로 Shingle을 이용한 여러가지 방법들중에 하나를 사용해서 제공하리라 본다. 하지만 이는 미리 비슷한 글들에 대해서 계산을 해놓지 않는다면 실시간 유사도 검색를 해서 서비스를 제공하기는 복잡도 측면에서 힘들다.
그런데 위 두가지 방법은 장단점이 있다.
md5는 정확한 중복을 제거하기위해 쓰인다. Shingle 계열의 방법은 근사적인 중복을 탐지하기 위해 쓰이기 때문이다. 둘다 검색엔진과 서비스를 구축하는데 필수적인 기술들이다. md5는 크롤링에 많이 쓰이겠다.
근사적인 중복계산의 복잡도를 줄이기 위해 I-Match 방법을 사용하기도 한다.
이 방법은 아주 빈번한 토큰과 아주 적게 나오는 토큰을 제거한 어느 문서를 대표할만한 토근만을 추출해서 signature을 만드는게 키 이다. 게다가 이 방법을 이용한 lexicon을 유지한다면 유사한 문서에 대한 검색 복잡도를 상당히 줄일 수 있게 된다.
물론 제거되는 토큰의 임계치의 정도를 정하는 문제등이 중복 정확도에 영향을 미치겠지만 이것은 속도와 정확도상의 trade off의 문제라고 생각한다.
말 그대로, 적절히 사용하면 된다는 뜻이다.
인터넷 검색하면서 찾은 발표자료를 첨부한다. 2007년에 만들어진 최신 slide네.
문서 중복에 대해서 . by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.