lcs算法的python實現的簡單介紹

本文目錄一覽：

• 1、python自然語言處理lcs什麼意思
• 2、最長公共序列(LCS)算法用c如何實現！
• 3、LCS算法是怎麼實現的？
• 4、LCS的概述
• 5、如何求兩個字符串的最長子串
• 6、詞義相似度計算

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訓練語料有限，可能結果也不是非常準確，相信如果網上很多預訓練的詞向量可能會有更好的結果。