Shingles algorithm의 간단한 설명

http://en.wikipedia.org/wiki/W-shingling
The document, "a rose is a rose is a rose" can be tokenized as follows.
(a,rose,is,a,rose,is,a,rose)
The set of all contiguous sequences of 4 tokens (N-grams, here: 4-grams) is
{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) }
By removing duplicate elements from this set, a 4-shingling is obtained:
{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }

굳이 설명을 한다면.....

"a rose is a rose is a rose” 라는 문서를 아래와 같이 토큰화하고
(a,rose,is,a,rose,is,a,rose)
하나의 SET를 4개의 연속된 텀으로 구성한다.
{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) }
여기서 중복을 제거하면
{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }  최종적으로 나오게 된다.

이제 공식에 대입만 하면 된다.
A문서 20개
B문서 15개
A B의 교집합되는 10개 <- 요놈만 잘 구하면 된다.
(10 / 20+15-10 ) * 100 = 40% 라는 유사도가 나오게 된다.

물론 여기까지만 생각하면 간단하지만 많은 데이터를 일일히 비교한다면 쉬운 일은 아닌 듯 하다.

wikipia에 있는 내용을 단순히 옮겨 놓은 정도이다.

JSP로 간단히 구현해보았다. 2,3,4개의 텀으로 구분할때마다 조금씩 유사도는 달라진다.
더 정확한지는 물론 알 수 없다. 정답이 없으니.......

개인적으로 서버가 없는 관계로 URL 생략
소스는 정리해서 올려 놓아야겠다.