Mythsman


乐极生悲,苦尽甘来。


文档分割的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”之类经常出现的词)加上后续的两个单词。这样做是因为广告通常比较精炼而较少包含停用词。