搜索引擎判断复制网页一般都基于这么一个思想:为每个网页计算出一组信息指纹(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
相关推荐
综上所述,哈尔滨工业大学信息检索研究室提出的大规模网页快速去重算法,通过创新的特征码技术与B-Tree索引策略,成功解决了传统聚类方法在处理大规模网页去重问题上的局限,展现了卓越的处理能力和精确度,对优化...
### 去除重复网页的改进方法 #### 引言 随着互联网的飞速发展,信息量呈爆炸式增长,如何高效地从海量信息中筛选出有价值的数据...未来的研究可以进一步探索更多维度的信息融合,以期达到更高水平的网页去重效果。
为了有效地实现网页正文去重,本研究设计了一个网页去重系统,其主要结构包括以下几个关键步骤: 1. **预处理阶段**:提取网页正文信息,屏蔽掉网页标题、导航栏等非正文内容。 2. **特征码生成**:根据提取出的...
毕业设计选题 -未来生鲜运输车设计.pptx
内容概要:本文详细探讨了基于樽海鞘算法(SSA)优化的极限学习机(ELM)在回归预测任务中的应用,并与传统的BP神经网络、广义回归神经网络(GRNN)以及未优化的ELM进行了性能对比。首先介绍了ELM的基本原理,即通过随机生成输入层与隐藏层之间的连接权重及阈值,仅需计算输出权重即可快速完成训练。接着阐述了SSA的工作机制,利用樽海鞘群体觅食行为优化ELM的输入权重和隐藏层阈值,从而提高模型性能。随后分别给出了BP、GRNN、ELM和SSA-ELM的具体实现代码,并通过波士顿房价数据集和其他工业数据集验证了各模型的表现。结果显示,SSA-ELM在预测精度方面显著优于其他三种方法,尽管其训练时间较长,但在实际应用中仍具有明显优势。 适合人群:对机器学习尤其是回归预测感兴趣的科研人员和技术开发者,特别是那些希望深入了解ELM及其优化方法的人。 使用场景及目标:适用于需要高效、高精度回归预测的应用场景,如金融建模、工业数据分析等。主要目标是提供一种更为有效的回归预测解决方案,尤其是在处理大规模数据集时能够保持较高的预测精度。 其他说明:文中提供了详细的代码示例和性能对比图表,帮助读者更好地理解和复现实验结果。同时提醒使用者注意SSA参数的选择对模型性能的影响,建议进行参数敏感性分析以获得最佳效果。
2025年中国生成式AI大会PPT(4-1)
内容概要:本文详细介绍了基于Simulink平台构建无刷直流电机(BLDC)双闭环调速系统的全过程。首先阐述了双闭环控制系统的基本架构,即外层速度环和内层电流环的工作原理及其相互关系。接着深入探讨了PWM生成模块的设计,特别是占空比计算方法的选择以及三角波频率的设定。文中还提供了详细的电机参数设置指导,如转动惯量、电感、电阻等,并强调了参数选择对系统性能的影响。此外,针对PI控制器的参数整定给出了具体的公式和经验值,同时分享了一些实用的调试技巧,如避免转速超调、处理启动抖动等问题的方法。最后,通过仿真实验展示了系统的稳定性和鲁棒性,验证了所提出方法的有效性。 适用人群:从事电机控制研究的技术人员、自动化工程领域的研究生及科研工作者。 使用场景及目标:适用于需要深入了解和掌握无刷直流电机双闭环调速系统设计与优化的人群。主要目标是帮助读者学会利用Simulink进行BLDC电机控制系统的建模、仿真和参数优化,从而提高系统的稳定性和响应速度。 其他说明:文章不仅提供了理论知识,还包括了许多实践经验和技术细节,有助于读者更好地理解和应用相关技术。
内容概要:本文详细介绍了西门子S7-1200 PLC与施耐德ATV310/312变频器通过Modbus RTU进行通讯的具体实现步骤和调试技巧。主要内容涵盖硬件接线、通讯参数配置、控制启停、设定频率、读取运行参数的方法以及常见的调试问题及其解决方案。文中提供了具体的代码示例,帮助读者理解和实施通讯程序。此外,还强调了注意事项,如地址偏移量、数据格式转换和超时匹配等。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是那些需要将西门子PLC与施耐德变频器进行集成的工作人员。 使用场景及目标:适用于需要通过Modbus RTU协议实现PLC与变频器通讯的工程项目。目标是确保通讯稳定可靠,掌握解决常见问题的方法,提高调试效率。 其他说明:文中提到的实际案例和调试经验有助于读者避免常见错误,快速定位并解决问题。建议读者在实践中结合提供的代码示例和调试工具进行操作。
内容概要:本文详细介绍了如何使用Verilog在FPGA上实现IIC(Inter-Integrated Circuit)主从机驱动。主要内容包括从机和主机的设计,特别是状态机的实现、寄存器读取、时钟分频策略、SDA线的三态控制等关键技术。文中还提供了详细的代码片段,展示了从机地址匹配逻辑、主机时钟生成逻辑、顶层模块的连接方法以及仿真实验的具体步骤。此外,文章讨论了一些常见的调试问题,如总线竞争、时序不匹配等,并给出了相应的解决方案。 适合人群:具备一定FPGA开发基础的技术人员,尤其是对IIC协议感兴趣的嵌入式系统开发者。 使用场景及目标:适用于需要在FPGA平台上实现高效、可靠的IIC通信的应用场景。主要目标是帮助读者掌握IIC协议的工作原理,能够独立完成IIC主从机系统的开发和调试。 其他说明:文章不仅提供了理论讲解,还包括了大量的实战经验和代码实例,有助于读者更好地理解和应用所学知识。同时,文章还提供了一个思考题,引导读者进一步探索多主设备仲裁机制的设计思路。
内容概要:本文介绍了一款基于C#开发的拖拽式Halcon可视化抓边、抓圆控件,旨在简化机器视觉项目中的测量任务。该控件通过拖拽操作即可快速生成测量区域,自动完成边缘坐标提取,并提供实时反馈。文中详细描述了控件的工作原理和技术细节,如坐标系转换、卡尺生成、边缘检测算法封装以及动态参数调试等功能。此外,还讨论了一些常见问题及其解决方案,如坐标系差异、内存管理等。 适合人群:从事机器视觉开发的技术人员,尤其是熟悉C#和Halcon的开发者。 使用场景及目标:适用于需要频繁进行边缘和圆形特征测量的工业自动化项目,能够显著提高测量效率并减少编码工作量。主要目标是将复杂的测量任务转化为简单的拖拽操作,使非专业人员也能轻松完成测量配置。 其他说明:该控件已开源发布在GitHub上,提供了完整的源代码和详细的使用指南。未来计划扩展更多高级功能,如自动路径规划和亚像素级齿轮齿距检测等。
内容概要:本文详细介绍了西门子200Smart PLC与维纶触摸屏在某疫苗车间控制系统的具体应用,涵盖配液、发酵、纯化及CIP清洗四个主要工艺环节。文中不仅展示了具体的编程代码和技术细节,还分享了许多实战经验和调试技巧。例如,在配液罐中,通过模拟量处理确保温度和液位的精确控制;发酵罐部分,着重讨论了PID参数整定和USS通讯控制变频器的方法;纯化过程中,强调了双PID串级控制的应用;CIP清洗环节,则涉及复杂的定时器逻辑和阀门联锁机制。此外,文章还提到了一些常见的陷阱及其解决方案,如通讯干扰、状态机切换等问题。 适合人群:具有一定PLC编程基础的技术人员,尤其是从事工业自动化领域的工程师。 使用场景及目标:适用于需要深入了解PLC与触摸屏集成控制系统的工程师,帮助他们在实际项目中更好地理解和应用相关技术和方法,提高系统的稳定性和可靠性。 其他说明:文章提供了大量实战经验和代码片段,有助于读者快速掌握关键技术点,并避免常见错误。同时,文中提到的一些优化措施和调试技巧对提升系统性能非常有帮助。
计算机网络课程的结课设计是使用思科模拟器搭建一个中小型校园网,当时花了几天时间查阅相关博客总算是做出来了,现在免费上传CSDN,希望小伙伴们能给博客一套三连支持
《芋道开发指南文档-2023-10-27更新》是针对软件开发者和IT专业人士的一份详尽的资源集合,旨在提供最新的开发实践、范例代码和最佳策略。这份2023年10月27日更新的文档集,包含了丰富的模板和素材,帮助开发者在日常工作中提高效率,保证项目的顺利进行。 让我们深入探讨这份文档的可能内容。"芋道"可能是一个开源项目或一个专业的技术社区,其开发指南涵盖了多个方面,例如: 1. **编程语言指南**:可能包括Java、Python、JavaScript、C++等主流语言的编码规范、最佳实践以及常见问题的解决方案。 2. **框架与库的应用**:可能会讲解React、Vue、Angular等前端框架,以及Django、Spring Boot等后端框架的使用技巧和常见应用场景。 3. **数据库管理**:涵盖了SQL语言的基本操作,数据库设计原则,以及如何高效使用MySQL、PostgreSQL、MongoDB等数据库系统。 4. **版本控制**:详细介绍了Git的工作流程,分支管理策略,以及与其他开发工具(如Visual Studio Code、IntelliJ IDEA)的集成。 5. **持续集成与持续部署(CI/CD)**:包括Jenkins、Travis CI、GitHub Actions等工具的配置和使用,以实现自动化测试和部署。 6. **云服务与容器化**:可能涉及AWS、Azure、Google Cloud Platform等云计算平台的使用,以及Docker和Kubernetes的容器化部署实践。 7. **API设计与测试**:讲解RESTful API的设计原则,Swagger的使用,以及Postman等工具进行API测试的方法。 8. **安全性与隐私保护**:涵盖OAuth、JWT认证机制,HTTPS安全通信,以及防止SQL注入、
内容概要:本文介绍了一种先进的综合能源系统优化调度模型,该模型将风电、光伏、光热发电等新能源与燃气轮机、燃气锅炉等传统能源设备相结合,利用信息间隙决策(IGDT)处理不确定性。模型中引入了P2G(电转气)装置和碳捕集技术,实现了碳经济闭环。通过多能转换和储能系统的协同调度,提高了系统的灵活性和鲁棒性。文中详细介绍了模型的关键组件和技术实现,包括IGDT的鲁棒性参数设置、P2G与碳捕集的协同控制、储能系统的三维协同调度等。此外,模型展示了在极端天气和负荷波动下的优异表现,显著降低了碳排放成本并提高了能源利用效率。 适合人群:从事能源系统优化、电力调度、碳交易等相关领域的研究人员和工程师。 使用场景及目标:适用于需要处理多种能源形式和不确定性的综合能源系统调度场景。主要目标是提高系统的灵活性、鲁棒性和经济效益,减少碳排放。 其他说明:模型具有良好的扩展性,可以通过修改配置文件轻松集成新的能源设备。代码中包含了详细的注释和公式推导,便于理解和进一步改进。
毕业设计的论文撰写、终期答辩相关的资源
该是一个在 Kaggle 上发布的数据集,专注于 2024 年出现的漏洞(CVE)信息。以下是关于该数据集的详细介绍:该数据集收集了 2024 年记录在案的各类漏洞信息,涵盖了漏洞的利用方式(Exploits)、通用漏洞评分系统(CVSS)评分以及受影响的操作系统(OS)。通过整合这些信息,研究人员和安全专家可以全面了解每个漏洞的潜在威胁、影响范围以及可能的攻击途径。数据主要来源于权威的漏洞信息平台,如美国国家漏洞数据库(NVD)等。这些数据经过整理和筛选后被纳入数据集,确保了信息的准确性和可靠性。数据集特点:全面性:涵盖了多种操作系统(如 Windows、Linux、Android 等)的漏洞信息,反映了不同平台的安全状况。实用性:CVSS 评分提供了漏洞严重程度的量化指标,帮助用户快速评估漏洞的优先级。同时,漏洞利用信息(Exploits)为安全研究人员提供了攻击者可能的攻击手段,有助于提前制定防御策略。时效性:专注于 2024 年的漏洞数据,反映了当前网络安全领域面临的新挑战和新趋势。该数据集可用于多种研究和实践场景: 安全研究:研究人员可以利用该数据集分析漏洞的分布规律、攻击趋势以及不同操作系统之间的安全差异,为网络安全防护提供理论支持。 机器学习与数据分析:数据集中的结构化信息适合用于机器学习模型的训练,例如预测漏洞的 CVSS 评分、识别潜在的高危漏洞等。 企业安全评估:企业安全团队可以参考该数据集中的漏洞信息,结合自身系统的实际情况,进行安全评估和漏洞修复计划的制定。
内容概要:本文档作为建模大赛的入门指南,详细介绍了建模大赛的概念、类型、竞赛流程、核心步骤与技巧,并提供实战案例解析。文档首先概述了建模大赛,指出其以数学、计算机技术为核心,主要分为数学建模、3D建模和AI大模型竞赛三类。接着深入解析了数学建模竞赛,涵盖组队策略(如三人分别负责建模、编程、论文写作)、时间安排(72小时内完成全流程)以及问题分析、模型建立、编程实现和论文撰写的要点。文中还提供了物流路径优化的实战案例,展示了如何将实际问题转化为图论问题并采用Dijkstra或蚁群算法求解。最后,文档推荐了不同类型建模的学习资源与工具,并给出了新手避坑建议,如避免过度复杂化模型、重视可视化呈现等。; 适合人群:对建模大赛感兴趣的初学者,特别是高校学生及希望参与数学建模竞赛的新手。; 使用场景及目标:①了解建模大赛的基本概念和分类;②掌握数学建模竞赛的具体流程与分工;③学习如何将实际问题转化为数学模型并求解;④获取实战经验和常见错误规避方法。; 其他说明:文档不仅提供了理论知识,还结合具体实例和代码片段帮助读者更好地理解和实践建模过程。建议新手从中小型赛事开始积累经验,逐步提升技能水平。
该资源为protobuf-6.30.1-cp310-abi3-win32.whl,欢迎下载使用哦!
内容概要:本文档详细介绍了基于Linux系统的大数据环境搭建流程,涵盖从虚拟机创建到集群建立的全过程。首先,通过一系列步骤创建并配置虚拟机,包括设置IP地址、安装MySQL数据库等操作。接着,重点讲解了Ambari的安装与配置,涉及关闭防火墙、设置免密登录、安装时间同步服务(ntp)、HTTP服务以及配置YUM源等关键环节。最后,完成了Ambari数据库的创建、JDK的安装、Ambari server和agent的部署,并指导用户创建集群。整个过程中还提供了针对可能出现的问题及其解决方案,确保各组件顺利安装与配置。 适合人群:具有Linux基础操作技能的数据工程师或运维人员,尤其是那些需要构建和管理大数据平台的专业人士。 使用场景及目标:适用于希望快速搭建稳定可靠的大数据平台的企业或个人开发者。通过本指南可以掌握如何利用Ambari工具自动化部署Hadoop生态系统中的各个组件,从而提高工作效率,降低维护成本。 其他说明:文档中包含了大量具体的命令行指令和配置细节,建议读者按照顺序逐步操作,并注意记录下重要的参数值以便后续参考。此外,在遇到问题时可参照提供的解决方案进行排查,必要时查阅官方文档获取更多信息。