算法学习与实现

多篇文章的学习内容将在文末的附录中列出。 1.算法是什么？

一段文本所包含的信息就是它的信息熵。 如果对这条信息进行无损压缩编码，理论上编码后的最短长度就是它的信息熵大小。

如果只是用来区分的话，就远远不需要那么长的编码。 任何一条信息（文本、语音、视频、图片等）都可以被映射（Hash编码）成一个不太长的随机数作为区分。 这条信息和其他信息的指纹，只要Hash算法设计得好，任何两条信息的指纹都很难重复。

该算法是2007年发表的论文《Near-for Web》中提到的指纹生成算法，用于搜索引擎网页去重的工作中。

简单来说，算法的主要工作就是对文本进行降维，生成一个值，也就是论文中提到的“指纹”。 通过比较不同文本的值，然后比较汉明距离，就可以判断两个文本的相似度。 花费。

对于文本去重问题，常见的解决方案有余弦算法、欧氏距离、相似度、最长公共子串等方法。 然而，这些方法无法有效地处理海量数据。

例如，在搜索引擎中，会出现很多相似的关键词。 用户需要获取的内容类似，但搜索关键词不同，比如“北京好吃的火锅”和“北京哪家店火锅好吃”是两个等价的关键词。 然而，通过普通的哈希计算，会生成两个截然不同的哈希字符串。 计算出的Hash字符串会非常相似，因此可以判断两个文本的相似度。

以下是查看值的示例

from simhash import Simhash
def get_Features(s):
    '''
    设置一个长度为3的滑动窗口，并只匹配数字英文加下划线，如输入'你好啊，今天真高兴':
    返回['你好啊', '好啊今', '啊今天', '今天真', '天真高', '真高兴']
    '''
    width = 3
    s = s.lower()#字符小写处理
    s = re.sub(r'[^\w]+','',s)#删除非下划线或单词的字符
    return [s[i:i + width] for i in range(max(len(s) -width + 1,1))]
    
print(get_Features('How are you? I am fine. Thanks.'))
'''
['how', 'owa', 'war', 'are', 'rey', 'eyo', 'you', 'oui', 'uia', 
 'iam', 'amf', 'mfi', 'fin', 'ine', 'net', 'eth', 'tha', 'han', 'ank', 'nks']
'''
print('%x' % Simhash(get_Features('How are you? I am fine. Thanks.')).value)
print('%x' % Simhash(get_Features('How are you? I am fine.      Thanks.')).value)
print('%x' % Simhash(get_Features('How r you? I       am fine. Thanks.')).value)
'''
\w :匹配包括下划线的任何单词字符,等价于 [A-Z a-z 0-9_]
\W :匹配任何非单词字符,等价于 [^A-Z a-z 0-9_]
%x ：16进制打印
'''
'''
E:\JP\LearnCoding\simhash_learn>python search_simhash.py
4d4da690b5a57e47
4d4da690b5a57e47
由于进行了正则替换掉所有非单词下划线的字符，所以，字符串空格的存在导致的不同不会影响最终结果
文字的顺序会影响结果
4f08a4f4b5a13a4b
'''

2.算法思维

假设我们有大量的文本数据，我们需要根据文本内容进行去重。 对于文本去重，目前有很多NLP相关的算法可以高精度地解决问题，但我们现在处理的是大数据维度的文本去重，这对算法的效率提出了很高的要求。

局部敏感哈希算法可以将原始文本内容映射为数字（哈希签名），相对相似的文本内容对应的哈希签名也相对相似。 该算法是该公司用于海量网页去重的高效算法。 它将原文映射为64位的二进制数字串，然后通过比较二进制数字串的差异来表达原文内容的差异。

它是一种局部敏感度（哈希）。 主要思想是降维，将高维特征向量映射为f位指纹（），通过比较两篇文章的f位指纹来判断文章是否重复。 或者高度近似。 汉明距离越小，相似度越低（根据Near-for Web论文）。 一般来说，汉明距离为3意味着两个文章是相同的。 。 为了描述方便，假设输入是文档的特征集，每个特征都有一定的权重。 例如，特征可以是文档中的单词，其权重可以是该单词出现的次数。

3. 算法流程

分词→哈希→加权→合并→降维

3.1 分词 3.1.1 短文本处理

直接分词并计算所有词

将需要评判的文本分割成词，形成本文的特征词。

def get_cibiao(Inp,Outp):
    '''
    获得文件的所有不重复的词，存入新的文件
    '''
    f=open(Inp,encoding="utf-8",errors="ignore")
    o=open(Outp,"w")
    for line in f:
        line=line.strip()
        ciyu=jieba.cut(line,cut_all=False)
	……省略使用部分的代码

3.1.2 长文本处理——基于TF-IDF的文本关键词提取方法

