文档分割的shingling算法

shingling算法是最常见的文档分割算法，说白了就是将一个文档分解成由短字符构成的字符串集合。分割后的文档就可以通过Jaccard相似度等简单的度量标准进行相似度检测了。

k-shingling

对于任意一篇文档，我们把他当成一个字符串，那么他的k-shingling集合就被定义为文档中所有长度为k的子字符串的集合。比如字符串“abcdabd”，他的2-shingling集合就是{ab,bc,cd,da,bd}。

当然，所有类型的子字符串只会在集合中出现一次。不过实际的文档中可能会有连续的空格、TAB、回车或者标点符号之类的东西，一般可以把他们都变成一个空格来进行处理。

shingle大小的选择

显然，如果要使用k-shingling来对文档进行处理就要先确定这个k值，一般而言，要确保这个值足够大，保证任意的shingle在文档中出现的概率较低。不过也没有一个具体的选择方法，倒是有一些经验参数，比如对于英文邮件，可以取k=5；而对于英文研究论文，可以取k=9，因为邮件的长度一般比较低，而论文则相对较高。

一个简单变种

有一种简单的基于词的shingling方法，能够很有效的区分英文新闻与广告。这个应用在对网页进行查重的时候特别有用，因为网页上除了新闻本身之外，通常还会有不同的广告，干扰我们对相同新闻的判断。具体的做法也很简单，就是把shingle定义成一个停用词(就是"and"、"but"、“you”之类经常出现的词)加上后续的两个单词。这样做是因为广告通常比较精炼而较少包含停用词。