什么是Shingling算法

2017/06/15 14:48
阅读数 1K

shingling算法用于计算两个文档的相似度,例如,用于网页去重。维基百科对w-shingling的定义如下:

In natural language processing a w-shingling is a set of unique "shingles"—contiguous subsequences of tokens in a document —that can be used to gauge the similarity of two documents. The w denotes the number of tokens in each shingle in the set.

维基百科用一个浅显的例子讲解了shingling算法的原理。比如,一个文档

"a rose is a rose is a rose"

分词后的词汇(token,语汇单元)集合是

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

那么w=4的4-shingling就是集合:

{ (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) }

给定shingle的大小,两个文档A和B的相似度 r 定义为:

r(A,B)=|S(A)∩S(B)| / |S(A)∪S(B)|

其中|A|表示集合A的大小。

因此,相似度是介于0和1之间的一个数值,且r(A,A)=1,即一个文档和它自身 100%相似。

 

扩展阅读

  • Shingling算法的更详细说明参见博客网页去重——Shingling算法,该文作者使用的类库是com.planetj.math.rabinhash.RabinHashFunction32
  • 距离和相似度度量
    • 范数和欧拉距离
    • cosine similarity
    • Jacard index
    • Pearson correlation coefficient
    • 编辑距离或者Levenshtein distance
    • SimRank 相似
  • 网页去重-算法篇
    • I-Match
    • Shingling
    • SimHashing( locality sensitive hash)
    • Random Projection
    • SpotSig
    • combined
  • 一个对算法进行解释的外文资料sketching
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部