基于编辑距离与余弦夹角的网站检索方法、装置及设备

摘要

本申请公开了一种基于编辑距离与余弦夹角的网站检索方法，由于文本向量的余弦夹角计算相对编辑距离计算速度更快，而相对编辑距离衡量文本相似度准确性更高，为了充分利用两者的优势，该方法利用K‑means方法对文本向量聚类，其中K‑means方法使用向量之间的余弦夹角作为衡量相似度的依据；当获取到检索信息之后，先确定检索信息归属的簇，再在该簇内使用编辑距离衡量簇内标题与检索信息之间的相似性，缩小了待计算的范围，提升了网站检索的实时性与准确性。此外，本申请还提供了一种基于编辑距离与余弦夹角的网站检索装置、设备及可读存储介质，其技术效果与上述方法的技术效果相对应。

说明书

技术领域

本申请涉及计算机技术领域，特别涉及一种基于编辑距离与余弦夹角的网站检索方法、装置、设备及可读存储介质。

背景技术

随着互联网飞速发展，互联网爬虫技术也日新月异。面对庞大的网站数据，首先有效的管理这些网站数据，才能挖掘出网站数据背后的价值。其中对网站标题近似度计算，实现对网站的近似检索，更是网络大数据管理的关键一步。网站检索不仅要求准确率高，而且对实时性有较高要求。

网站检索中，计算网站标题的相似度是关键步骤。当前主要基于最长公共子序列实现相似度计算。具体的，使用动态规划方法计算两个字符串的公共子序列最长长度，公共子序列越长，表示两个字符串越接近。这种计算方式得到的字符串相似度精确度较高，但是因为是通过使用动态规划方法，所以本质是一种递归的方法，需要将目标网站标题与数据库中所有网站标题两两计算最长公共子序列。因此，时间复杂度高，性能差，不能满足实时查询要求。

可见，如何提升网站检索方案的准确性和实时性，是亟待本领域技术人员解决的问题。

发明内容

本申请的目的是提供一种基于编辑距离与余弦夹角的网站检索方法、装置、设备及可读存储介质，用以解决当前网站检索方案的准确性或实时性较差的问题。其具体方案如下：

第一方面，本申请提供了一种基于编辑距离与余弦夹角的网站检索方法，包括：

以向量表示的余弦夹角作为衡量两个标题之间相似度的依据，预先采用K-means聚类算法对标题集合中的标题进行聚类，得到多个标题簇；

获取当前输入的检索信息；

确定所述检索信息归属的目标标题簇；

基于编辑距离，分别计算所述检索信息与所述目标标题簇中各个标题之间的相似度；

根据所述相似度确定目标标题，并显示所述目标标题对应的网站信息。

优选的，所述以向量表示的余弦夹角作为衡量两个标题之间相似度的依据，预先采用K-means聚类算法对标题集合中的标题进行聚类，得到多个标题簇，包括：

爬取网站标题，得到标题集合；

对所述标题集合中的各个标题进行分词，得到每个标题对应的词序列；根据所述词序列，生成标题的向量表示；

以向量表示的余弦夹角作为衡量两个标题之间相似度的依据，采用K-means聚类算法对所述标题集合中的标题进行聚类，得到多个标题簇。

优选的，所述对所述标题集合中的各个标题进行分词，得到每个标题对应的词序列；根据所述词序列，生成标题的向量表示，包括：

对所述标题集合中的各个标题进行分词，得到每个标题对应的词序列以及所述标题集合对应的词库；根据所述词序列中各个词在所述词库的出现频率，生成标题的向量表示。

优选的，所述采用K-means聚类算法对所述标题集合中的标题进行聚类，包括：

根据k值的最优经验值，采用K-means聚类算法对所述标题集合中的标题进行聚类。

优选的，所述采用K-means聚类算法对所述标题集合中的标题进行聚类，包括：

根据迭代终止条件，采用K-means聚类算法对所述标题集合中的标题进行聚类，所述迭代终止条件为达到最大迭代次数或簇中心的位移小于预设阈值。

优选的，所述确定所述检索信息归属的目标标题簇，包括：

