《計算機應用研究》|Application Research of Computers

求解最長循環公共子序列問題的兩個算法

Two algorithms to solve longest circular common subsequence problems

免費全文下載 (已被下載 次)  
獲取PDF全文
作者 鄭子君,王洪,余成
機構 重慶理工大學 機械工程學院;重慶交通大學 河海學院
統計 摘要被查看 次,已被下載
摘要 最長循環公共子序列(LCCS)是兩個字符串在所有可能的循環移位操作下能得到的最長公共子序列(LCS)。針對窮舉移位量求解LCCS效率過低的問題,設法對候選移位量進行篩選。通過證明循環移位操作對兩字符串間LCS長度增量影響的上下限,得到最優移位量的必要條件,從而減小了求解LCCS的枚舉量;在此基礎上,建立了求解LCCS的迭代方法,只經過少數幾次迭代便可消除絕大部分無效候選移位量;此外,還提出一個可在O(mn)的時間復雜度下快速估算LCCS的長度的近似算法。大量隨機模擬表明,當兩字符串間的相似度明顯高于隨機字符串的相似度時,提出的兩種算法表現良好。
關鍵詞 最長公共子序列;循環字符串;文本相似度;動態規劃
基金項目 國家自然科學基金青年項目(11702046)
重慶市教委科學研究項目(KJ1600910)
本文URL http://www.048285.live/article/02-2020-11-007.html
收稿日期
修回日期
頁碼 -
中圖分類號 TP301.6
文獻標志碼
012曾道人三尾中特书