Wnma's Blogs
0%

杂记

发表于 更新于 分类于

SimHash算法是一种用于计算文档相似度的算法，可以通过计算文本的SimHash值来比较文档间的汉明距离，从而比较文档间的相似度。本文介绍了SimHash算法的基本原理和实现步骤，并介绍了中文分词方法和不同类型的分词算法。同时，还对损失函数、汉明距离、hash函数、频率与频度、互现信息等关键概念进行了详细解释，有助于读者深入了解SimHash算法背后的技术原理。

SimHash算法原理

SimHash是用来计算文档之间的相似度。通过该算法计算每篇文档的 SimHash值，通过计算得到的二进制来比较文档间的汉明距离，进而来比较文档间的相似度。

步骤：

  1. 分词

    对一段文本进行切割，得到有效的特征向量（词）。为每个特征向量设置对应的权值（1-5），权值越高则代表这个特征向量在文本中越重要。

  2. hash

    利用 hash函数计算各个特征向量的 hash值。hash函数

  3. 加权

    在 hash之后，对每个特征向量进行加权，即W = Hash * Weight

  4. 合并

    在对每个特征向量加权后，再累加，变成一个序列串。

  5. 降维

    由于最后合并的数字可能过大（过小），设定一个阈值，大于某阈值的设置为1，小于某阈值的设置为0。有很多降维处理的操作，这里只是简单举个例子

举例：

文本：人生苦短，我用Python

  1. 分词。

  2. hash。

  3. 加权。遇到0就变为负数

  4. 合并。对应位加和。

  5. 降维。大于0的设置为1，否则为0。

    1
    2
    3
    4
    5
    6
    7
    8
    分词	  hash				加权 			合并			 降维

    生(5)  人生("10101")	  	5 -5 5 -5 5	  5+5+4+3-3-3-2=9 	1
    ython(5)  Python("11101")	5 5 5 -5 5	   -5+5-4-3-3-3-2=-15	0
    (4) 	 苦("10110")		  4 -4 4 4 -4	 5+5+4+3+3-3-2=15	  1
    (3)	 短("00101")		 3 -3 3 3 -3	 -5-5+4+3-3-3+2=-7	 0
    (3)	 我("00001")		 -3 -3 3 -3 3	 5+5-4-3+3+3-2=7	1
    (2)  	 用("00010")		 -2 -2 -2 2 -2

    中文分词方法

基于规则的分词方法

机械分词、基于字典。按照一定的策略在一个词典中的词条进行匹配，若找到某词条则匹配成功。

三要素：

  • 分词词典

  • 文本扫描顺序

    • 正向扫描
    • 逆向扫描
    • 双向扫描

  • 匹配原则

    • 最大匹配（MM）

      假定词典中的最长词条所含汉字个数为i，则被处理文本中前i个字符作为匹配字段，查找词典。如果词典中含有这样i个汉字个数的词，则匹配成功，并且切分出这个词；如果找不到就匹配失败，将匹配字段去掉最后一个汉字，继续匹配，直到匹配成功为止。统计方法表明，错误率为1/169。

    • 最小匹配（逆向最大匹配，RMM）。与MM方法相同，只不过是从文本末尾开始，匹配失败就去掉前一个汉字。错误率为1/245。

    • 逐词匹配。将词典中的词由长到短逐词遍历，直到文本切分完成。

    • 最佳匹配（OM）

      在词典中按词频的大小顺序排列词条，缩短检索时间，降低时间复杂度，加快分词速度。不算是一种分词方法，只是一种对分词词典的一种组织方式。OM 法的分词词典每条词的前面必须有指明长度的数据项，所以其空间复杂度有所增加，对提高分词精度没有影响，分词处理的时间复杂度有所降低。

基于统计的分词方法

基本思想：词是稳定的组合。

上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。

字与字相邻出现的概率或频率反应出词的可信度。

无字典分词：统计文本中相邻字的组合的频度，计算它们之间的互现信息。

该方法所应用的主要的统计模型有：N 元文法模型（N-gram）、隐马尔可夫模型（Hiden Markov Model，HMM）、最大熵模型（ME）、条件随机场模型（Conditional Random Fields，CRF）等。

在实际应用中此类分词算法一般是将其与基于词典的分词方法结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。

基于语义的分词方法

语义分析。对自然语言自身的语言信息进行更多的处理。

  • 扩充转移网络法

    有限状态机。有限状态机只能识别正则语言，对有限状态机作的第一次扩充使其具有递归能力，形成递归转移网络 （RTN）。在RTN 中，弧线上的标志不仅可以是终极符（语言中的单词）或非终极符（词类），还可以调用另外的子网络名字分非终极符（如字或字串的成词条件）。这样，计算机在 运行某个子网络时，就可以调用另外的子网络，还可以递归调用。词法扩充转移网络的使用， 使分词处理和语言理解的句法处理阶段交互成为可能，并且有效地解决了汉语分词的歧义。

  • 知识分词语义分析法

  • 邻接约束法

  • 综合匹配法

  • 后缀分词法

  • 特征词库法

  • 矩阵约束法

    先建立一个语法约束矩阵和一个语义约束矩阵， 其中元素分别表明具有某词性的词和具有另一词性的词相邻是否符合语法规则， 属于某语义类的词和属于另一词义类的词相邻是否符合逻辑，机器在切分时以之约束分词结果。

  • 语法分析法

  • ……

基于理解的分词方法

通过让计算机模拟人对句子的理解，达到识别词的效果。这种分词方法需要使用大量的语言知识和信息。

基本思想：在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。

  • 分词子系统
  • 句法语义子系统
  • 总控部分

在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。

主要的方法：

  • 专家系统分词法

    从专家系统角度把分词的知识（包括常识性分词知识与消除歧义切分的启发性知识即歧义切分规则）从实现分词过程的推理机中独立出来，使知识库的维护与推理机的实现互不干扰，从而使知识库易于维护和管理。它还具有发现交集歧义字段和多义组合歧义字段的能力和一定的自学习功能。

  • 神经网络分词法

    该方法是模拟人脑并行，分布处理和建立数值计算模型工作的。它将分词知识所分散隐式的方法存入神经网络内部，通过自学习和训练修改内部权值，以达到正确的分词结果，最后给出神经网络自动分词结果，如使用 LSTM、GRU 等神经网络模型等。

  • 神经网络专家系统集成式分词法

    该方法首先启动神经网络进行分词，当神经网络对新出现的词不能给出准确切分时，激活专家系统进行分析判断，依据知识库进行推理，得出初步分析，并启动学习机制对神经网络进行训练。该方法可以较充分发挥神经网络与专家系统二者优势，进一步提高分词效率。

损失函数

损失函数整理

补充

汉明距离

在信息论中，两个等长字符串之间的汉明距离（Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。

汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。

hash函数

hash（散列、杂凑）函数，是将任意长度的数据映射到有限长度的域上。直观解释起来，就是对一串数据m进行杂糅，输出另一段固定长度的数据h，作为这段数据的特征（指纹）。

频率与频度

频率：一定时间（一分钟，一秒，一小时）内，某动作的次数（某事物出现的次数）。

频度：即时间频度。一个算法执行所耗费的时间。一个算法中的语句执行次数称为语句频度或时间频度。

互现信息

互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可以认为此字组可能构成了一个词。