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

阿牛CPP

“中國(guó)就有這么一群奇怪的人, 本身是最底階層, 利益每天都在被損害,卻具有統(tǒng)治階級(jí)的意識(shí). 在動(dòng)物世界里找這么弱智的東西都幾乎不可能。” ——林語(yǔ)堂

字符串相似度算法( Levenshtein Distance算法)

昨天論壇看到的,簡(jiǎn)單寫(xiě)了一下
題目: 一個(gè)字符串可以通過(guò)增加一個(gè)字符,刪除一個(gè)字符,替換一個(gè)字符得到另外一個(gè)字符串,假設(shè),我們把從字符串A轉(zhuǎn)換成字符串B,前面3種操作所執(zhí)行的最少次數(shù)稱(chēng)為AB相似度
如  abc adc  度為 1
      ababababa babababab 度為 2
      abcd acdb 度為2


 字符串相似度算法可以使用 Levenshtein Distance算法(中文翻譯:編輯距離算法) 這算法是由俄國(guó)科學(xué)家Levenshtein提出的。其步驟

Step Description
1 Set n to be the length of s.
Set m to be the length of t.
If n = 0, return m and exit.
If m = 0, return n and exit.
Construct a matrix containing 0..m rows and 0..n columns.
2 Initialize the first row to 0..n.
Initialize the first column to 0..m.
3 Examine each character of s (i from 1 to n).
4 Examine each character of t (j from 1 to m).
5 If s[i] equals t[j], the cost is 0.
If s[i] doesn't equal t[j], the cost is 1.
6 Set cell d[i,j] of the matrix equal to the minimum of:
a. The cell immediately above plus 1: d[i-1,j] + 1.
b. The cell immediately to the left plus 1: d[i,j-1] + 1.
c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.
7 After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].

C++實(shí)現(xiàn)如下
#include <iostream>
#include 
<vector>
#include 
<string>
using namespace std;

//算法
int ldistance(const string source,const string target)
{
    
//step 1

    
int n=source.length();
    
int m=target.length();
    
if (m==0return n;
    
if (n==0return m;
    
//Construct a matrix
    typedef vector< vector<int> >  Tmatrix;
    Tmatrix matrix(n
+1);
    
for(int i=0; i<=n; i++)  matrix[i].resize(m+1);

    
//step 2 Initialize

    
for(int i=1;i<=n;i++) matrix[i][0]=i;
    
for(int i=1;i<=m;i++) matrix[0][i]=i;

     
//step 3
     for(int i=1;i<=n;i++)
     
{
        
const char si=source[i-1];
        
//step 4
        for(int j=1;j<=m;j++)
        
{

            
const char dj=target[j-1];
            
//step 5
            int cost;
            
if(si==dj){
                cost
=0;
            }

            
else{
                cost
=1;
            }

            
//step 6
            const int above=matrix[i-1][j]+1;
            
const int left=matrix[i][j-1]+1;
            
const int diag=matrix[i-1][j-1]+cost;
            matrix[i][j]
=min(above,min(left,diag));

        }

     }
//step7
      return matrix[n][m];
}

int main(){
    
string s;
    
string d;
    cout
<<"source=";
    cin
>>s;
    cout
<<"diag=";
    cin
>>d;
    
int dist=ldistance(s,d);
    cout
<<"dist="<<dist<<endl;
}

#include 
<iostream>
#include 
<vector>
#include 
<string>
using namespace std;

//算法
int ldistance(const string source,const string target)
{
    
//step 1

    
int n=source.length();
    
int m=target.length();
    
if (m==0return n;
    
if (n==0return m;
    
//Construct a matrix
    typedef vector< vector<int> >  Tmatrix;
    Tmatrix matrix(n
+1);
    
for(int i=0; i<=n; i++)  matrix[i].resize(m+1);

    
//step 2 Initialize

    
for(int i=1;i<=n;i++) matrix[i][0]=i;
    
for(int i=1;i<=m;i++) matrix[0][i]=i;

     
//step 3
     for(int i=1;i<=n;i++)
     
{
        
const char si=source[i-1];
        
//step 4
        for(int j=1;j<=m;j++)
        
{

            
const char dj=target[j-1];
            
//step 5
            int cost;
            
if(si==dj){
                cost
=0;
            }

            
else{
                cost
=1;
            }

            
//step 6
            const int above=matrix[i-1][j]+1;
            
const int left=matrix[i][j-1]+1;
            
const int diag=matrix[i-1][j-1]+cost;
            matrix[i][j]
=min(above,min(left,diag));

        }

     }
//step7
      return matrix[n][m];
}

int main(){
    
string s;
    
string d;
    cout
<<"source=";
    cin
>>s;
    cout
<<"diag=";
    cin
>>d;
    
int dist=ldistance(s,d);
    cout
<<"dist="<<dist<<endl;
}

posted on 2008-09-21 03:03 whn 閱讀(20481) 評(píng)論(15)  編輯 收藏 引用 所屬分類(lèi): 算法

評(píng)論

# re: 字符串相似度算法( Levenshtein Distance算法) 2008-09-21 10:13 fejay

我也在論壇上看到了。學(xué)習(xí)學(xué)習(xí)  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2008-09-21 22:35 Post

在哪里看到的?  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2008-09-22 16:30 Vinson

kind of like DP..  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2008-10-05 13:20 kina

請(qǐng)問(wèn):
把從字符串A轉(zhuǎn)換成字符串B,如果最少執(zhí)行次數(shù)為3,那這3次的執(zhí)行動(dòng)作要如何印出來(lái)?需把程式加在哪裡?
  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-13 12:39 shinjikun

如果不需要得到執(zhí)行動(dòng)作的話(huà)你這個(gè)算法空間復(fù)雜度高了(應(yīng)該是O(n))。
如果需要的話(huà),只要回溯就可以了。  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-17 12:36 whn

@shinjikun
不知道你是怎么做的 不過(guò) 回溯 速度很慢的   回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-25 01:06 test01x

我也比較關(guān)心國(guó)家大事 kina 提出的問(wèn)題。
另外,我還沒(méi)有搞清楚這個(gè)算法和KMP算法的原理和實(shí)現(xiàn)的不同支出,能指點(diǎn)一下嗎?謝謝!
我會(huì)時(shí)常關(guān)注評(píng)論。  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-25 01:07 test01x

暈,輸入法智能聯(lián)想問(wèn)題。原本應(yīng)該是:
我也比較關(guān)心 kina 提出的問(wèn)題。
另外,我還沒(méi)有搞清楚這個(gè)算法和KMP算法的原理和實(shí)現(xiàn)的不同之處,能指點(diǎn)一下嗎?謝謝!
我會(huì)時(shí)常關(guān)注評(píng)論。  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-26 10:19 whncpp

@test01x
兩個(gè)算法解決的問(wèn)題是完全不一樣的,kmp解決模式匹配的LD 是解決相似度的 問(wèn)題,  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-30 13:50 ray040123

dp算法

如果想打印,用一個(gè)數(shù)組c[i][j] 記錄每步的決策(above,left,diag)
之后從c[n,m] 倒推,記錄,輸出即可  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2011-06-16 15:46 splash

代碼有瑕疵。因?yàn)閙atrix[0][0]沒(méi)有初始化。  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2012-04-24 11:43 peter4431

@splash
說(shuō)明你沒(méi)看懂 matrix[0][0]就沒(méi)用到  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法) 2012-06-14 08:48 safds

請(qǐng)問(wèn)這個(gè)在哪個(gè)環(huán)境里通過(guò)了?

REDMOND # 139.com謝謝  回復(fù)  更多評(píng)論   

# re: 字符串相似度算法( Levenshtein Distance算法)[未登錄](méi) 2016-01-07 11:50 max

@peter4431
我只是路過(guò),感謝樓主的分享,但是這個(gè)地方確實(shí)是用到啦,像掃雷一樣,周邊都是度,可能確實(shí)要初始化一下。  回復(fù)  更多評(píng)論   


只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            久久精品国产在热久久| 亚洲美女诱惑| 一区二区三区不卡视频在线观看 | 亚洲一区二区免费看| 亚洲国产精品va在线观看黑人| 亚洲一区二区三区三| 99香蕉国产精品偷在线观看| 蜜臀91精品一区二区三区| 久久精品欧美| 国产亚洲va综合人人澡精品| 一区二区三区日韩欧美| 中文欧美在线视频| 欧美日韩日本国产亚洲在线 | 美日韩丰满少妇在线观看| 国产精品国产精品| 一区二区三区成人精品| 亚洲天堂av在线免费观看| 欧美黄色片免费观看| 免费亚洲一区二区| 亚洲国产精品久久久久婷婷老年| 久久精品亚洲热| 狂野欧美性猛交xxxx巴西| 国内精品久久久| 久久av老司机精品网站导航| 欧美影院午夜播放| 国产自产v一区二区三区c| 午夜在线电影亚洲一区| 久久精品夜色噜噜亚洲a∨| 国产一区二区三区网站| 欧美自拍偷拍午夜视频| 美女视频一区免费观看| 亚洲国产欧美一区| 欧美女同视频| 亚洲午夜羞羞片| 欧美综合国产精品久久丁香| 激情综合五月天| 女仆av观看一区| 亚洲欧洲精品一区二区| 亚洲国产高清视频| 欧美日韩国产探花| 韩日欧美一区二区| 亚洲精品乱码久久久久久日本蜜臀 | 欧美喷水视频| 亚洲综合第一| 麻豆精品视频在线| 一区二区欧美国产| 国产午夜精品福利| 欧美xxx在线观看| 中国成人在线视频| 蜜臀av国产精品久久久久| 亚洲人体偷拍| 国产精品综合| 免费在线观看成人av| 国产精品99久久久久久人| 久久国产天堂福利天堂| 亚洲人成啪啪网站| 国产精品亚洲成人| 欧美成人午夜77777| 中文av一区二区| 美国三级日本三级久久99| 中国成人亚色综合网站| 国产主播精品在线| 欧美性猛片xxxx免费看久爱| 久久精选视频| 一区二区三区 在线观看视频| 久久青青草综合| 在线亚洲美日韩| 在线观看av不卡| 国产精品黄色| 欧美—级高清免费播放| 欧美专区亚洲专区| 亚洲视频碰碰| 亚洲欧洲日本一区二区三区| 欧美一区永久视频免费观看| 日韩视频专区| 尤物yw午夜国产精品视频| 国产精品久久久久久久久久久久久| 久久躁狠狠躁夜夜爽| 亚洲欧美怡红院| 一本到12不卡视频在线dvd| 欧美成ee人免费视频| 久久成人亚洲| 亚洲欧美中文另类| 国产精品99久久久久久人 | 国产有码在线一区二区视频| 欧美午夜精品久久久久久久| 欧美国产三区| 另类综合日韩欧美亚洲| 性欧美暴力猛交另类hd| 亚洲一区二区三区三| aa日韩免费精品视频一| 亚洲欧洲免费视频| 亚洲高清在线观看| 久久亚洲国产精品一区二区| 久久精品99国产精品日本| 午夜宅男欧美| 欧美一区二区大片| 欧美一级在线播放| 亚洲欧美影院| 午夜欧美电影在线观看| 小黄鸭精品密入口导航| 午夜在线精品偷拍| 亚欧成人精品| 久久久91精品国产| 久久婷婷综合激情| 麻豆精品网站| 亚洲成人资源| 一个色综合av| 亚洲少妇最新在线视频| 亚洲一级特黄| 欧美一区二区三区免费视| 欧美一级黄色网| 久久久久国色av免费看影院 | 欧美国产精品劲爆| 亚洲电影av在线| 亚洲国产精品一区制服丝袜| 亚洲电影观看| 亚洲美女电影在线| 亚洲视频第一页| 久久爱www| 欧美成人激情在线| 欧美深夜福利| 国产亚洲精品美女| 亚洲经典视频在线观看| 一区二区精品国产| 欧美一区二区在线看| 久久综合成人精品亚洲另类欧美| 麻豆乱码国产一区二区三区| 欧美激情视频给我| 在线亚洲自拍| 久久精品成人一区二区三区| 欧美**人妖| 欧美日韩在线免费| 国产日韩欧美在线播放| 亚洲国产精品123| 一区二区高清视频在线观看| 欧美在线关看| 欧美激情在线| 亚洲自拍偷拍麻豆| 免费亚洲一区| 国产乱码精品一区二区三区五月婷 | 亚洲麻豆av| 欧美一区免费| 亚洲国产精品ⅴa在线观看| 一区二区三区四区蜜桃| 久久精品一区二区三区不卡| 欧美日韩国产综合视频在线观看| 国产日韩欧美| 99在线|亚洲一区二区| 久久久天天操| 一区二区三区四区五区视频 | 国产三级欧美三级日产三级99| 黄色一区二区在线| 亚洲无人区一区| 欧美69视频| 亚洲影院一区| 欧美激情一区二区| 怡红院精品视频| 欧美一级久久久| 一二美女精品欧洲| 欧美bbbxxxxx| 一区二区三区在线观看视频| 亚洲欧美在线aaa| 亚洲另类春色国产| 欧美成人国产va精品日本一级| 国产喷白浆一区二区三区| 亚洲伦伦在线| 欧美激情久久久| 久久精品理论片| 国产毛片一区二区| 亚洲欧美激情一区二区| 亚洲毛片视频| 欧美激情中文字幕一区二区| 在线观看国产精品网站| 久久久久久夜| 午夜精品福利一区二区三区av| 欧美精品1区2区| 精品动漫3d一区二区三区免费| 欧美一级夜夜爽| 亚洲一区国产一区| 国产精品sss| 一本色道久久综合精品竹菊| 欧美韩日一区| 欧美 日韩 国产 一区| 一区在线免费| 久久一区二区精品| 久久久久9999亚洲精品| 国内免费精品永久在线视频| 久久激情综合网| 欧美一级在线视频| 国产在线精品一区二区夜色| 久久久高清一区二区三区| 欧美在线日韩在线| 国产真实精品久久二三区| 久久国产精品99国产| 欧美一级免费视频| 韩国成人精品a∨在线观看| 久久国产精品亚洲va麻豆| 欧美一乱一性一交一视频| 依依成人综合视频|