青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

chenglong7997

字符串相似度算法介紹(整理)(轉)

最近在做這方面的應用,把我找到的資料貼出來,有需要的人可以參考參考。
1.編輯距離(Levenshtein Distance)
編輯距離就是用來計算從原串(s)轉換到目標串(t)所需要的最少的插入,刪除和替換
的數目,在NLP中應用比較廣泛,如一些評測方法中就用到了(wer,mWer等),同時也常用來計算你對原文本所作的改動數。編輯距離的算法是首先由俄國科學家Levenshtein提出的,故又叫Levenshtein Distance。
Levenshtein Distance算法可以看作動態規劃。它的思路就是從兩個字符串的左邊開始比較,記錄已經比較過的子串相似度(實際上叫做距離),然后進一步得到下一個 字符位置時的相似度。 用下面的例子: GUMBO和GAMBOL。當算到矩陣D[3,3]位置時,也就是當比較到GUM和GAM時,要從已經比較過的3對子串GU-GAM, GUM-GA和GU-GA之中選一個差別最小的來當它的值. 所以要從左上到右下構造矩陣。
編輯距離的偽算法:
整數 Levenshtein距離(字符 str1[1..lenStr1], 字符 str2[1..lenStr2])
   宣告 int d[0..lenStr1, 0..lenStr2]
   宣告 int i, j, cost
 
   對于 i 等于 由 0 至 lenStr1
       d[i, 0] := i
   對于 j 等于 由 0 至 lenStr2
       d[0, j] := j
   對于 i 等于 由 1 至 lenStr1
       對于 j 等于 由 1 至 lenStr2
           若 str1[i] = str2[j] 則 cost := 0
                                否則 cost := 1
           d[i, j] := 最小值(
                                d[i-1, j  ] + 1,     // 刪除
                                d[i  , j-1] + 1,     // 插入
                                d[i-1, j-1] + cost   // 替換
                            )
返回 d[lenStr1, lenStr2]

double Minimum(double a, double b, double c) 

 double mi; 
 
 mi = a; 
 if (b < mi) { 
  mi = b; 
 } 
 if (c < mi) { 
  mi = c; 
 } 
 return mi; 
}


int* GetCellPointer(int *pOrigin, int col, int row, int nCols) 

 return pOrigin + col + (row * (nCols + 1)); 
}

int GetAt(int *pOrigin, int col, int row, int nCols) 

 int *pCell; 
 
 pCell = GetCellPointer (pOrigin, col, row, nCols); 
 return *pCell; 
}

void PutAt(int *pOrigin, int col, int row, int nCols, double x) 

 int *pCell; 
 pCell = GetCellPointer (pOrigin, col, row, nCols); 
 *pCell = x; 
}

