文本比较算法Ⅲ——计算文本的相似度

简介:

在“文本比较算法Ⅰ——LD算法”中,介绍了编辑距离的计算。

  在“文本比较算法Ⅱ——Needleman/Wunsch算法”中,介绍了最长公共子串的计算。

  在给定的字符串A和字符串B,LD(A,B)表示编辑距离,LCS(A,B)表示最长公共子串的长度。

  如何来度量它们之间的相似度呢?

  不妨设S(A,B)来表示字符串A和字符串B的相似度。那么,比较合理的相似度应该满足下列性质。

  性质一:0≤S(A,B)≤100%,0表示完全不相似,100%表示完全相等

  性质二:S(A,B)=S(B,A)

  目前,网上介绍的各种相似度的计算,都有各自的不尽合理的地方。

  计算公式一:S(A,B)=1/(LD(A,B)+1)

    能完美的满足性质二。

    当LD(A,B)=0时,S(A,B)=100%,不过无论LD(A,B)取任何值,S(A,B)>0,不能满足性质一。

 

  计算公式二:S(A,B)=1-LD(A,B)/Len(A)

    当Len(B)>Len(A)时,S(A,B)<0。不满足性质一。

    有人会说,当S(A,B)<0时,强制指定S(A,B)=0就解决问题了。

    问题是,S(A,B)=1-LD(A,B)/Len(A),而S(B,A)=1-LD(B,A)/Len(B)。当Len(A)≠Len(B)时,S(A,B)≠S(B,A)。不满足性质二

    还有一个例子可以说明问题

    A="BC",B="CD",C="EF"

    S(A,B)=1-LD(A,B)/Len(A)=1-2/2=0

    S(A,C)=1-LD(A,C)/Len(A)=1-2/2=0

    A和B的相似度与A和C的相似度是一样的。不过很明显的是B比C更接近A

 

  计算公式三:S(A,B)=LCS(A,B)/Len(A)

    这个公式能完美的满足的性质一

    不过当Len(A)≠Len(B)时,S(A,B)≠S(B,A)。不满足性质二

    用一个例子说明问题

    A="BC",B="BCD",C="BCEF"

    S(A,B)=LCS(A,B)/Len(A)=2/2=100%

    S(A,C)=LCS(A,C)/Len(A)=2/2=100%

    A和B的相似度与A和C的相似度是一样的。不过很明显的是B比C更接近A

 

  上面是网上能找到的三个计算公式,从上面的分析来看都有各自的局限性。

 

  我们看一个例子:

  A=GGATCGA,B=GAATTCAGTTA,LD(A,B)=5,LCS(A,B)=6

  他们的匹配为:

    A:GGA_TC_G__A

    B:GAATTCAGTTA

  可以看出上面蓝色的部分表示的是LCS部分,黑色表示的是LD部分。

  因此,给出一个新的公式

  S(A,B)=LCS(A,B)/(LD(A,B)+LCS(A,B))

  这个公式能解决上述三个公式的种种不足。

  而LD(A,B)+LCS(A,B)表示两个字符串A、B的最佳匹配字串的长度。这个是唯一的。

  还有注意的是LD(A,B)+LCS(A,B)和Max(Len(A),Len(B))这两个并不完全相等。

 

  

 

     本文转自万仓一黍博客园博客,原文链接:http://www.cnblogs.com/grenet/archive/2010/06/04/1751147.html,如需转载请自行联系原作者


相关文章
|
4月前
|
算法 JavaScript 数据安全/隐私保护
基于GA遗传优化的最优阈值计算认知异构网络(CHN)能量检测算法matlab仿真
本内容介绍了一种基于GA遗传优化的阈值计算方法在认知异构网络(CHN)中的应用。通过Matlab2022a实现算法,完整代码含中文注释与操作视频。能量检测算法用于感知主用户信号,其性能依赖检测阈值。传统固定阈值方法易受噪声影响,而GA算法通过模拟生物进化,在复杂环境中自动优化阈值,提高频谱感知准确性,增强CHN的通信效率与资源利用率。预览效果无水印,核心程序部分展示,适合研究频谱感知与优化算法的学者参考。
|
6月前
|
算法 数据安全/隐私保护
基于Big-Bang-Big-Crunch(BBBC)算法的目标函数最小值计算matlab仿真
该程序基于Big-Bang-Big-Crunch (BBBC)算法,在MATLAB2022A中实现目标函数最小值的计算与仿真。通过模拟宇宙大爆炸和大收缩过程,算法在解空间中搜索最优解。程序初始化随机解集,经过扩张和收缩阶段逐步逼近全局最优解,并记录每次迭代的最佳适应度。最终输出最佳解及其对应的目标函数最小值,并绘制收敛曲线展示优化过程。 核心代码实现了主循环、粒子位置更新、适应度评估及最优解更新等功能。程序运行后无水印,提供清晰的结果展示。
126 14
|
11月前
|
存储 分布式计算 算法
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
大数据-106 Spark Graph X 计算学习 案例:1图的基本计算、2连通图算法、3寻找相同的用户
178 0
|
11月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
225 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
12月前
|
机器学习/深度学习 存储 人工智能
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计
使用Python作为开发语言,基于文本数据集(一个积极的xls文本格式和一个消极的xls文本格式文件),使用Word2vec对文本进行处理。通过支持向量机SVM算法训练情绪分类模型。实现对文本消极情感和文本积极情感的识别。并基于Django框架开发网页平台实现对用户的可视化操作和数据存储。
274 0
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计
|
算法 数据可视化 数据安全/隐私保护
基于LK光流提取算法的图像序列晃动程度计算matlab仿真
该算法基于Lucas-Kanade光流方法,用于计算图像序列的晃动程度。通过计算相邻帧间的光流场并定义晃动程度指标(如RMS),可量化图像晃动。此版本适用于Matlab 2022a,提供详细中文注释与操作视频。完整代码无水印。
|
12月前
|
算法 C++
如何精确计算出一个算法的CPU运行时间?
如何精确计算出一个算法的CPU运行时间?
|
12天前
|
机器学习/深度学习 算法 新能源
【优化调度】基于matlab粒子群算法求解水火电经济调度优化问题研究(Matlab代码实现)
【优化调度】基于matlab粒子群算法求解水火电经济调度优化问题研究(Matlab代码实现)
|
14天前
|
算法 机器人 定位技术
基于机器视觉和Dijkstra算法的平面建筑群地图路线规划matlab仿真
本程序基于机器视觉与Dijkstra算法,实现平面建筑群地图的路径规划。通过MATLAB 2022A读取地图图像,识别障碍物并进行路径搜索,支持鼠标选择起点与终点,最终显示最优路径及长度,适用于智能导航与机器人路径规划场景。
|
15天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的XGBoost时间序列预测算法matlab仿真
本程序基于Matlab 2024b实现,结合粒子群优化(PSO)与XGBoost算法,用于时间序列预测。通过PSO优化XGBoost超参数,提升预测精度。程序包含完整注释与操作视频,运行后生成预测效果图及性能评估指标RMSE。

热门文章

最新文章