这部分主要是指中文文本关键词提取的三种方法——以及TF-IDF算法的介绍与实现

用每篇文章抽取若干个关键词（例如20个），合并成一个集合，计算每篇文章对于这个集合中的单词的词频（为了避免文章长度的差异，可以使用相对词频）；

如果您只是使用这样的算法的实现，则这部分可以省略。 毕竟这个计算过程好像已经被封装在库中了（大概就是这么称呼的）。

3.1.2.1 TF-IDF算法思想词频（Term，TF）

指给定单词在当前文档中出现的频率。 由于同一个单词在长文件中的词频可能比短文件中更高，因此需要根据文件的长度对给定单词进行归一化，即给定单词出现的次数除以总数当前文件中的单词数。

逆文件频率 ( , IDF)

是一个词的一般重要性的衡量标准。 也就是说，如果一个词只出现在少数文档中，则意味着它更能代表文档的主旨，其权重会更大； 如果一个词出现在大量文档中，则说明不清楚该内容代表什么，其权重就会较小。 它应该很小。 可以通过将文档总数除以包含该单词的文档数，然后取商的对数来获得。

TF-IDF（词项 - ，词频 - 逆文档频率）

它是信息检索（ ）和文本挖掘（ 文本 ）常用的加权技术。

它是一种统计方法，用于评估单词对于文档集或语料库中的文档的重要性。 单词的重要性与它在文档中出现的次数成正比增加，但同时与它在语料库中出现的频率成反比降低。

TF-IDF的主要思想是

如果某个词在一篇文章中出现频率较高，而在其他文章中出现频率较低，则认为该词更能代表当前文章的含义。 也就是说，一个词的重要性与它在文档中出现的次数成正比，与它在语料库中的文档中出现的频率成反比。

3.1.2.2 TF-IDF文本关键词提取方法流程

从上面可以看出，TF-IDF对文本中所有候选关键词进行加权，并根据权重对关键词进行排序。 假设Dn为测试语料库的大小，则该算法的关键词提取步骤如下：

(1)对于给定的文本D，进行分词、词性标注、去除停用词等数据预处理操作。 这部分采用口吃分词，保留词性词'n'、'nz'、'v'、'vd'、'vn'、'l'、'a'、'd'，最终得到n候选关键词，即D=[t1,t2,…,tn]；

(2)计算文本D中单词ti的词频；

（3）计算单词ti在整个语料中的IDF=log(Dn/(Dt+1))，其中Dt是语料中单词ti出现的文档数量；

（4）计算单词ti的TF-IDF=TF*IDF，重复（2）-（4）得到所有候选关键词的TF-IDF值；

(5)将候选关键词的计算结果倒序排列，得到前N个词作为文本关键词。

3.1.2.3 代码实现（待修改/实现）

第三方工具包-learn提供了TFIDF算法相关的函数。 本文主要使用..text下的and函数。 其中，该函数用于构造语料库中的词频矩阵，该函数用于计算单词的tfidf权重。

注：()函数只有一个参数，默认值为True。 如果设置为False，则IDF的计算公式为idf=log(Dn /Dt) + 1。

基于TF-IDF方法进行文本关键词提取的代码执行步骤如下：

(1)读取样本源文件.csv；

(2) 获取每行记录的标题和摘要字段，并拼接这两个字段；

（3）加载自定义停用词列表.txt，并对拼接后的文本进行数据预处理操作，包括分词、过滤掉与词性匹配的词、去除停用词、拼接成以空格分隔的文本；

(4) 遍历文本记录，并将预处理后的文本放入文档集中；

(5) 使用()函数得到词频矩阵，a[j][i]表示第i篇文档中第j个词的词频；

(6)使用()函数计算每个词的tf-idf权重；

(7) 获取词袋模型中的关键词以及对应的tf-idf矩阵；

(8) 遍历tf-idf矩阵，打印每个文档的词汇表和对应的权重；

(9) 对于每个文档，按照词权值降序排列，选取前N个词作为文本关键词，写入数据框中；

(10) 将最终结果写入.csv文件中。