//編輯距離
LD(const char *s, const char *t)
{
 int *d; // pointer to matrix
 int n; // length of s
 int m; // length of t
 int i; // iterates through s
 int j; // iterates through t
 char s_i1; // ith character of s
 char s_i2; // ith character of s
 char t_j1; // jth character of t
 char t_j2; // jth character of t
 int *cost; // cost代價矩陣
 int result; // result
 int cell; // contents of target cell
 int above; // contents of cell immediately above
 int left; // contents of cell immediately to left
 int diag; // contents of cell immediately above and to left
 int sz; // number of cells in matrix

 // Step 1

 n = strlen (s);
 m = strlen (t);
 if (n == 0) 
 {
  return m;
 }
 if (m == 0) 
 {
  return n;
 }
 sz = (n+1) * (m+1) * sizeof (int);
 d = (int *) malloc (sz);
 cost = (int *) malloc (sz);

 // Step 2

 for (i = 0; i <= n; i++) 
 {
  PutAt (d, i, 0, n, i);
 }

 for (j = 0; j <= m; j++)
 {
  PutAt (d, 0, j, n, j);
 }
 for (int g=0;g<=m;g++)//把代價距離矩陣全部初始化為同一個值,以后可根據此值判斷相應的方格是否被賦過值
 {
  for(int h=0;h<=n;h++)
  {
   PutAt(cost,h,g,n,2);
  }
 }
 // Step 3

 for (i = 1; i <= n; i++) 
 {

  s_i1 = s[i-1];
  s_i2 = s[i];
  bool sbd=false;
  bool tbd=false;
  if(s_i1>=' '&&s_i1<='@'||s_i1>='A'&&s_i1<='~' )
  {//s為標點符號或其他非中文符號和數字
  sbd=true;
  }
  // Step 4

  for (j = 1; j <= m; j++) 
  {

   tbd=false;
   t_j1 = t[j-1];
   t_j2 = t[j];
   // Step 5
   if(t_j1>=' '&&t_j1<='@'||t_j1>='A'&&t_j1<='~' )
   {//t也為標點符號
    tbd=true;
   }
   if(!sbd)
   {//s為漢字
    if(!tbd)
    {//t也為漢字
     if (s_i1 == t_j1&&s_i2 == t_j2) 
     {
      bool tt=false;
      int temp=GetAt(cost,i,j,n);
      if(temp==2)
      {
       PutAt(cost,i,j,n,0);
       tt=true;
      }
      if(tt)
      {//因為st全市漢字,所以把代價矩陣他相鄰的未賦過值的三個格賦值
       int temp1=GetAt(cost,i+1,j,n);
       if(temp1==2)
       {
        PutAt(cost,i+1,j,n,0);
       }
       int temp2=GetAt(cost,i,j+1,n);
       if(temp2==2)
       {
        PutAt(cost,i,j+1,n,0);
       }
       int temp3=GetAt(cost,i+1,j+1,n);
       if(temp3==2)
       {
        PutAt(cost,i+1,j+1,n,0);
       }
      }
     }
     else 
     {
      bool tt=false;
      int temp=GetAt(cost,i,j,n);
      if(temp==2)
      {
       PutAt(cost,i,j,n,1);
       tt=true;
      }
      if(tt)
      {
       int temp1=GetAt(cost,i+1,j,n);
       if(temp1==2)
       {
        PutAt(cost,i+1,j,n,1);
       }
       int temp2=GetAt(cost,i,j+1,n);
       if(temp2==2)
       {
        PutAt(cost,i,j+1,n,1);
       }
       int temp3=GetAt(cost,i+1,j+1,n);
       if(temp3==2)
       {
        PutAt(cost,i+1,j+1,n,1);
       }
      }
     }
    }
    else
    {//t為符號
     bool tt=false;
     int temp=GetAt(cost,i,j,n);
     if(temp==2)
     {
      PutAt(cost,i,j,n,1);
      tt=true;
     }
     if(tt)
     {
      int temp1=GetAt(cost,i+1,j,n);
      if(temp1==2)
      {
       PutAt(cost,i+1,j,n,1);
      }
     }
    
    }

   }
   else
   {//s為符號
    if(!tbd)
    {//t為漢字 
     bool tt=false;
     int temp=GetAt(cost,i,j,n);
     if(temp==2)
     {
      PutAt(cost,i,j,n,1);
      tt=true;
     }
     if(tt)
     {
      int temp1=GetAt(cost,i,j+1,n);
      if(temp1==2)
      {
       PutAt(cost,i,j+1,n,1);
      }
     }
    }
    else
    {
     if(s_i1==t_j1)
     {
      int temp=GetAt(cost,i,j,n);
      if(temp==2)
      {
       PutAt(cost,i,j,n,0);
      }
     }
     else
     {
      int temp=GetAt(cost,i,j,n);
      if(temp==2)
      {
       PutAt(cost,i,j,n,1);
      }
     }
    }

   }

    // Step 6

   above = GetAt (d,i-1,j, n);
   left = GetAt (d,i, j-1, n);
   diag = GetAt (d, i-1,j-1, n);
   int curcost=GetAt(cost,i,j,n);
   cell = Minimum (above + 1, left + 1, diag + curcost);
   PutAt (d, i, j, n, cell);
  }
 }

  // Step 7

  result = GetAt (d, n, m, n);
  free (d);
  return result;

}