分别计算所述检索信息与各个所述标题簇的簇中心的余弦夹角，确定余弦夹角最小的标题簇，以作为目标标题簇。

优选的，所述根据所述相似度确定目标标题，包括：

确定相似度大于相似度阈值的标题，以作为目标标题；

或者，

确定相似度最大的预设数量的标题，以作为目标标题。

第二方面，本申请提供了一种基于编辑距离与余弦夹角的网站检索装置，包括：

初步聚类模块：用于以向量表示的余弦夹角作为衡量两个标题之间相似度的依据，预先采用K-means聚类算法对标题集合中的标题进行聚类，得到多个标题簇；

检索信息获取模块：用于获取当前输入的检索信息；

归属簇确定模块：用于确定所述检索信息归属的目标标题簇；

相似度计算模块：用于基于编辑距离，分别计算所述检索信息与所述目标标题簇中各个标题之间的相似度；

检索结果输出模块：用于根据所述相似度确定目标标题，并显示所述目标标题对应的网站信息。

第三方面，本申请提供了一种基于编辑距离与余弦夹角的网站检索设备，包括：

存储器：用于存储计算机程序；

处理器：用于执行所述计算机程序，以实现如上所述的基于编辑距离与余弦夹角的网站检索方法。

第四方面，本申请提供了一种可读存储介质，所述可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时用于实现如上所述的基于编辑距离与余弦夹角的网站检索方法。

本申请所提供的一种基于编辑距离与余弦夹角的网站检索方法，包括：以向量表示的余弦夹角作为衡量两个标题之间相似度的依据，预先采用K-means聚类算法对标题集合中的标题进行聚类，得到多个标题簇；获取当前输入的检索信息；确定检索信息归属的目标标题簇；基于编辑距离，分别计算检索信息与目标标题簇中各个标题之间的相似度；根据相似度确定目标标题，并显示目标标题对应的网站信息。

可见，由于文本向量的余弦夹角计算相对编辑距离计算速度更快，而相对编辑距离衡量文本相似度准确性更高，为了充分利用两者的优势，该方法利用K-means方法对文本向量聚类，其中K-means方法使用向量之间的余弦夹角作为衡量相似度的依据；当获取到检索信息之后，先确定检索信息归属的簇，再在该簇内使用编辑距离衡量簇内标题与检索信息之间的相似性，缩小了待计算的范围，提升了网站检索的实时性与准确性。

此外，本申请还提供了一种基于编辑距离与余弦夹角的网站检索装置、设备及可读存储介质，其技术效果与上述方法的技术效果相对应，这里不再赘述。

附图说明

为了更清楚的说明本申请实施例或现有技术的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单的介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本申请所提供的一种基于编辑距离与余弦夹角的网站检索方法实施例一的实现流程图；

图2为本申请所提供的一种基于编辑距离与余弦夹角的网站检索方法实施例二的实现流程图；

图3为本申请所提供的一种基于编辑距离与余弦夹角的网站检索装置实施例的功能框图；

图4为本申请所提供的一种基于编辑距离与余弦夹角的网站检索设备实施例的结构示意图。

具体实施方式

本申请的核心是提供一种基于编辑距离与余弦夹角的网站检索方法、装置、设备及可读存储介质，充分利用基于余弦夹角和基于编辑距离的相似度计算方法，使用向量之间的余弦夹角作为衡量相似度的依据，利用K-means方法从而对标题进行聚类；当获取到检索信息之后，先确定检索信息归属的簇，再在该簇内使用编辑距离衡量簇内标题与检索信息之间的相似性，缩小了待计算的范围，提升了网站检索的实时性与准确性。

为了使本技术领域的人员更好地理解本申请方案，下面结合附图和具体实施方式对本申请作进一步的详细说明。显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

下面对本申请提供的一种基于编辑距离与余弦夹角的网站检索方法实施例一进行介绍，参见图1，实施例一包括：

S101、以向量表示的余弦夹角作为衡量两个标题之间相似度的依据，预先采用K-means聚类算法对标题集合中的标题进行聚类，得到多个标题簇；