看了很多大佬的代码，这个简单的还是适合我的。 我不需要要求详细的解释，只需要使用它即可。

Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 23:11:46) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>> import jieba.analyse
>>> corpus ='逆向文件频率（Inverse Document Frequency，IDF）是一个词语普遍重要性的度量。即如果一个词语只在很少的文件中出现，表示更能代表文件的主旨，它的权重也就越大；如果一个词在大量文件中都出现，表示不清楚代表什么内容，它的权重就应该小。'
>>> keywords_textrank = jieba.analyse.textrank(corpus)
Building prefix dict from the default dictionary ...
Dumping model to file cache C:…………………………………………………………（此处是文件地址）
Loading model cost 0.704 seconds.
Prefix dict has been built successfully.
>>> print(keywords_textrank)
['文件', '表示', '代表', '出现', '权重', '重要性', '词语', '度量', '主旨', '内容', '频率', '逆向', '应该', '大量文件']
>>> keywords_tfidf = jieba.analyse.extract_tags(corpus)
>>> print(keywords_tfidf)
['文件', '词语', '权重', '大量文件', 'Inverse', 'Document', 'Frequency', 'IDF', '代表', '逆向', '主旨', '度量', '更能', '一个', '如果', '表示', '出现', '重要性', '频率', '很少']
>>> 
jieba.analyse.extract_tags(sentence, topK=20, withWeight=False, allowPOS=())
>>>sentence 为待提取的文本
>>>topK 为返回几个 TF/IDF 权重最大的关键词，默认值为 20
>>>withWeight 为是否一并返回关键词权重值，默认值为 False
>>>allowPOS 仅包括指定词性的词，默认值为空，即不筛选

3.2 哈希

每个单词通过哈希算法变成一个哈希值（请参考哈希算法总结）。

例如，使用哈希算法计算出“美国”，使用哈希算法计算出“51区”。

这样我们的字符串就变成了一串数字。 请记住我在文章开头所说的。 只有将文章转化为数值计算，才能提高相似度计算的性能。 现在是进行降维过程的时候了。

学姐说：计算机中存储的任何数据都是数字，更准确地说是二进制值。 计算机行业有句话叫“一切源于比特”。

3.3 加权

结果是通过2步哈希生成的，需要根据单词的权重形成加权数字串。

W=哈希*

具体计算过程如下：为1的哈希二进制串乘以特征词的分词权重，为0的二进制串乘以特征词的分词权重然后负，然后得到权重向量。

例如“美国”的哈希值为“”，加权计算为“4 -4 -4 4 -4 4”； “51区”的哈希值为“”，加权计算为“5 -5 5 -5 5 5”。

我们假设权重分为5个级别（1~5）。 例如：

《美国“51区”员工称里面有9个飞碟，还看到灰色外星人》

==> 分词后是

“美国（4）51区（5）雇员（3）说（1）里面（2）有（1）9个（3）飞碟（5）有（1）看到（3）灰色（4）外星人(5)”,

括号表示该词在整个句子中的重要性。 数字越大，越重要。

3.4 合并

将上面为每个单词计算的序列值累加起来，仅形成一个序列字符串。

例如，“美洲”中的“4 -4 -4 4 -4 4”，“51区”中的“5 -5 5 -5 5 5”，将每个数字相加，“4+5 -4±5 -4” +5 4±5 -4+5 4+5”

==》“9 -9 1 -1 1 9”。

这里以仅计算两个单词为例。 实际计算需要累加所有单词的序列串。

3.5 降维

取4步计算出来的“9 -9 1 -1 1 9”，大于0则位置1，小于等于0则位置0，我们就可以得到文本的值并转成一串 0 1 组成我们最终的签名。

每一位大于0则记录为1，小于0则记录为0。

最终计算结果为：“1 0 1 0 1 1”。

整个流程的流程图原作者给出了下图：

4. 签名距离计算

我们将库中的文本全部转为签名，转为long类型存储，这样就大大减少了空间。

既然我们解决了空间问题，那么我们如何计算两者之间的相似度呢？ 是为了比较两个01之间有多少差异吗？

是的，事实确实如此。 我们可以通过汉明距离来计算两个对象是否相似。 两个对应的二进制数字（01串）的不同值的个数称为两者的汉明距离。 示例如下：

10101和00110从第一位开始第一、四、五位不同，则汉明距离为3。

对于二进制串a和b，汉明距离等于XOR b异或运算结果中1的个数（通用算法）。

计算两个值之间的距离

from simhash import Simhash
hash1 = Simhash(u'i am very happy'.split())
hash2 = Simhash(u'i am very sad'.split())
print('hash1',hash1)
print('hash2',hash2)
print('hash1.distance(hash2):',hash1.distance(hash2))
--结果
hash1 <simhash.Simhash object at 0x0000012E64607710>
hash2 <simhash.Simhash object at 0x0000012E646077F0>
hash1.distance(hash2): 8

4.1 什么是汉明距离？

简单来说，汉明距离（·）可以理解为两个二进制串之间同一位置的差异个数。

例如，[1, 1, 1, 0, 0, 0] 和 [1, 1, 1, 1, 1, 1] 之间的汉明距离为 3。

在处理大规模数据时，我们一般使用64位数据，可以用long类型来存储。 在这种情况下，如果汉明距离在 3 以内，则可以认为两个文本相似。

4.2 大规模数据下的汉明距离计算

