DSC和DSC—SS算法

   DSC(Digital Syntactic Clus~fing) 及其改进DSC—SS(super Shingle). 两种算法是由Broder在1997年提
出的。DSC将 文章按n个字一组分成一个Shingle,整篇文章就由 个Shin—gles组成。再根据一种过滤策略(如每n个
Shingles中取一个),过滤出其中的一些Shingles,由这些被选中的Shingles参 加比较。由此可见,过滤策略是影响
算法效率的关键。
   DSC所使用的过滤算法是每25个Shingles中保留一个,但是这种方法极大地损害了算法的精确性,很多完全不同的文
档被判断为相似的文档;当文档数目较多时,比较次数极大地损害了该算法的效率。它的改进DSC—SS则是使用Super
Shingles,即将几个Shingles合在一起形成一个Super Shingle,这样与其比较多个Shingles,还不如比较一个Super
 Shingle,减少了比较的次数。但是这种算法对于较为短小的文档而言却是个灾难,在处理短小文档时正确率将大幅下降。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: