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 |
| DOI: | 10.57237/j.cst.2023.01.006 |
View:
Downloads:
Received: 7 January 2023
Accepted: 25 February 2023
Published Online: 2 March 2023
References
| [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. |
Join the Editorial Board
We invite active, qualified and high profile scientists and researchers to join as Editorial Board Members.
Join UsBecome a Reviewer
Scholars with a strong interest in reviewing are invited to join the reviewer panel to ensure the quality of the research to be published.
Join Us