本文目录一览：
python自然语言处理lcs什么意思
lcs是Longest common subsequence的缩写，翻译过来也就是最长公子序列，是一种算法，所以python自然语言处理lcs。就是说使用python实现求解最长公子序列的算法。
如果解决了您的问题请采纳！
如果未解决请继续追问
最长公共序列(LCS)算法用c如何实现！
int **lcs_length(char p[],char q[],int **c,int **k,int m,int n)
{
int i,j;
for(i=1;i=m;i++)
{
for(j=1;j=n;j++)
{
if(p[i-1]==q[j-1])//如果两个字母相等的情况
{
c[i][j]=c[i-1][j-1]+1;
k[i][j]=1;
}
else
{
if(c[i-1][j]=c[i][j-1])//两字母不等情况1
{
c[i][j]=c[i-1][j];
k[i][j]=2;
}
else//两字母不等情况2
{
c[i][j]=c[i][j-1];
k[i][j]=3;
}
}
}
}
return c,k;
}
输出代码
void print_lcs(int **k,char p[],int i,int j)
{
if(i==0||j==0)
return ;
if(k[i][j]==1)
{
print_lcs(k,p,i-1,j-1);//通过递归的方法按照输入的从头到尾的顺序输出LCS
coutp[i-1];
}
else if(k[i][j]==2)
print_lcs(k,p,i-1,j);
else
print_lcs(k,p,i,j-1);
}
LCS算法是怎么实现的？
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置。
下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。下面是新的矩阵生成方式：
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
不用多说，你大概已经看出来了。当字符匹配的时候，我们并不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。
这样做速度比较快，但是花的空间太多。我们注意到在改进的矩阵生成方式当中，每生成一行，前面的那一行就已经没有用了。因此我们只需使用一维数组即可。最终的代码如下：
Private Function LCS(ByVal str_1 As String, ByVal str_2 As String) As String
If str_1 = "" Or str_2 = "" Then Return ""
Dim c(str_1.Length) As Integer
Dim max, maxj, i, j As Integer
maxj = 0 : max = 0 '这两个是标志变量
For i = 0 To str_2.Length - 1
For j = str_1.Length - 1 To 0 Step -1
If str_2.Chars(i) = str_1.Chars(j) Then
If i = 0 Or j = 0 Then
c(j) = 1
Else
c(j) = c(j - 1) + 1
End If
Else
c(j) = 0
End If
If c(j) max Then '把改成=则返回最后一个最长匹配子串
max = c(j) : maxj = j '更新标志变量
End If
Next
Next
If max = 0 Then Return ""
Return str_1.Substring(maxj - max + 1, max) '直接从标志变量得出结果
End Function
LCS的概述
濒海战斗舰(Littoral Combat Ship，LCS)是美国海军下一代水面战舰的第一种设计。作为濒海区域(靠近海岸)作战的相对小型水面船只，LCS比海军的导弹驱逐舰更小，与国际上所指的护卫舰相仿。然而，LCS还具有小型攻击运输舰的能力，具有一个可操作两架SH-60海鹰直升机(SH-60 Seahawk)的飞行甲板和机库，还有从船尾回收和释放小艇的能力，以及足够大的货运量来运输一只小型攻击部队、装甲车、和码头接驳器。LCS的标准武装是一门Mk110 57毫米快炮，并可依照不同任务套件选用非线视界发射系统(Non-Line-of-Sight Launch System)或Mark 54 MAKO 轻型鱼雷及其他武装。它还能搭载无人空中、水面和水下载具。LCS强调速度、可根据战斗任务类型灵活调整的模组空间和较浅的吃水。
如何求两个字符串的最长子串
//求使用最长子串使用LCS算法
char* LCS(char left[],char right[]) { //获取左子串的长度,获取右子串的长度 int lenLeft=strlen(left),lenRight=strlen(right),k; //注意这里要写成char型,而不是int型,否则输入整型数据时会产生错误。 //矩阵c纪录两串的匹配情况 char*c=malloc(lenRight),*p; //int c[M][M]={0};//当将c申明为一个二维数组时 int start,end,len,i,j;//start表明最长公共子串的起始点，end表明最长公共子串的终止点 end=len=0;//len表示最长公共子串的长度 for(i=0; ilenLeft; i++) //串1从前向后比较 { //串2从后向前比较,为什么要从后向前呢?是把一维数组c[ ]当二维数组来用, //如果要从前向后,可以将c申明为一个二维数组c[M][M].但程序要做相应调整. // for(j=0;jlenRight;j++)//当c申明为一个二维数组时 for(j=lenRight-1; j=0; j--) { if(left[i] == right[j])//元素相等时 { if(i==0||j==0) c[j]=1;//c[i][j]=1; else { c[j]=c[j-1]+1;//c[i][j]=c[i-1][j-1]+1; } } else c[j] = 0; //c[i][j]=0; if(c[j] len) //if (c[i][j]len) { len=c[j]; //len=c[i][j]; end=j; } } } start=end-len+1; //数组p纪录最长公共子串 p =(char*)malloc(len+1); for(i=start; i=end; i++) { p[i-start] = right[i]; } p[len]='\0'; return p; } void main() { char str1[M],str2[M]; printf("请输入字符串1:"); gets(str1) printf("请输入字符串2:"); gets(str2); printf("最长子串为:"); printf("%s\n",LCS(str1,str2)); }
词义相似度计算
语义计算索引作业一 词义相似度计算
实现2种词汇相关度计算方法，基于词典与基于语料各一种
基于Mturk-771进行实验和分析(开放式) ：
这里我们使用WordNet词典，使用的工具是nltk，利用里面自带的相似度方法来计算词义相似度。Nltk是比较知名的Python自然语言处理包，从里面可以导入wordnet词典和一些语料，来帮助我们进行词义等的分析。其中有六种相似度计算的算法：
brown_ic = wordnet_ic.ic('ic-brown.dat')
path_similarity(c1,c2) # 词在词典层次结构中的最短路径
wup_similarity(c1,c2) # Wu-Palmer 提出的最短路径
lch_similarity(c1,c2) # Leacock Chodorow 最短路径加上类别信息
res_similarity(c1,c2, brown_ic) # -log P(LCS(c1,c2)) 公共包容节点在层次结构中位置越低，相似性越大
jcn_similarity(c1,c2, brown_ic) # 1/2 * log P(LCS(c1,c2)) - (logP(c1) + logP(c2))
lin_similarity(c1,c2, semcor_ic) # 2 * log P(LCS(c1,c2)) / (logP(c1) + logP(c2))
特殊处理：
1、 其中lin_similarity、wup_similarity和path_similarity结果范围在[0,1]之间，而由我们的数据可知，数据结果应该在[0,5]之间，因此这里我们把结果×5进行处理。
2、 一个词会有多种词义，判断两个词需要让两个词之间的各个词义进行比较。如何判断两个词之间的相似度呢？我同时使用了最大值和平均值，发现平均值得到的结果会非常小，猜想两个词之间可能有较多的词义无关，影响了结果，因此最后选择用最大值。
3、 lch_similarity得到的值都不大，因此最后进行了归一化处理×5
4、 res_similarity(c1,c2, brown_ic) jcn_similarity(c1,c2, brown_ic)得到的结果存在le+300，而第二大的数分别为12.26837533572617和19.273454235478546，因此取13和20代替原来的最大le+300。
剩余分数则是归一化后再×5
五分分值：
因为预训练词向量都比较大，这里就使用了gensim中的word2vec模型进行自行训练，训练语料为text8，大概有100M左右。
最后得到的结果如下图：score为真实评分分布，w2v为word2vec实际评分分布。
结果分析使用了均方误差
由图可以看出，word2vec方法和 res算法结果较好，观察预测结果分布，可以看出这两种方法和真实结果分布比较相似。
在观察时，我们也发现，path等方法相似度偏向与1（或者是5）左右，原因是我们这里取的是最大值，对于account,explanation这两个单词，因为它们有相同的词义，这里就认为相似度最大。但实际在现实生活中，考虑两个词词义是否相似，除却词义的重合程度外，可能还要考虑两个词是否是常用词义相似等等。比如两个词常用含义相似和两个词罕见含义相似，虽然都是某种词义相似，但显然前者更能体现词的相似度。
因此可能取平均和取最大都不能很好的描述两个词之间的相似度。而语料的方法则可以得到词的常用和罕见意义这一信息。这里用word2vec训练语料有限，可能结果也不是非常准确，相信如果网上很多预训练的词向量可能会有更好的结果。