在数据量规模较大的情况下，如果通过位比较的方法计算两个文本的64位汉明距离来查找汉明距离小于等于3的文本，这会消耗大量的时间，并且资源。

这时就有了更好的办法来平衡计算汉明距离的时间复杂度和空间复杂度。 具体计算思路如下：

将 64 位数据分为四部分。 如果两个零件相似（汉明距离小于或等于3），根据鸽巢原理（一般称为抽屉原理（数学原理）），其中一个零件一定是完全相同的。

这样，我们就可以通过部分比较来快速找出两个文本是否相似。 【可以简化理解为有四个部分，并且不同部分的数量少于三个，也就是说其中一个必须与另一个完全相同】

参考本节

贮存：

1. 将 64 位签名拆分为 4 个 16 位二进制代码。 （图中红色的16位）

2、用4个16位二进制码查找当前对应位置是否有元素。 （放大16位）

3、如果对应位置没有元素，则直接追加到链表中； 如果对应位置有元素，则直接追加到链表末尾。 （图中S1——SN）

寻找：

1、将需要比较的签名分割成4个16位二进制码。

2. 分别取出四个16位二进制码，查找集合中相应位置是否存在元素。

3、如果有元素，则取出链表，依次查找比较，直到值小于一定大小，整个过程完成。

原则：

从算法中学习找到可以哈希的键值，因为我们使用的是本地敏感哈希。 该算法的特点是只要相似的字符串只有个别数字有差异变化即可。 这样，我们就可以推断出两个相似的文本至少有 16 位的共同点。 具体选择 16 位、8 位或 4 位。 您可以根据自己的数据测试来选择。 虽然比较的位数越小，就越准确，但空间也会变大。 分成4个16位段的存储空间是单独存储空间的4倍。之前5000w数据计算出来是382Mb，扩容4倍大约是1.5G，可以接受。

5、大规模文本去重

这部分内容主要参考文章。

这里的大规模文本需要去重的时候可能有两种情况：

作为新手，我在删除重复文本时的第一个想法是将它们两两进行比较。 看似非常简单明了，但我面临着一个非常重要的问题：时间。 减肥时我们能承受多少时间成本？

通过调用该库，我们可以轻松计算文本值并在不同文本之间进行成对比较，如下：

import jieba.analyse
from simhash import Simhash
#通过对上述两个库的引用，我们就已经可以完成文本的两两比对了。
……（过程省略）
with open(Outp,'a', encoding='gbk') as o:
     hash1 = Simhash(line1.split())
     hash2 = Simhash(line2.split())
     print('f1:{} 与 f2:{}的海明距离是：{}'.format(fr1[66:],fr2[66:],str(hash1.distance(hash2))),file=o)
     if hash1.distance(hash2) <= 3:
          print('文本相似')
     else:
          print('文本不相似')
            

如果文档只有几个，通过这样的流程处理起来是非常快的。 至少对于我的需求来说，这个处理后的时间长短没有影响。 然而，当我们放大文档数量时，比如2698个文件的两两比较，就意味着计算机会比较超过300万次。 小小的笔记本承受着它的尺寸不该有的负担。 已经运行了近5个小时。

那么摆在我们面前的是：如何去重==》如何高效去重==》如何高效比较文件

文章作者提到，高效去重、降低时间复杂度的关键是尽量将潜在相似的文本聚合在一起，从而大大缩小比较的范围。

那就是减少计算机的工作量，让它少做一些工作。

5.1 首次抽搐试验

看完大佬文章的第一段，我突然想到：

设置一个篇章可能具有的行数
按行读取文件
	将每行的内容添加到列表
	如果目前列表的元素数大于行数，并且新的一行的具有篇章的初始标记：
		获得一个完整的篇章内容
		取得其Simhsah值
		将列表存入字典
		建立索引
		如果列表的simhash值未找到相似，说明是不重复文本
		如果有相似，说明是重复文本。

直到我开始写这一段，程序果然还是没有运行完。 因为我没有在减少运行时间上下功夫，最终学会了一种简单的单文本去重方法。 虽然比较还是基于两两比较的思想，但是我觉得这可能是当我们尝试合法的抓取网页内容的时候，如果我不知道其他的方法，这可能会帮助我抓取网页页面以删除重复项。

也许我只是在愚弄你。 我应该使用一个不太大的文件，并且必须有重复的文件来测试。 我不想在运行中途将其关闭。 我必须等待明天的结果。

虽然还没有运行完，但是我确定这个想法是有效的，但是我的代码有问题。 因为是局部敏感的，所以从之前的测试中我们可以发现，微小的变化都会带来汉明距离的变化。 我试图比较的文本重复了段落，标题也不一致，因此可能需要更改一些内容。

参考文章