搜索引擎判断复制网页一般都基于这么一个思想:为每个网页计算出一组信息指纹(Fingerprint)
,若两个网页有一定数量相同的信息指纹,则认为这两个网页的内容重叠性很高,也就是说两个网页是内容复制的。
很多搜索引擎判断内容复制的方法都不太一样,主要是以下两点的不同:
1、计算信息指纹(Fingerprint)
的算法;
2、判断信息指纹的相似程度的参数。
在描述具体的算法前,先说清楚两点:
1、什么是信息指纹?
信息指纹就是把网页里面正文信息,提取一定的信息,可以是关键字、词、句子或者段落及其在网页里面的权重等,对它进行加密,如MD5加密,从而形成的一个字符串。信息指纹如同人的指纹,只要内容不相同,信息指纹就不一样。
2、算法提取的信息不是针对整张网页,而是把网站里面共同的部分如导航条、logo、版权等信息(这些称之为网页的“噪音”)过滤掉后剩下的文本。
分段签名算法
这种算法是按照一定的规则把网页切成N段,对每一段进行签名,形成每一段的信息指纹。如果这N个信息指纹里面有M个相同时(m是系统定义的阙值),则认为两者是复制网页。
这种算法对于小规模的判断复制网页是很好的一种算法,但是对于像google这样海量的搜索引擎来说,算法的复杂度相当高。
基于关键词的复制网页算法
像google这类搜索引擎,他在抓取网页的时候都会记下以下网页信息:
1、网页中出现的关键词(中文分词技术)以及每个关键词的权重(关键词密度);
2、提取meta
descrīption或者每个网页的512个字节的有效文字。
关于第2点,baidu和google有所不同,google是提取你的meta
descrīption,如果没有查询关键字相关的512个字节,而百度是直接提取后者。这一点大家使用过的都有所体会。
在以下算法描述中,我们约定几个信息指纹变量:
Pi表示第i个网页;
该网页权重最高的N个关键词构成集合Ti={t1,t2,...tn},其对应的权重为Wi={w1,w2,...wi}
摘要信息用Des(Pi)表示,前n个关键词拼成的字符串用Con(Ti)表示,对这n个关键词排序后形成的字符串用Sort(Ti)表示。
以上信息指纹都用MD5函数进行加密。
基于关键词的复制网页算法有以下5种:
1、MD5(Des(Pi))=MD5(Des(Pj))
,就是说摘要信息完全一样,i和j两个网页就认为是复制网页;
2、MD5(Con(Ti))=MD5(Con(Tj))
,两个网页前n个关键词及其权重的排序一样,就认为是复制网页;
3、MD5(Sort(Ti))=MD5(Sort(Tj))
,两个网页前n个关键词一样,权重可以不一样,也认为是复制网页。
4、MD5(Con(Ti))=MD5(Con(Tj))并且Wi-Wj的平方除以Wi和Wj的平方之和小于某个阙值a
,则认为两者是复制网页。
5、MD5(Sort(Ti))=MD5(Sort(Tj))并且Wi-Wj的平方除以Wi和Wj的平方之和小于某个阙值a
,则认为两者是复制网页。
关于第4和第5的那个阙值a,主要是因为前一个判断条件下,还是会有很多网页被误伤,搜索引擎开发根据权重的分布比例进行调节,防止误伤。
这
个是北大天网搜索引擎的去重算法(可以参考:《搜索引擎--原理、技术与系统》一书),以上5种算法运行的时候,算法的效果取决于N,就是关键词数目的选
取。当然啦,选的数量越多,判断就会越精确,但是谁知而来的计算速度也会减慢下来。所以必须考虑一个计算速度和去重准确率的平衡。据天网试验结果,10个
左右关键词最恰当。
网页去重的算法
1. I-Match
2. Shingliing
3. SimHashing( locality sensitive hash)
4. Random Projection
5. SpotSig
6. combined
I-Match算法
I-Match算法有一个基本的假设说:不经常出现的词和经常出现的词不会影响文档的语义,所以这些词是可以去掉的。
算法的基本思想是:将文档中有语义的单词用hash的办法表示成一个数字,数字的相似性既能表达文档的相似性
算法的框架是:
1. 获取文档(或者是主体内容)
2. 将文档分解成token流,移除格式化的标签
3. 使用term的阈值(idf),保留有意义的tokens
4. 插入tokens到升序排列的排序树中
5. 对每一个token,相加得到一个hash值,知道文档结束为止
6. 将元组(doc_id,SHA hash) 插入到某一词典中,如果词典有冲突,这两个文档相似。
算法有一个缺点是稳定性差。如果文档的某个词改变了,最终的hash值就会发生显著的变化。对空文档,算法是无效的。
有一个解决办法是,用随机化的方法,参考Lexicon randomization for near-duplicate
detection with I-Match。具体细节这里就不提了
Shingling算法
Shingling算法说,I-Match以词为单位做hash显然是不准确的,因为它忽略了文档之间书顺序。另,一个Shingle为连续的若干个单词的串。
Shingling算法有个很少神奇的数学背景。如果一个shingle的长度为k,那么长度为n的文档就有n-k+1个shingle,每一个
shingle可以用MD5或者其他算法表示成一个fingerprint,而两个文档的相似性Jacard相似性来表示,Jarcard公式是指两个集
合的相似性=集合之交/集合之并。为了估计两个文档的相似性,有时候n-k+1个fingerprint还是太大了,所以取m个fingerprint函
数,对每一个函数fi,都可以计算出n-k+1个fingerprint,取其中的最小的fingerprint,成为i-minvalue.
那么一个文档机会有m个i-minvalue。数学上,Broder大师说:
平均来讲,两个文档中相同的唯一single的比率和两个文档中相同的i-minvalue的比率是一样的
Shingling的算法框架是:
1. 获取文档(或者是主体内容)
2.
将文档分解成n-k+1个shingle,取m个fingerprint函数,对每一个fingerpint函数计算i-minvalue值
3. 将m个i-minvalue值组合成更少m’个surpersingle
4.计算两个文档相同的surpergingle的个数a。
5. 如果a大于某一个值b(say:2),那么两个文档Jarcard 相似
一般的参数设置为:m=84,m’=6,b=2
SimHash 算法
locality sensitive
hash算法博大精深。基本思想是,如果两个东西相似,我可以用一个hash函数把他们投影到相近的空间中LSH。用到near
duplication detection上,算法框架是:
1. 将文档转换为特征的集合,每一个特征有一个权重
2. 利用LSH函数把特征向量转换为f位的fingerprint,如:64
3. 查找fingerprint的海明距离
haha,看,多么简单和明朗,这里的几个问题及时寻找正确的LSH
Random Projection算法
shingling关注了文档顺序,但是忽略了文档单词出现的频率,random projection说我要讨论文档的频率。
Random Projection也是很有意思的一种算法,它是一种随机算法。简单描述为:
1. 将每一个token映射到b位的空间。每一个维度是由{-1,1}组成。对所有页面投影函数是一样的
2. 每一个页面的b维度向量,是所有token的投影的简单加和
3. 最后把b维向量中的正数表示为1,负数和0都写成0
4. 比较两个page的b维向量一致的个数
Charikar最牛的地方是,证明,两个b位变量一致的位数的比率就是文档向量的consine相似性。这里的数学基础还是很有意思的,如果感兴趣,可以参考M.S.
Charikar. Similarity Estimation Techniques for Rounding
Algorithm(May 2002)
SpotSig算法
ref:SpotSigs:Robust and Efficient Near Duplicate Detection in
Large Web Collection
SpotSig是个比较有意思的算法,它说,我为什么要关注所有的单词啊,我要关注的单词是有语义的词,哪些是有语义的词呢?哦,想 the
a this an
的等虚词后面的就是我要关注的东西罗。Spot就是指这些虚词的后面的词串。然后呢,每一个文档我都有很多很多Spot了,现在一个文档就是一个Spot
的集合,两个文档是相似程度就是集合的Jaccard相似度。算法虽然简单,但是我想重点是两个比较有借鉴意义的工程上的性能考虑。
1. Optimal Partition
Sim(A,B) = | A B交集| / | A B 并集| <= min(A,B)/max(A,B)
<= |A|/|B| say: |A|<|B|
好了,这是一个很好的枝剪条件,如果文档spot vector的个数比小于某个值(当然是,小 /
大),就可以完全不用求交,并了。Optimal Partition就是说,好啊,我把每一个文档的spot
vector的长度都投影到相应的从小到大的bucket中,保证|d1|/|d2| >=r if |d1|
< |d2| .
且不存在这样的反例。另一个保证是这个bucket是满足条件的最小的。有了这个partition,我们最多只用关心相邻的三个bucket了
2. Inverted Index
Pruning
说,两个文档,如果能相似,起码有一个公共的spot。逆向索引说的就是把spot做为index,包含它的所有文档作为其value。
有了这两个工具,计算复杂度可以明显下降,因为它不会计算不能是duplication的文档。
转自:http://blog.sina.com.cn/s/blog_48299b340100jsfg.html
相关推荐
### 去除重复网页的改进方法 #### 引言 随着互联网的飞速发展,信息量呈爆炸式增长,如何高效地从海量信息中筛选出有价值的数据...未来的研究可以进一步探索更多维度的信息融合,以期达到更高水平的网页去重效果。
为了有效地实现网页正文去重,本研究设计了一个网页去重系统,其主要结构包括以下几个关键步骤: 1. **预处理阶段**:提取网页正文信息,屏蔽掉网页标题、导航栏等非正文内容。 2. **特征码生成**:根据提取出的...
矢量边界,行政区域边界,精确到乡镇街道,可直接导入arcgis使用
毕业设计
毕业设计
经验贝叶斯EB的简单例子
智慧园区,作为现代城市发展的新形态,旨在通过高度集成的信息化系统,实现园区的智能化管理与服务。该方案提出,利用智能手环、定制APP、园区管理系统及物联网技术,将园区的各类设施与设备紧密相连,形成一个高效、便捷、安全的智能网络。从智慧社区到智慧酒店,从智慧景区到智慧康养,再到智慧生态,五大应用板块覆盖了园区的每一个角落,为居民、游客及工作人员提供了全方位、个性化的服务体验。例如,智能手环不仅能实现定位、支付、求助等功能,还能监测用户健康状况,让科技真正服务于生活。而智慧景区的建设,更是通过大数据分析、智能票务、电子围栏等先进技术,提升了游客的游玩体验,确保了景区的安全有序。 尤为值得一提的是,方案中的智慧康养服务,展现了科技对人文关怀的深刻体现。通过智慧手环与传感器,自动感知老人身体状态,及时通知家属或医疗机构,有效解决了“空巢老人”的照护难题。同时,智慧生态管理系统的应用,实现了对大气、水、植被等环境要素的实时监测与智能调控,为园区的绿色发展提供了有力保障。此外,方案还提出了建立全域旅游营销平台,整合区域旅游资源,推动旅游业与其他产业的深度融合,为区域经济的转型升级注入了新的活力。 总而言之,这份智慧园区建设方案以其前瞻性的理念、创新性的技术和人性化的服务设计,为我们展示了一个充满智慧与活力的未来园区图景。它不仅提升了园区的运营效率和服务质量,更让科技真正融入了人们的生活,带来了前所未有的便捷与舒适。对于正在规划或实施智慧园区建设的决策者而言,这份方案无疑提供了一份宝贵的参考与启示,激发了他们对于未来智慧生活的无限遐想与憧憬。
数学建模相关主题资源2
内容概要:本文围绕SQL在求职和实际工作中的应用展开,详细解析了SQL的重要性及其在不同行业中不可替代的地位。文章首先强调了SQL作为“一切数据工作的起点”,是数据分析、数据挖掘等领域必不可少的技能,并介绍了SQL与其他编程语言在就业市场的对比情况。随后重点探讨了SQL在面试过程中可能出现的挑战与应对策略,具体涉及到询问澄清问题、正确选择JOIN语句类型、恰当使用GROUP BY及相关过滤条件的区别、理解和运用窗口函数等方面,并给出了详细的实例和技巧提示。另外提醒面试者要注意重复值和空值等问题,倡导与面试官及时沟通。文中引用IEEE Spectrum编程语言排行榜证明了SQL不仅广泛应用于各行各业,在就业市场上也最受欢迎。 适用人群:从事或打算转入数据科学领域(包括但不限于数据分析师、数据科学家、数据工程师等职业方向),并对掌握和深入理解SQL有一定需求的专业人士,尤其是正准备涉及SQL相关技术面试的求职者。 使用场景及目标:帮助用户明确在面对复杂的SQL查询题目时能够更加灵活应对,提高解题效率的同时确保准确性;同时让用户意识到SQL不仅仅是简单的数据库查询工具,而是贯穿整个数据处理流程的基础能力之一,进而激发他们进一步探索的热情。 其他说明:SQL在性能方面优于Excel尤其适用于大规模数据操作;各知名企业仍将其视为标准数据操作手段。此外还提供了对初学者友好的建议,针对留学生普遍面临的难题如零散的学习资料、昂贵且效果不佳的付费教程以及难以跟上的纯英教学视频给出了改进的方向。
COMSOL仿真揭示石墨烯临界耦合光吸收特性:费米能级调控下的光学性能探究,COMSOL仿真揭示石墨烯临界耦合光吸收特性:费米能级调控下的光学性能探究,COMSOL 准 BIC控制石墨烯临界耦合光吸收。 COMSOL 光学仿真,石墨烯,光吸收,费米能级可调下图是仿真文件截图,所见即所得。 ,COMSOL; 准BIC; 石墨烯; 临界耦合光吸收; 光学仿真; 费米能级可调。,COMSOL仿真:石墨烯光吸收的BIC控制与费米能级调节
Labview与Proteus串口仿真下的温度采集与报警系统:Keil单片机程序及全套视频源码解析,Labview与Proteus串口仿真温度采集及上位机报警系统实战教程:设定阈值的Keil程序源码分享,labview 和proteus 联合串口仿真 温度采集 上位机报警 设定阈值单片机keil程序 整套视频仿真源码 ,关键词:LabVIEW;Proteus;串口仿真;温度采集;上位机报警;阈值设定;Keil程序;视频仿真源码。,LabVIEW与Proteus联合串口仿真:温度采集与报警系统,Keil程序与阈值设定全套视频源码
整车性能目标书:涵盖燃油车、混动车及纯电动车型的十六个性能模块目标定义模板与集成开发指南,整车性能目标书:涵盖燃油车、混动车及纯电动车型的十六个性能模块目标定义模板与集成开发指南,整车性能目标书,汽车性能目标书,十六个性能模块目标定义模板,包含燃油车、混动车型及纯电动车型。 对于整车性能的集成开发具有较高的参考价值 ,整车性能目标书;汽车性能目标书;性能模块目标定义模板;燃油车;混动车型;纯电动车型;集成开发;参考价值,《汽车性能模块化目标书:燃油车、混动车及纯电动车的集成开发参考》
熵值法stata代码(含stata代码+样本数据) 面板熵值法是一种在多指标综合评价中常用的数学方法,主要用于对不同的评价对象进行量化分析,以确定各个指标在综合评价中的权重。该方法结合了熵值理论和面板数据分析,能够有效地处理包含多个指标的复杂数据。
“电子电路”仿真资源(Multisim、Proteus、PCB等)
在 GEE(Google Earth Engine)中,XEE 包是一个用于处理和分析地理空间数据的工具。以下是对 GEE 中 XEE 包的具体介绍: 主要特性 地理数据处理:提供强大的函数和工具,用于处理遥感影像和其他地理空间数据。 高效计算:利用云计算能力,支持大规模数据集的快速处理。 可视化:内置可视化工具,方便用户查看和分析数据。 集成性:可以与其他 GEE API 和工具无缝集成,支持多种数据源。 适用场景 环境监测:用于监测森林砍伐、城市扩展、水体变化等环境问题。 农业分析:分析作物生长、土地利用变化等农业相关数据。 气候研究:研究气候变化对生态系统和人类活动的影响。
内容概要:本文介绍了C++编程中常见指针错误及其解决方案,并涵盖了模板元编程的基础知识和发展趋势,强调了高效流操作的最新进展——std::spanstream。文章通过一系列典型错误解释了指针的安全使用原则,强调指针初始化、内存管理和引用安全的重要性。随后介绍了模板元编程的核心特性,展示了编译期计算、类型萃取等高级编程技巧的应用场景。最后,阐述了C++23中引入的新特性std::spanstream的优势,对比传统流处理方法展现了更高的效率和灵活性。此外,还给出了针对求职者的C++技术栈学习建议,涵盖了语言基础、数据结构与算法及计算机科学基础领域内的多项学习资源与实战练习。 适合人群:正在学习C++编程的学生、从事C++开发的技术人员以及其他想要深入了解C++语言高级特性的开发者。 使用场景及目标:帮助读者掌握C++中的指针规则,预防潜在陷阱;介绍模板元编程的相关技术和优化方法;使读者理解新引入的标准库组件,提高程序性能;引导C++学习者按照有效的路径规划自己的技术栈发展路线。 阅读建议:对于指针部分的内容,应当结合实际代码样例反复实践,以便加深理解和记忆;在研究模板元编程时,要从简单的例子出发逐步建立复杂模型的理解能力,培养解决抽象问题的能力;而对于C++23带来的变化,则可以通过阅读官方文档并尝试最新标准特性来加深印象;针对求职准备,应结合个人兴趣和技术发展方向制定合理的学习计划,并注重积累高质量的实际项目经验。
JNA、JNI, Java两种不同调用DLL、SO动态库方式读写FM1208 CPU卡示例源码,包括初始化CPU卡、创建文件、修改文件密钥、读写文件数据等操作。支持Windows系统、支持龙芯Mips、LoongArch、海思麒麟鲲鹏飞腾Arm、海光兆芯x86_Amd64等架构平台的国产统信、麒麟等Linux系统编译运行,内有jna-4.5.0.jar包,vx13822155058 qq954486673
内容概要:本文全面介绍了Linux系统的各个方面,涵盖入门知识、基础操作、进阶技巧以及高级管理技术。首先概述了Linux的特点及其广泛的应用领域,并讲解了Linux环境的搭建方法(如使用虚拟机安装CentOS),随后深入剖析了一系列常用命令和快捷键,涉及文件系统管理、用户和权限设置、进程和磁盘管理等内容。此外,还讨论了服务管理的相关指令(如nohup、systemctl)以及日志记录和轮替的最佳实践。这不仅为初学者提供了一个完整的知识框架,也为中级和高级用户提供深入理解和优化系统的方法。 适合人群:适用于有意深入了解Linux系统的学生和专业技术人员,特别是需要掌握服务器运维技能的人群。 使用场景及目标:本文适合初次接触Linux的操作员了解基本概念;也适合作为培训教材,指导学生逐步掌握各项技能。对于有一定经验的技术人员而言,则可以帮助他们巩固基础知识,并探索更多的系统维护和优化可能性。 阅读建议:建议按照文章结构循序渐进地学习相关内容,尤其是结合实际练习操作来加深记忆和理解。遇到复杂的问题时可以通过查阅官方文档或在线资源获得更多帮助。