具体的，爬取大量网站标题，得到标题集合；对标题集合中的各个标题进行分词，得到每个标题对应的词序列；根据词序列，生成标题的向量表示；以向量表示的余弦夹角作为衡量两个标题之间相似度的依据，采用K-means聚类算法对标题集合中的标题进行聚类，得到多个标题簇。

其中，在生成标题的向量表示时，可以选用词频向量。对标题集合中的各个标题进行分词，不仅仅可以得到每个标题对应的词序列，还可以得到标题集合对应的词库；然后根据词序列中各个词在词库的出现频率，生成标题的向量表示。

K-means聚类算法的迭代终止条件具体可以设置为：达到最大迭代次数或簇中心的位移小于预设阈值。

此外，作为一种具体的实施方式，可以根据k值的最优经验值，采用K-means聚类算法对标题集合中的标题进行聚类。

S102、获取当前输入的检索信息；

S103、确定检索信息归属的目标标题簇；

具体的，分别确定检索信息与各个标题簇的簇中心的相似度，将相似度最小的标题簇作为目标标题簇。当基于余弦夹角计算相似度时，上述过程具体为：分别计算检索信息与各个标题簇的簇中心的余弦夹角，确定余弦夹角最小的标题簇，以作为目标标题簇。

S104、基于编辑距离，分别计算检索信息与目标标题簇中各个标题之间的相似度；

S105、根据相似度确定目标标题，并显示目标标题对应的网站信息。

具体的，确定相似度大于相似度阈值的标题，以作为目标标题，或者，确定相似度最大的预设数量的标题，以作为目标标题。

本实施例所提供一种基于编辑距离与余弦夹角的网站检索方法，首先对标题进行文本分词，生成词频向量；基于词频向量间的余弦夹角值对全量网站标题库进行K-means聚类，其中K-means聚类的目的是缩小待比较的标题集合范围；后续在获取到检索信息之后，只需要确定检索信息归属的目标标题簇，然后将检索信息与该标题簇中的各个标题基于编辑距离进行相似度计算，最终确定目标标题。因此既能有效利用基于文本向量间余弦夹角计算的实时性，还能满足基于文本编辑距离判断相似度的准确性，最终提升网站检索的准确性和实时性。

下面开始详细介绍本申请提供的一种基于编辑距离与余弦夹角的网站检索方法实施例二，实施例二的实施过程如图2所示，主要包括以下步骤：

S201、收集互联网首页，爬取互联网首页的标题信息。

S202、将网站标题信息全量转化为数学表示向量，这里选择词频向量，具体的转化过程如下：

(1)使用中文分词工具将标题字段分词处理；

(2)去除分词中的停用词，标点符号，特殊符号；

(3)基于步骤(2)得到的分词库，分别将每个标题信息转化为词频向量。

例如网站标题1：中国科学院官方网站&北京，网站标题2:中国科学技术网站，北京。步骤(1)(2)分词后的结果分别是，标题1：中国、科学院、官方、网站、北京；标题2：中国、科学、技术、网站、北京。对应的词频向量分别是：

标题1:中国(1)科学院(1)官方(1)网站(1)北京(1)科学(0)技术(0)，

标题2:中国(1)科学院(0)官方(0)网站(1)北京(1)科学(0)技术(1)。

S203、得到了网站标题的词频向量，以词频向量的余弦夹角作为衡量两个向量相似度依据，用K-means聚类算法对相似标题聚合，具体步骤如下：

(1)选择K-means聚合类群大小，根据多次试验调优得到最优k经验值，k＝16384。

(2)随机抽取k个文本作为初始聚类簇的中心点。

(3)除了聚类中心点外其余剩余的每个标题向量，与k个中心点计算夹角余弦，夹角余弦公式如下：

由于θ变量表示两个向量之间的夹角，cosθ值越大表示两个向量之间的夹角越小，两个向量也越近似。a表示向量1，b表示向量2，n表示向量维度，x

(4)同一个聚类簇集合，使用均值更新该聚类簇的中心点，并用变量distance记录新的聚类簇与旧的聚类簇之间的位移距离。

(5)重复步骤(3)，直到聚类簇中心位移距离distance小于阈值0.1或者迭代次数达到最大阈值500。

