Table of Contents
2、整体文档处理
Home Database Mysql Tutorial 从100万篇文档中找出相似度较高的文档对

从100万篇文档中找出相似度较高的文档对

Jun 07, 2016 pm 03:56 PM
us find out document resemblance High

当我们想从100万篇文档中找出相项较高的文档对,就需要两两相互比较,一共是5千亿次,如果每次比较花费1微秒,那一共需要6天才能计算完,这肯定是不行的。 问题应用: 1、论文查重,读过大学的就都听过这个词,让无数人崩溃的查重,就是本题的一种应用,只是

当我们想从100万篇文档中找出相似项较高的文档对,就需要两两相互比较,一共是5千亿次,如果每次比较花费1微秒,那一共需要6天才能计算完,这肯定是不行的。

问题应用:

1、论文查重,读过大学的就都听过这个词,让无数人崩溃的查重,就是本题的一种应用,只是将一篇和上千万篇比较,但原理是一样的。

2、同源文档。我们再网站百度一些东西时,点开几个页面,可能发现很多页面及其相似,内容甚至重复,比如CSDN上的博客就有很多是从别的地方复制过来的,各个网站上的新闻等也有时候会相同或相似。如果一个网站汇总每天的新闻,那肯定是要能识别内容相似的两篇文章,选一个即可。

相似度定义:

Jaccard相似度:集合S和T的交集与集合并集大小的比率。加入S文档有三个字母A,B,C,T文档有5个字母B,C,D,E,F,那么S和T的相似度就是2除以6,三分之一。

问题处理

1、单个文档处理

步骤1——Shingling

文档一般都很长,总不能一个字符一个字符的比较,最有效的解决方法就是把整个文档拆分成短字符集合(长度为k),这样处理后如果集合中相同元素越多,那么相似度也就越高,同时还能忽略句子顺序(很多人抄论文时就经常改句子顺序)。

例:文档为abcdabd,选择k=2,那字符集合就是{ab,bc,cd,da,bd}。

当然k=2肯定是不行的,这样集合最大才是26^2,估计任何两个长文档都会认为相似。

具体k应该为多少呢?如果文档是邮件,那么k=5就够了,如果像论文这样大文档,一般k=9.

此外,文档中有很多次被称作停用词,像the,and,to等,一般是忽略这些词,因为对文章主题无作用。

步骤2——哈希

如果k=9,那么集合最大为26^9,每个元素需要9个字节来表示,而实际的集合大小是文档长度*9,现在我想把这多么元素哈希到2^32个桶中,这样每个元素就可以用4个字节来表示,这种做法的效果要比直接另k=4要好。原因是k=4时,实际集合中的元素最多为26^4,而且通常是20^4,因为像字母z,j的频率出现的次数是很低的。而9个字节的集合大小最大能达到26^9

感谢哈希算法一次。

步骤3——最小哈希

即使用4个字节的shingle,那么每篇文档难道要保存4倍的文档大小的信息?本步骤的目标就是将大集合替换成小很多的“签名”,通过计算签名集合的相似度来估计原始集合的相似的,当用50Kb的文档shingle到200Kb,而最后的签名集合只有1Kb时,最终差异值可能在几个百分点之内。

假设有M个文档集合,一共有N元素(所有集合中元素的并集,N很大),那么集合可以用一个N行M列来表示,当这个集合含这个元素时,对应位置为1,否则为0.

我们随机选择n(通常为几百)为签名大小,可以构建集合S的最小哈希签名向量[h1(r),h2(r)...hn(r)]。

步骤如下:

初始矩阵SIG(大小n*M)都为正无穷,对每行r如下处理:

(1)随机选择n个哈希函数,计算出h1(r)...hn(r).

(2)如果原N*M矩阵对应位置为0,什么都不做,如果为1,那么将SIG中新的值变为hi(r)和SIG中原值的最小值。

也就是通过N步迭代,把原来的N*M大小矩阵,变成n*M大小的矩阵(对于一个文档来说,就是N变成了n)。

这种方法能估计准确有一定的理论依据,概括为:两个集合的两个最小哈希值相等的概率等于这连个几个的相似度。

再次感谢哈希算法。

2、整体文档处理

现在文档本身不是很大,但是需要比较的文档对的数目太大。 实际中我们关注的是相似度大于某个值的文档对,这样很多相似度较低的文档对是不需要比较的。 处理方法:局部敏感哈希(LSH) 我们对目标项进行多次哈希处理,使得相似项会比不相似项更可能到同一个桶中,然后只要比较同一个桶中的文档对。哈希到同一个桶的非相似文档对成为伪正例,而真正相似的分到两个桶的为伪反例,我们希望这两个越少越好。 一种有效的方法是将上面的n*M矩阵再分为b块,每块是r行*M列,(n=br)。将每个r长的序列哈希到一个大数目范围的桶。这样矩阵缩小为b*M,对于两列来说,只要有一行在一个桶中,就是相似候选对,这种方法的准确也是很高的,关于LSH技术详细理论分析可以查看其他文献。 这种LSH技术由于在过滤阶段非相似的数据对象大部分被过滤掉,因而极大地缩短了查询计算时间,提高了效率。 再次感谢哈希。 总结 最后总结这种问题常用思路: 1、先选择k,构建shingle集合,可以再通过哈希映射成更短的桶编号。 2、计算出最小哈希签名。 3、应用LSH技术构建候选对。 每一步都用了哈希算法,复杂度一再缩小。
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Insufficient memory or disk space to repagin or print this document Word error Insufficient memory or disk space to repagin or print this document Word error Feb 19, 2024 pm 07:15 PM