2.最長公共子串 (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,而是賦上其左上角元素的值加一。我們用兩個標記變量來標記矩陣中值最大的元素的位置,在矩陣生成的過 程中來判斷當前生成的元素的值是不是最大的,據此來改變標記變量的值,那么到矩陣完成的時候,最長匹配子串的位置和長度就已經出來了。

//最長公共子串
char* LCS(char*left,char* right){
 int lenLeft,lenRight;
 lenLeft = strlen(left);
 lenRight = strlen(right);
 int *c = new int[lenRight];
 int start,end,len;
 end = len = 0;
 for(int i = 0; i < lenLeft; i++){
  for(int j = lenRight-1; j >= 0; j--){
   if(left[i] == right[j]){
    if(i == 0 || j == 0)
     c[j] = 1;
    else
     c[j] = c[j-1]+1;
   }
   else
    c[j] = 0;
   if(c[j] > len){
    len = c[j];
    end = j;
   }
  }
 }
 char *p = new char[len+1];
 start = end - len + 1;
 for(i = start; i <= end; i++)
  p[i - start] = right[i];
 p[len] = '/0';
 return p;
}
3. 余弦定理 (向量空間算法)
余弦定理古老而廣泛的數學概念,在各個學科及實踐中都得到了大量的應用,這里簡單的介紹下其在判斷兩個字符串相似度的應用。
在余弦定理中基本的公式為:

假如字符串s1與s2,比較兩個字符串的相似度,sim(s1,s2),假設s1,s2中含有n個不同的字符,其分別為c1,c2,...cn,判 斷字符串的相似度轉換為兩個字符串對應的向量v1,v2之間夾角大小的判斷,余弦值越大其向量之間的夾角越小,s1與S2的相似度越大。
向量空間算法的介紹:
在 向量空間模型中,文本泛指各種機器可讀的記錄。用D(Document)表示,特征項(Term,用t表示)是指出現在文檔D中且能夠代表該文檔內容的基 本語言單位,主要是由詞或者短語構成,文本可以用特征項集表示為D(T1,T2,…,Tn),其中Tk是特征項,1<=k<=N。例如一篇文 檔中有a、b、c、d四個特征項,那么這篇文檔就可以表示為D(a,b,c,d)。對含有n個特征項的文本而言,通常會給每個特征項賦予一定的權重表示其 重要程度。即D=D(T1,W1;T2,W2;…,Tn,Wn),簡記為D=D(W1,W2,…,Wn),我們把它叫做文本D的向量表示。其中Wk是Tk 的權重,1<=k<=N。在上面那個例子中,假設a、b、c、d的權重分別為30,20,20,10,那么該文本的向量表示為 D(30,20,20,10)。在向量空間模型中,兩個文本D1和D2之間的內容相關度Sim(D1,D2)常用向量之間夾角的余弦值表示,公式為:  

 
其中,W1k、W2k分別表示文本D1和D2第K個特征項的權值,1<=k<=N。我們可以利用類似的方法來計算兩個字符串的相關度。    
這個算法網上沒找到,雖然我寫過,但是沒什么通用性,就不貼出來。很簡單的,有興趣的可以自己寫一個。

posted on 2012-04-01 07:52 Snape 閱讀(651) 評論(0)  編輯 收藏 引用 所屬分類: C++ 轉載

導航

<2012年6月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

統計

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

my

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久久久久久综合日本| 一区二区三区欧美在线| 亚洲欧美一区二区原创| 亚洲国产视频一区二区| 久久一区视频| 欧美成人在线影院| 亚洲图片激情小说| 午夜精品理论片| 国产一区二区丝袜高跟鞋图片| 原创国产精品91| 亚洲大片av| 一本色道久久综合亚洲91| 欧美色综合天天久久综合精品| 红桃视频国产精品| 欧美激情区在线播放| 欧美伦理一区二区| 欧美一区二区三区在线观看| 久久久999精品| 夜夜嗨av色一区二区不卡| 一区二区三区欧美在线| 黄色成人av在线| 亚洲日本va午夜在线电影| 国产精品午夜在线| 欧美激情女人20p| 国产精品女同互慰在线看| 免费日韩av| 欧美亚洲成人网| 欧美h视频在线| 国产精品久久久久久妇女6080 | 亚洲每日在线| 国产一区二区三区成人欧美日韩在线观看 | 永久免费精品影视网站| 亚洲精品一区二区三区av| 欧美中文字幕在线播放| 日韩亚洲一区二区| 久久精品主播| 午夜视频久久久| 欧美激情在线免费观看| 久久精品在线视频| 国产精品wwwwww| 亚洲日本成人女熟在线观看| 国产亚洲欧美日韩精品| av成人免费| 亚洲青色在线| 久久久av毛片精品| 欧美在线视频免费观看| 亚洲午夜精品一区二区三区他趣 | 亚洲永久免费av| 国产精品国产三级国产普通话三级 | 亚洲欧洲一级| 久久久久久久久久久久久女国产乱| 亚洲伊人一本大道中文字幕| 国产精品夜夜夜| 亚洲一区精品视频| 免费看的黄色欧美网站| 久久久久久欧美| 国产精品一区二区男女羞羞无遮挡 | 国产视频欧美| 一区二区三区精品视频在线观看 | 久久久天天操| 亚洲日本欧美在线| 久久久久国产精品麻豆ai换脸| 亚洲第一区在线观看| 久久av二区| 久久综合图片| 亚洲成色www久久网站| 久久久综合网| 欧美激情精品久久久久久蜜臀| 欧美日韩一区二区在线播放| 欧美一区二区精品| 国产精品影音先锋| 亚洲第一天堂av| 欧美日韩亚洲激情| 一区二区三区久久久| 黄色精品一二区| 久久久久99| 亚洲国产导航| 国产亚洲精品高潮| 欧美在线视频免费| 麻豆精品视频在线观看| 亚洲经典在线看| 欧美另类极品videosbest最新版本 | 欧美日韩精品一区二区三区四区| 午夜精品久久久久久久白皮肤| 久久国产一区| 欧美激情在线狂野欧美精品| 一区二区三区高清| 国产精品伊人日日| 亚洲精品久久久久中文字幕欢迎你 | 欧美三级视频| 亚洲欧美在线看| 免费观看一区| 一区二区三区**美女毛片| 国产伦一区二区三区色一情| 久久久国产精品亚洲一区| 亚洲国产精品一区二区www在线 | 国产精品五区| 欧美一区2区三区4区公司二百| 一级成人国产| 国产日韩欧美一区在线| 欧美成人午夜免费视在线看片| 久久久久久久999| 日韩视频免费在线| 噜噜噜噜噜久久久久久91 | 国语自产在线不卡| 欧美日本韩国| 久久人人97超碰人人澡爱香蕉| 亚洲欧美激情一区二区| 欧美激情小视频| 欧美亚洲免费电影| 亚洲精品一二三| 蘑菇福利视频一区播放| 亚洲综合电影| 亚洲人成网站在线观看播放| 国产农村妇女精品一二区| 欧美激情精品久久久| 久久精品欧美| 亚洲免费婷婷| av72成人在线| 亚洲黄色尤物视频| 老司机久久99久久精品播放免费 | 欧美三日本三级少妇三2023| 久久精品主播| 亚洲欧美日韩国产精品| 日韩视频二区| 先锋影院在线亚洲| 在线看一区二区| 亚洲一区二区欧美| 在线观看日韩专区| 一区二区高清在线| 在线视频中文亚洲| 一区二区三区欧美在线观看| 好看的日韩视频| 国产一区二区看久久| 国产精品视频专区| 欧美婷婷久久| 欧美日韩在线影院| 欧美日韩国产综合视频在线观看中文 | 99精品视频一区| 国产精品久久久久久久久免费樱桃| 一区二区三区精品| 久久久久这里只有精品| 新狼窝色av性久久久久久| 亚洲综合国产| 在线成人av.com| 曰韩精品一区二区| 在线观看欧美精品| 亚洲欧洲一区二区在线观看| 亚洲国产一区二区三区青草影视 | 欧美一区亚洲一区| 羞羞漫画18久久大片| 先锋亚洲精品| 久久久久久9| 蜜臀久久久99精品久久久久久| 日韩一级片网址| 一区二区欧美日韩| 亚洲欧美日韩精品在线| 久久www免费人成看片高清| 久久久最新网址| 欧美精品一区二区在线播放| 欧美视频一区| 国产一区二区在线观看免费播放| 欧美成人精品一区| 欧美另类专区| 国产日韩视频一区二区三区| 黄色成人av网站| aa级大片欧美| 久久精品123| 亚洲大片在线观看| 一本高清dvd不卡在线观看| 香蕉免费一区二区三区在线观看| 亚洲精品偷拍| 午夜精品美女久久久久av福利| 亚洲精品在线免费| 午夜精品视频一区| 欧美成人午夜剧场免费观看| 国产精品久久久久久福利一牛影视| 欧美成人国产一区二区| 欧美一区二区在线免费播放| 免费不卡视频| 国产乱码精品一区二区三区忘忧草| 欧美日本精品| 国产一区二区在线观看免费| 夜夜嗨av一区二区三区中文字幕| 在线日韩中文| 亚洲欧美日本在线| 亚洲大黄网站| 久久精品视频在线观看| 欧美午夜不卡在线观看免费| 经典三级久久| 国产一区二区三区在线免费观看 | 久久久爽爽爽美女图片| 欧美日韩一区二区视频在线观看| 欧美激情一区二区三区四区| 亚洲精品一区在线观看| 欧美电影免费| 性色av一区二区三区| 一区二区三区四区蜜桃| 亚洲精品影视在线观看| 久久精品卡一|