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

阿牛CPP

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

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

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


 字符串相似度算法可以使用 Levenshtein Distance算法(中文翻譯:編輯距離算法) 這算法是由俄國科學(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++實現(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) 評論(15)  編輯 收藏 引用 所屬分類: 算法

評論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

dp算法

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

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

代碼有瑕疵。因為matrix[0][0]沒有初始化。  回復(fù)  更多評論   

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

@splash
說明你沒看懂 matrix[0][0]就沒用到  回復(fù)  更多評論   

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

請問這個在哪個環(huán)境里通過了?

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

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

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


只有注冊用戶登錄后才能發(fā)表評論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   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>
            久热精品视频在线| 亚洲电影av| 亚洲一区二区三区乱码aⅴ| 欧美极品影院| 一本色道久久综合精品竹菊 | 国产日产亚洲精品系列| 欧美一区二区三区男人的天堂 | 国产伦精品一区二区三区免费| 亚洲欧美文学| 欧美一区免费视频| 在线精品视频在线观看高清| 亚洲福利视频一区二区| 欧美日韩不卡视频| 午夜一区在线| 久久久久久久久久久久久9999| 亚洲区欧美区| 亚洲人成网站在线观看播放| 国产精品日韩在线播放| 女生裸体视频一区二区三区| 欧美日韩亚洲一区二区三区在线观看 | 国产欧美精品| 亚洲第一免费播放区| 国产精品久久久久久av福利软件| 久久九九免费视频| 欧美母乳在线| 欧美激情视频一区二区三区不卡| 欧美日韩综合一区| 国产精品久久久一区麻豆最新章节| 欧美主播一区二区三区| 久久午夜av| 亚洲专区欧美专区| 久久精品国产第一区二区三区最新章节| 在线看不卡av| 亚洲国产综合在线看不卡| 欧美日韩国产综合视频在线观看| 亚洲激情av| 欧美一进一出视频| 欧美成人精品影院| 久久久九九九九| 麻豆freexxxx性91精品| 久久高清国产| 久久嫩草精品久久久精品一| 日韩亚洲欧美一区| 中文欧美字幕免费| 国内久久精品视频| 亚洲第一在线| 国产精品午夜av在线| 久久一区视频| 欧美理论在线播放| 久久精品成人一区二区三区| 久久久水蜜桃av免费网站| 亚洲精品在线观| 亚洲一区中文字幕在线观看| 在线免费高清一区二区三区| 亚洲免费观看在线观看| 国产午夜精品理论片a级探花 | 久久久久一区二区三区| 亚洲欧美国产制服动漫| 欧美激情bt| 欧美一站二站| 亚洲人体大胆视频| 久久av二区| 一区二区三区欧美| 亚洲国产婷婷香蕉久久久久久| 国产精品老牛| 91久久国产综合久久91精品网站| 国产麻豆91精品| 亚洲国产美女| 韩日视频一区| 宅男噜噜噜66一区二区66| 亚洲国产成人精品久久| 亚洲免费视频在线观看| 亚洲精品国产精品国产自| 中文高清一区| 日韩亚洲精品在线| 久久午夜电影| 久久只精品国产| 国产精品专区第二| 亚洲人成人一区二区三区| 国内精品视频在线观看| 午夜免费久久久久| 亚洲一区二区综合| 欧美日韩精品在线| 亚洲国产激情| 亚洲激情社区| 久久综合中文| 欧美成人免费全部| 在线观看视频日韩| 久久精品久久综合| 久久精品国产清高在天天线| 国产精品日韩欧美大师| 亚洲午夜一区二区三区| 中文久久精品| 国产精品久久久久aaaa| 一区二区日韩欧美| 亚洲午夜一级| 国产精品国产一区二区| 亚洲国产欧美一区二区三区丁香婷| 最近中文字幕日韩精品| 毛片一区二区| 欧美高清视频www夜色资源网| 国模精品一区二区三区| 久久精品一区二区三区不卡牛牛| 久久精品人人做人人爽| 国产一区二区三区日韩欧美| 久久se精品一区二区| 麻豆av一区二区三区| 亚洲一区二区三区中文字幕| 国产精品福利在线观看网址| 亚洲欧美一区二区激情| 久久久亚洲影院你懂的| 亚洲国产成人精品久久久国产成人一区| 久久精品夜色噜噜亚洲a∨| 欧美91视频| 国产日韩欧美视频| 久热精品视频在线免费观看| 欧美激情亚洲综合一区| 亚洲美女视频在线观看| 欧美三级电影一区| 亚洲欧美怡红院| 欧美1区2区3区| 夜夜精品视频| 国产精品都在这里| 亚洲国产裸拍裸体视频在线观看乱了中文 | 国产精品久久久久三级| 亚洲制服少妇| 亚洲第一精品影视| 一本大道久久a久久综合婷婷| 国产精品女人网站| 久久综合综合久久综合| av成人免费观看| 久久综合激情| 亚洲视频综合| 韩国av一区二区三区| 欧美精品久久久久久久| 中文一区字幕| 亚洲在线一区二区三区| 亚洲国产精品久久久久婷婷老年| 欧美日韩亚洲一区二区三区在线 | 先锋a资源在线看亚洲| 亚洲国产经典视频| 国产精品久久久免费| 欧美激情1区2区3区| 久久黄金**| 亚洲日本中文字幕区| 欧美亚洲视频在线观看| 亚洲毛片在线观看.| 国产亚洲a∨片在线观看| 欧美精品1区| 欧美日韩一本到| 欧美激情按摩在线| 久久久久久国产精品mv| 亚洲综合色丁香婷婷六月图片| 亚洲自拍偷拍网址| 亚洲激情第一区| 国产精品看片资源| 免费亚洲婷婷| 亚洲欧美日韩成人高清在线一区| 久久久久国产精品一区二区| 日韩写真视频在线观看| 国产欧美精品va在线观看| 欧美成人在线免费观看| 亚洲欧美综合一区| 久久久精品动漫| 在线视频亚洲欧美| 国产精品久久99| 老司机凹凸av亚洲导航| 夜夜精品视频一区二区| 欧美18av| 午夜视频一区在线观看| 欧美一区二区三区四区高清| 亚洲精品一品区二品区三品区| 一色屋精品亚洲香蕉网站| 韩国v欧美v日本v亚洲v| 亚洲精品一区二区三区婷婷月| 樱花yy私人影院亚洲| 欧美久久精品午夜青青大伊人| 午夜精品久久久久久久男人的天堂| 一级成人国产| 夜夜精品视频一区二区| 一本色道88久久加勒比精品 | 亚洲国产精品v| 亚洲视频欧美在线| 在线看成人片| 99成人在线| 99re8这里有精品热视频免费| 亚洲黄色成人网| 亚洲免费伊人电影在线观看av| 欧美激情麻豆| 久热精品视频在线免费观看| 国产真实久久| 久久婷婷人人澡人人喊人人爽| 日韩视频精品| 久久久欧美精品| 国产欧美日韩三区| 日韩小视频在线观看专区| 亚洲国产另类久久久精品极度| 欧美一级午夜免费电影| 国产精品草莓在线免费观看| 一本色道久久综合狠狠躁的推荐|