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

阿牛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>
            欧美国产先锋| 久久噜噜亚洲综合| 亚洲国产裸拍裸体视频在线观看乱了 | 小处雏高清一区二区三区| 国产精品免费一区二区三区在线观看 | 午夜精品久久久久久| 亚洲欧美激情诱惑| 国产在线视频不卡二| 免费观看久久久4p| 欧美女同在线视频| 久久成人免费网| 久久久久九九九| 亚洲日本精品国产第一区| 99综合电影在线视频| 国产视频欧美视频| 亚洲国产精品va在看黑人| 国产精品99免视看9| 久久一区二区三区超碰国产精品| 免费亚洲一区| 欧美一区深夜视频| 欧美成人免费在线视频| 欧美亚洲一级| 欧美高清在线播放| 久久动漫亚洲| 欧美精品亚洲| 久久蜜臀精品av| 欧美另类一区| 另类人畜视频在线| 国产精品久久久999| 欧美激情一区二区三区| 国产精品一区二区你懂得| 亚洲国产综合在线| 国产日韩欧美在线看| 最新国产成人在线观看 | 美女脱光内衣内裤视频久久网站| 亚洲一级在线观看| 欧美a级在线| 久久久国产一区二区| 欧美色精品在线视频| 欧美高清视频一区| 国内精品伊人久久久久av一坑| 亚洲精选国产| 亚洲欧洲一区二区三区在线观看| 午夜精品在线视频| 亚洲欧美国产精品专区久久| 欧美高清日韩| 久久性天堂网| 国产一区二区日韩精品欧美精品| 99在线热播精品免费| 亚洲伦理在线观看| 欧美r片在线| 欧美大片在线看免费观看| 国产日韩欧美在线视频观看| 在线综合亚洲欧美在线视频| 9久草视频在线视频精品| 久久亚洲综合色一区二区三区| 午夜精品福利电影| 欧美午夜一区二区福利视频| 亚洲精品视频一区| 亚洲精品日韩在线观看| 久久亚洲二区| 男男成人高潮片免费网站| 好吊色欧美一区二区三区视频| 欧美一区二区视频网站| 久久精品视频网| 国产一区在线播放| 亚洲欧美成人一区二区三区| 欧美日韩国产电影| 99xxxx成人网| 亚洲女优在线| 国产欧美日韩在线观看| 久久se精品一区二区| 久久人人爽人人爽| 在线看不卡av| 欧美精品二区| 亚洲一区在线播放| 久久亚洲国产成人| 亚洲激情一区二区三区| 欧美国产日韩xxxxx| 一本久久青青| 久久国产一二区| 亚洲第一页中文字幕| 欧美激情aaaa| 亚洲网在线观看| 久久天天狠狠| 一本色道久久综合亚洲91| 国产精品久久久久一区二区三区| 欧美一区二区精品| 欧美aⅴ一区二区三区视频| 99国产精品视频免费观看一公开| 欧美视频不卡中文| 久久精品国产精品亚洲精品| 亚洲国产精品一区二区三区| 亚洲欧美国产高清| 亚洲高清影视| 国产精品日本一区二区| 麻豆av一区二区三区久久| 日韩写真在线| 久久夜色精品国产噜噜av| 一区二区三区日韩欧美| 国产欧美精品在线播放| 欧美大尺度在线| 午夜精品免费| 亚洲精品久久久久久久久久久久 | 日韩午夜中文字幕| 国产一区二区三区四区在线观看| 欧美1区2区3区| 性色av香蕉一区二区| 亚洲欧洲日产国产综合网| 午夜精品电影| 一本色道88久久加勒比精品 | 欧美日韩国产首页在线观看| 久久国产精品久久久| 一区二区精品在线观看| 欧美韩国日本一区| 久久精品在线播放| 性欧美videos另类喷潮| 99香蕉国产精品偷在线观看| 亚洲国产成人porn| 国产一区二区三区丝袜 | 欧美精品电影在线| 久久综合中文字幕| 欧美在线视频a| 亚洲砖区区免费| 一区二区三区免费网站| 亚洲国产中文字幕在线观看| 免费观看在线综合色| 久久精品99无色码中文字幕| 亚洲午夜视频| 亚洲午夜精品久久久久久app| 最近中文字幕日韩精品| 好吊日精品视频| 91久久视频| 欧美激情1区2区3区| 欧美成人一区二区在线| 久久久亚洲国产天美传媒修理工 | 亚洲与欧洲av电影| 一本色道久久综合一区| 一区二区动漫| 一区二区毛片| 亚洲午夜av电影| 亚洲线精品一区二区三区八戒| 99re国产精品| 亚洲少妇自拍| 亚洲欧美bt| 欧美在线亚洲| 另类春色校园亚洲| 欧美黄色aa电影| 91久久国产综合久久91精品网站| 91久久极品少妇xxxxⅹ软件| 亚洲人午夜精品免费| 日韩一级在线观看| 亚洲视频在线二区| 午夜精品一区二区三区电影天堂 | 亚洲欧美日本国产专区一区| 香蕉免费一区二区三区在线观看| 欧美在线999| 榴莲视频成人在线观看| 欧美精品成人一区二区在线观看 | 国产视频一区二区在线观看 | 国产精品婷婷| 激情久久综艺| 一本色道久久88亚洲综合88| 亚洲一区在线观看视频 | 欧美激情一区二区三区在线视频观看 | 99精品久久久| 午夜国产精品视频| 老司机免费视频久久| 欧美激情视频免费观看| 一本一道久久综合狠狠老精东影业 | 欧美性感一类影片在线播放 | 浪潮色综合久久天堂| 欧美极品一区二区三区| 国产精品网站在线观看| 1024亚洲| 欧美一级专区| 欧美激情在线免费观看| 亚洲午夜久久久久久久久电影院| 久久九九热免费视频| 欧美精品偷拍| 在线色欧美三级视频| 亚洲一本大道在线| 免费黄网站欧美| 亚洲视频在线视频| 欧美 日韩 国产精品免费观看| 国产精品视频免费| 日韩网站在线观看| 久久夜色精品| 亚洲精品中文字幕有码专区| 欧美一级一区| 日韩视频国产视频| 麻豆成人在线播放| 国产视频一区欧美| 亚洲女优在线| 亚洲日本黄色| 欧美成人精品h版在线观看| 国产一区二区精品| 欧美一级播放| 一区二区三区欧美成人| 欧美屁股在线|