通过k-means算法目的是利用向量计算的低时间复杂度，对全量网站标题预分类，使得近似标题都能保证在同一个聚类簇下。但是使用余弦夹角比较文本相似度有局限性，比如同义词问题，所以需要一个更加准确的衡量算法，在k-means聚类簇集合下再做准确细致计算。因此在余弦夹角的基础上又引入了基于编辑距离判断近似度。

S204、同一个聚类簇下基于编辑距离判断文本标题近似度，算法可以用公式表示：

其中，变量A

(1)网站标题A或B的长度如果是0，则直接返回另一个字符串的长度，即A和B的最少编辑距离。

(2)初始化(n+1)*(m+1)的矩阵d，并让第一行和列的值从0开始增长。

(3)扫描两字符串(n*m级的)，如果：A

(4)扫描完后，返回矩阵的最后一个值d[n][m]即是字符串A和B之间的最少编辑距离。

显而易见，编辑距离越小，表示两个字符串之间的相似度越高，可以用如下公式计算相似度：

可见，本实施例提供的一种基于编辑距离与余弦夹角的网站检索方法，首先应用计算实时性较高的文本夹角余弦衡量网站标题的相似度，基于K-means聚类算法结果，可以缩小待比较标题集合范围。因为基于文本余弦夹角本身算法的局限性，然后又用基于文本编辑距离衡量相似度提高文本作为补充，提高文本比较准确度。

从而，应用此算法对网站标题近似检索，既能有效提高检索的速度，又能提高检索的准确度。

下面对本申请实施例提供的一种基于编辑距离与余弦夹角的网站检索装置进行介绍，下文描述的一种基于编辑距离与余弦夹角的网站检索装置与上文描述的一种基于编辑距离与余弦夹角的网站检索方法可相互对应参照。

本实施例的基于编辑距离与余弦夹角的网站检索装置，如图3所示，包括：

初步聚类模块301：用于以向量表示的余弦夹角作为衡量两个标题之间相似度的依据，预先采用K-means聚类算法对标题集合中的标题进行聚类，得到多个标题簇；

检索信息获取模块302：用于获取当前输入的检索信息；

归属簇确定模块303：用于确定检索信息归属的目标标题簇；

相似度计算模块304：用于基于编辑距离，分别计算检索信息与目标标题簇中各个标题之间的相似度；

检索结果输出模块305：用于根据相似度确定目标标题，并显示目标标题对应的网站信息。

本实施例的基于编辑距离与余弦夹角的网站检索装置用于实现前述的基于编辑距离与余弦夹角的网站检索方法，因此该装置中的具体实施方式可见前文中的基于编辑距离与余弦夹角的网站检索方法的实施例部分，例如，初步聚类模块301、检索信息获取模块302、归属簇确定模块303、相似度计算模块304、检索结果输出模块305，分别用于实现上述基于编辑距离与余弦夹角的网站检索方法中步骤S101，S102，S103，S104，S105。所以，其具体实施方式可以参照相应的各个部分实施例的描述，在此不再展开介绍。

另外，由于本实施例的基于编辑距离与余弦夹角的网站检索装置用于实现前述的基于编辑距离与余弦夹角的网站检索方法，因此其作用与上述方法的作用相对应，这里不再赘述。

此外，本申请还提供了一种基于编辑距离与余弦夹角的网站检索设备，如图4所示，包括：

存储器100：用于存储计算机程序；

处理器200：用于执行所述计算机程序，以实现如上文所述的基于编辑距离与余弦夹角的网站检索方法。

最后，本申请提供了一种可读存储介质，可读存储介质上存储有计算机程序，计算机程序被处理器执行时用于实现如上文所述的基于编辑距离与余弦夹角的网站检索方法。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其它实施例的不同之处，各个实施例之间相同或相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

结合本文中所公开的实施例描述的方法或算法的步骤可以直接用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器(RAM)、内存、只读存储器(ROM)、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的存储介质中。

以上对本申请所提供的方案进行了详细介绍，本文中应用了具体个例对本申请的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本申请的方法及其核心思想；同时，对于本领域的一般技术人员，依据本申请的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本申请的限制。