本文主要是介绍NLP文本相似度之LCS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
基础
LCS（Longest Common Subsequence）通常指的是最长公共子序列，区别最长公共字串（Longest Common Substring）。我们先从子序列的定义理解：
一个序列S任意删除若干个字符得到新的序列T，则T叫做S的子序列。
子序列和子串的一个很大的不同点是，子序列不要求连接，而子串要求连接。
两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列，例如：
- 字符串12455与245576的最长公共子序列为2455；
- 字符串acdfg与adfc的最长公共子序列为adf
应用
LCS通常可以用来描述两段文字之间的相似度。例如：在辨别抄袭中，对一段文字进行修改后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，就可以判断文字修改的部分了。
求解
对于求解字符串X，Y的最长公共子序列问题，最容易想到的应该是暴力穷举法。如果假定X，Y的长度分别为m、n，则X共有pow(2,m)个不同的子序列，Y有pow(2,n)个不同的子序列，对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。穷举法带来的时间复杂度为 O ( 2 m ∗ 2 n ) O(2^m*2^n)
这篇关于NLP文本相似度之LCS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
