LCS分词扩展与求解子序列算法优化研究
四川师范大学, 物理与电子工程学院, 四川成都 610101
| 摘 要： | 相似度计算作为自然语言处理（Natural Language Processing, NLP）中一项最常见且关键的任务，在查重检测、信息检索等领域有着广泛的应用。为提高文本相似度计算的准确性，在深入分析传统LCS算法的基础上，本文提出一种基于分词与同义词匹配的LCS扩展算法。该算法结合自然语言处理研究的新成果，针对LCS用于文本相似度比较时无法甄别同义词替换等常见的抄袭、套改等手段，以及在求解最长公共子序列时采用的回溯算法时间复杂度高、性能较弱等问题，在分词的基础上通过同义词词林对词语间的相似度进行计算，实现序列间同义词的匹配，达到甄别对原文进行同义词替换等抄袭、套改手段。同时，该算法对求解LCS子序列的传统算法进行改进，通过记录最长公共子序列的字符在每个序列中的关联位置，适当增加空间复杂度，实现共有序列链式标记。实验结果表明，本文提出的LCS扩展算法可以准确识别文本中同义词的替换，文本相似度的计算结果更加准确，同时使求解LCS子序列的时间复杂度由O(2max(m,n))降低至线性级别O(n)。 |
| 关 键 词： | 最长公共子序列; 动态规划; 中文分词; 同义词匹配; 链式标记 |
| DOI： | 10.57237/j.cst.2023.01.006 |
View:
Downloads:
收稿日期: 2023-01-07
接受日期: 2023-02-25
在线出版日期: 2023-03-02
Research on LCS Word Segmentation Expansion and Optimization of Subsequence Solving Algorithm
Department of Physics and Electronic Engineering, Sichuan Normal University, Chengdu 610101, China
| Abstract: | As one of the most common and critical tasks in natural language processing (NLP), similarity calculation has a wide range of applications in fields such as censorship detection and information retrieval. In order to improve the accuracy of text similarity calculation, based on the in-depth analysis of traditional LCS algorithms, this paper proposes an extended LCS algorithm based on word separation and synonym matching. The algorithm combines the new achievements in natural language processing research, and addresses the problems that LCS cannot screen the common means of plagiarism and nesting when used for text similarity comparison, as well as the high time complexity and weak performance of the backtracking algorithm used in solving the longest common subsequence, and realizes the matching of synonyms between sequences by calculating the similarity between words through synonym word forest on the basis of word separation. It achieves the screening of plagiarism and copying means such as synonym substitution to the original text. At the same time, the algorithm improves the traditional algorithm for solving LCS subsequences by recording the associated positions of the characters of the longest common subsequence in each sequence and appropriately increasing the spatial complexity to realize the chain marking of common sequences. The experimental results show that the LCS extension algorithm proposed in this paper can accurately identify the substitution of synonyms in the text, and the calculation result of text similarity is more accurate, while the time complexity of solving the LCS subsequence is reduced from O(2max(m,n)) to linear level O(n). |
| Keywords: | Longest Common Subsequence; Dynamic Programming; Chinese Participle; Matching of Synonyms; Chain Marking |
参考文献
| [1] | 翟璐莎. 最长公共子序列查询算法研究 [D]. 燕山大学, 2018. |
| [2] | Hunt J W, MacIlroy M D. An algorithm for differential file comparison [M]. Murray Hill: Bell Laboratories, 1976. |
| [3] | 徐雅静, 李通, 刘玉涛. 基于代码相似度的隐含学生行为模式挖掘 [J]. 计算机教育, 2017, (06): 90-94. |
| [4] | 李明. 文本文件差异对比算法研究 [J]. 软件, 2017, 38 (12): 216-219. |
| [5] | Dayhoff M O. Computer aids to protein sequence determination [J]. Journal of Theoretical Biology, 1965, 8 (1): 97-112. |
| [6] | Hofacker I L, Huynen M A, Stadler P F, et al. Knowledge Discovery in RNA Sequence Families of HIV Using Scalable Computers [J]. KDD, 1996, 7 (2): 1460-1483. |
| [7] | Robert A. Wagner and Michael J. Fischer. 1974. The String-to-String Correction Problem. J. ACM 21, 1 (Jan. 1974), 168–173. |
| [8] | Tseng C T, Yang C B, Ann H Y. Efficient Algorith ms for the Longest Common Subsequence Problem with Squential Substring Constraints [J]. Journal of Complexity, 2013, 29 (1): 44-52. |
| [9] | Masek W J, Paterson M S. A faster algorithm computing string edit distances☆ [J]. Journal of Computer & System Sciences, 1980, 20 (1): 18-31. |
| [10] | 林清波, 吴锤红. 求最长公共子序列长度的一个新方法 [J]. 福建农业大学学报, 1998 (04): 122-126. |
| [11] | Hirschberg D S. A linear space algorithm for computing maximal common subsequences [J]. Communications of the Acm, 1975, 18 (18): 341-343. |
| [12] | 郑翠玲. 最长公共子序列算法的分析与实现 [J]. 武夷学院学报, 2010, 29 (02): 44-48. |
| [13] | 朱巧明, 李培峰, 吴娴, 朱晓旭. 中文信息处理技术教程 [M]. 北京: 清华大学出版社, 2005. |
| [14] | 韩士洋, 马致远, 杨芳艳, 李想, 汪伟. 针对中文分词的带标签注意力的成词记忆网络 [J]. 计算机应用研究, 2022, 39 (06): 1651-1655. |
| [15] | 霍晨鹏. 科技专家遴选系统关键技术研究与实现 [D]. 华南理工大学, 2020. |
| [16] | 王洪信, 何爱元, 陈新, 张楠. 搜索引擎之中文分词技术研究 [J]. 信息技术与信息化, 2015 (10): 189-190. |
