没有合适的资源?快使用搜索试试~ 我知道了~
首页优化算法:高效求解最长循环公共子序列
"求解最长循环公共子序列问题的两个算法" 本文主要探讨的是如何高效地解决最长循环公共子序列(LCCS)问题,这是在文本相似度计算中一个重要概念。LCCS是指两个字符串在所有可能的循环移位操作下能够得到的最长公共子序列。传统的穷举方法在处理这个问题时效率低下,因此,文章提出了两种新的算法来优化这一过程。 首先,论文证明了循环移位操作对于两个字符串之间LCS(最长公共子序列)长度增量的影响有明确的上下界。通过这个理论基础,作者给出了最优移位量的必要条件,从而有效地减少了枚举候选移位量的次数。这种筛选策略降低了计算复杂性,提高了求解LCCS的效率。 接着,文章构建了一个迭代方法来进一步减少无效的候选移位量。该方法仅需少数次迭代就可以剔除大部分不满足条件的移位,显著提升了计算速度。 此外,为了在更短的时间内估算LCCS的长度,作者还提出了一种近似算法,其时间复杂度为O(mn),其中m和n分别代表两个字符串的长度。这个近似算法在保持一定精度的同时,极大地提高了计算效率。 通过大量的随机模拟实验,作者发现当两个字符串的相似度显著高于随机字符串的相似度时,所提出的这两种算法表现出了良好的性能。这表明它们在实际应用中,尤其是在文本相似度比较或数据匹配等场景下,具有较高的实用价值。 文章的贡献在于为LCCS问题提供了新的算法思路,不仅优化了计算效率,而且在特定条件下能准确估算LCCS长度。这些成果对于处理大规模文本数据或在有限计算资源下进行文本相似度分析具有重要的理论与实践意义。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/18271027/bg1.jpg)
收稿日期:20190626;修回日期:20190809 基金项目:国家自然科学基金青年项目(11702046);重庆市教委科学研究项目(KJ1600910)
作者简介:郑子君(1985),男(通信作者),重庆万州人,副教授,硕导,博士,主要研究方向为计算力学、岩土力学(zhengzj@cqut.edu.cn);
王洪(1997),男,重庆人,硕士研究生;余成(1984),男,重庆人,副教授,硕导,博士,主要研究方向为岩土力学、交通工程.
求解最长循环公共子序列问题的两个算法
郑子君
1
,王 洪
1
,余 成
2
(1.重庆理工大学 机械工程学院,重庆 400054;2.重庆交通大学 河海学院,重庆 400074)
摘 要:最长循环公共子序列(LCCS)是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列
(LCS)。针对穷举移位量求解 LCCS效率过低的问题,设法对候选移位量进行筛选。通过证明循环移位操作对
两字符串间
LCS长度增量影响的上下限,得到最优移位量的必要条件,从而减小了求解 LCCS的枚举量;在此基
础上,建立了求解
LCCS的迭代方法,只经过少数几次迭代便可消除绝大部分无效候选移位量;此外,还提出一
个可在 O(mn)时间复杂度下快速估算 LCCS长度的近似算法。大量随机模拟表明,当两字符串间的相似度明显
高于随机字符串的相似度时,提出的两种算法表现良好。
关键词:最长公共子序列;循环字符串;文本相似度;动态规划
中图分类号:TP301.6 文献标志码:A 文章编号:10013695(2020)11027333404
doi:10.19734/j.issn.10013695.2019.06.0258
Twoalgorithmstosolvelongestcircularcommonsubsequenceproblems
ZhengZijun
1
,WangHong
1
,YuCheng
2
(1.CollegeofMechanicalEngineering,ChongqingUniversityofTechnology,Chongqing400054,China;2.CollegeofHehai, Chongqing
JiaotongUniversity
,Chongqing400074,China)
Abstract:Longestcommoncircularsubsequence(LCCS)isthelongestcommonsubsequence(LCS)oftwostringswithany
possiblecircularshifting.FindingtheLCSforeverypossiblecircularshiftingmountisthesimplestapproachtosolveLCCS
problem
,butitisveryinefficient.Thispaperestablishedanecessaryconditionfortheoptimumshiftingamountbyestimating
theupperandlowerboundsoftheLCSlengthincrementafteracircularshifting,andthusestablishedaniterativefilteringalgo
rithmtosolveLCCSproblem.Thisalgorithmcouldeliminatemostoftheinvalidcandidatesinseveraliterationaccordingtothe
tests.Thispaperprovidedanapproximatealgorithm estimatethelengthofLCCSevenfaster,whichworkedwithatimecom
plexityofO(mn).Stochastictestsshowthatbothproposedalgorithmsworkverywellifthesimilaritybetweenthegivenstrings
issufficientlyhigherthanthatbetweentworandomstrings.
Keywords:longestcommonsubsequence(LCS);circularstring;textsimilarity;dynamicprogramming
0 引言
字符串之间相似度的比较在多个场景都有应用,例如文本
代码比较
[1~3]
、抄 袭 检 测
[4]
、自 然 语 言 处 理
[5]
、地 质 地 理 分
析
[6,7]
、时间序列分析
[8]
、基因测序
[9,10]
、成像识别
[11]
等。相似
度有多种定义方式,在不考虑语义的情形下有夹角余弦
[1]
、
Levenshtein距离
[4]
、Dice系数
[11]
、信息熵
[12]
以及利用最长公
共子序列 (
LCS)的定义
[2,3,7,13,14]
等。根据使用场景的不同,
LCS还有一些变种,如可逆序 LCS、滑动窗口 LCS、加权 LCS、编
辑距离约束 LCS等
[15,16]
。本文考虑 LCS问题的一个变种:最
长循环公共子序列问题(LCCS)
[17,18]
,即对两个字符串 X、Y,将
X向 左 循 环 移 位 i次 后 得 到 的 字 符 串 记 为 X
i
,求 解 所 有
LCS(X
i
,Y)中的最长者。这里与最长 LCS对应的 i称为最优
移位数。利用 LCCS可定义字符串的循环相似度为
sim(X,Y)=
|LCCS(X,Y)|
max(|X|,|Y|)
(1)
其中:|· |表示字符串长度。循环相似度的典型应用是抄袭检
测或自然语言分析中 对倒装现象 的识别,例 如 Iam here和
HereIam,两个句子应当被认为非常相似;另一方面,一些原核
生物拟核中的 DNA序列呈现环状结构,此时进行它们基因组
的比对也归结为字符串的循环相似度问题
[9,10]
。
对于直接求解 LCCS(X,Y)的算法文献描述较少,目前最
优算法是
Tiskin
[19]
给出的时间复杂度为 O(mn)的算法,其中
m、n分别是两个字符串的长度,但数据结构较复杂。由于 LCS
可等效为最长上升子序列(LIS)问题
[20]
,该问题也可借鉴最长
循环上升子序列(LICS)问题的求解方法。计算 LICS最简单
的思路是穷举,若基于经典的动态规划算法
[20]
穷举,则时间代
价为 O(n′
2
log(n′)),其中 n′是与 LIC问题等效的 LIS问题的
数列长度,可以用 mn除以字符种类数来估计;若基于 Emde
Boas
树算法
[21,22]
穷举,则时间代价约为 O(n′
2
log(log(n′))),
计算量仍大,因此穷举前对移位数进行初步筛选是非常必要
的。Albert等人
[17]
、Deorowicz
[18]
分别提出了对移位数进行筛
选的方法,最终的时间复杂度分别为 O(n′llog(n′))和 O(n′l,
(n′+l
3
)log(n′))),其中 l=|LICS|=|LCCS|。
容易发现,随着两字符串相似度的增加,l增大,文献[17,
18]中算法的候选移位数增多,效率下降。Albert等人
[17]
给出
的解决方案是,当候选集合较大时,不必严格遵循定义,而是可
采用蒙特卡罗法随机抽取部分候选元素,得出近似最优解,这
样处理后的时间复杂度为 O(n′
3/2
log(n′))。尽管这可能导致
错误的结果,但考虑到在实际应用中常涉及海量数据,并且字
符串相似度的概念本身有一定的模糊性,牺牲准确度换取效率
仍然是值得的。
本文先通过证明增删元素时,LCS增量的一个不等式来估
计 |LCCS|的上下限,再得到最优移位数的必要条件,从而得到
第 37卷第 11期
2020年 11月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol37No11
Nov.2020
下载后可阅读完整内容,剩余4页未读,立即下载
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
weixin_38703669
- 粉丝: 8
- 资源: 879
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析:故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全:高效编程的秘密武器
- 网页制作入门:常用代码详解
- TX2440A开发板网络远程监控系统移植教程:易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析:Socket基础与应用
- 掌握Struts1:Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全:字体、文本、列表样式详解
- Proteus元件库大全:从基础到高级组件
- 74HC08芯片:高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题:设置字符集为GB2312
- C语言的诞生与演进:从汇编到系统编程的革命
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)