梦想很圆满,现实很骨感 01月23日

也许梦

梦醒了,现实终究会到来

梦想很圆满,现实很骨感

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被认为是当前最好的两个算法。 (更多…)