This article will introduce how to solve the problem of insufficient memory or disk space to repage or print the document in Microsoft Word. This error usually occurs when users try to print a Word document. If you encounter a similar error, please refer to the suggestions provided in this article to resolve it. Insufficient memory or disk space to repage or print this document Word error How to resolve the Microsoft Word printing error "There is not enough memory or disk space to repage or print the document." Update Microsoft Office Close memory-hogging applications Change your default printer Start Word in safe mode Rename the NorMal.dotm file Save the Word file as another

How to add redline to Word document How to add redline to Word document Mar 01, 2024 am 09:40 AM

It is 395 words, which is 495. This article will show you how to add red lines in Word documents. Redlining a document refers to making modifications to the document so that users can clearly see the changes. This feature is very important when multiple people are editing a document together. What redline means Marking a document Redlining means using red lines or callouts to indicate changes, edits, or revisions to a document. The term was inspired by the practice of using a red pen to mark printed documents. Redline comments are widely used in different scenarios, such as clearly showing recommended changes to authors, editors, and reviewers when editing a document. Propose changes and modifications in legal agreements or contracts Provide constructive criticism and suggestions on papers, presentations, etc. How to give W

Can't open hyperlink in word document Can't open hyperlink in word document Feb 18, 2024 pm 06:10 PM

In recent years, with the continuous development of network technology, our lives are inseparable from various digital tools and the Internet. When processing documents, especially in writing, we often use word documents. However, sometimes we may encounter a difficult problem, that is, the hyperlink in the word document cannot be opened. This issue will be discussed below. First of all, we need to make it clear that hyperlinks refer to links added in word documents to other documents, web pages, directories, bookmarks, etc. When we click on these links, I

Learn the os.Stdout.Write function in the Go language documentation to implement standard output Learn the os.Stdout.Write function in the Go language documentation to implement standard output Nov 03, 2023 pm 03:48 PM

Learn the os.Stdout.Write function in the Go language documentation to implement standard output. In the Go language, standard output is implemented through os.Stdout. os.Stdout is a variable of type *os.File, which represents the standard output device. In order to output content to standard output, you can use the os.Stdout.Write function. This article will introduce how to use the os.Stdout.Write function to implement standard output and provide specific code examples. os.

Word document is blank when opening on Windows 11/10 Word document is blank when opening on Windows 11/10 Mar 11, 2024 am 09:34 AM

When you encounter a blank page issue when opening a Word document on a Windows 11/10 computer, you may need to perform repairs to resolve the situation. There are various sources of this problem, one of the most common being a corrupted document itself. Furthermore, corruption of Office files may also lead to similar situations. Therefore, the fixes provided in this article may be helpful to you. You can try to use some tools to repair the damaged Word document, or try to convert the document to another format and reopen it. In addition, checking whether the Office software in the system needs to be updated is also a way to solve this problem. By following these simple steps, you may be able to fix Word document blank when opening Word document on Win

Interpretation of Java documentation: Detailed introduction to the substring() method of the StringBuilder class Interpretation of Java documentation: Detailed introduction to the substring() method of the StringBuilder class Nov 03, 2023 pm 04:31 PM

Interpretation of Java documentation: Detailed introduction to the substring() method of the StringBuilder class Introduction: In Java programming, string processing is one of the most common operations. Java provides a series of classes and methods for string processing, among which the StringBuilder class is a commonly used choice for frequent string operations. In the StringBuilder class, the substring() method is a very useful method for intercepting substrings of strings. This article will

How to implement the basic usage of Workerman documents How to implement the basic usage of Workerman documents Nov 08, 2023 am 11:46 AM

Introduction to how to implement the basic usage of Workerman documents: Workerman is a high-performance PHP development framework that can help developers easily build high-concurrency network applications. This article will introduce the basic usage of Workerman, including installation and configuration, creating services and listening ports, handling client requests, etc. And give corresponding code examples. 1. Install and configure Workerman. Enter the following command on the command line to install Workerman: c

How to connect PHP to Taobao product search API documentation How to connect PHP to Taobao product search API documentation Jul 01, 2023 pm 10:16 PM

How to connect PHP to Taobao Product Search API Documentation Taobao is one of the largest e-commerce platforms in China, with a huge product inventory and user base. For developers, by connecting to Taobao's API interface, they can obtain product information, promotion activities, transactions and other functions, thereby realizing personalized business applications. This article will introduce how to use PHP language to connect to Taobao product search API to help developers quickly build their own e-commerce applications. Step 1: Register as a Taobao developer. Before starting, you need to register as a Taobao developer.

See all articles