simhash算法的原理 01月06日
第一次听说google的simhash算法[1]时，我感到很神奇。传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值，原理上相当于伪随机数产生算法。传统hash算法产生的两个签名，如果相等，说明原始内容在一定概率下是相等的；如果不相等，除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字节，所产生的签名也很可能差别极大。从这个意义上来说，要设计一个hash算法，对相似的内容产生的签名也相近，是更为艰难的任务，因为它的签名值除了提供原始内容是否相等的信息外，还能额外提供不相等的原始内容的差异程度的信息。
因此当我知道google的simhash算法产生的签名，可以用来比较原始内容的相似度时，便很想了解这种神奇的算法的原理。出人意料，这个算法并不深奥，其思想是非常清澈美妙的。 (更多…)
网页查重算法Shingling和Simhash研究 01月06日
据统计,互联网上的重复网页约占 30%~45%。这其中有由于镜像转载引起的内容完全相同的网页,也有仅存在微小差别的网页,比如广告,计数器,时间戳等不同,而这些差别是和搜索的内容 无关的。根据中国互联网络信息中心2005年7月发布的统计报告显示,用户在回答“检索信息时遇到的最大问题”这一提问时,选择“重复信息太多”选项的占 44.6%,排名第1位[1]。将相似的网页消除,可以节省网络带宽,减少占用的存储空间,提高索引的质量,即提高查询服务的效率和质量,同时减轻网页所 在远程服务器的负担。在网页查重算法中shingling和simhash被认为是当前最好的两个算法。 (更多…)