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

阿牛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>
            欧美在线播放高清精品| 欧美在线看片| 亚洲高清一区二区三区| 免费在线欧美黄色| 一本一本久久a久久精品综合麻豆| 最新亚洲一区| 欧美日韩aaaaa| 午夜久久一区| 久久久久久噜噜噜久久久精品 | 欧美伊人久久大香线蕉综合69| 国产情人综合久久777777| 久久久中精品2020中文| 猛干欧美女孩| 亚洲欧美中日韩| 久久婷婷丁香| 亚洲一区二区精品| 久久久久久久一区二区三区| 亚洲精品一二三| 亚洲一区二区三区四区五区黄| 黄色成人av在线| 亚洲巨乳在线| 国内精品久久久久久久97牛牛| 亚洲第一主播视频| 国产日韩欧美在线播放| 亚洲国产日韩一区| 国产伦精品一区二区三区免费迷 | 亚洲国产另类久久精品| 国产伦精品一区二区三区照片91| 欧美成人精品不卡视频在线观看 | 香蕉视频成人在线观看| 日韩小视频在线观看专区| 午夜综合激情| 亚洲精品一区中文| 久久久久国产精品www| 亚洲一区二区三区在线观看视频| 久久一区二区三区av| 亚洲欧美日韩国产综合精品二区| 美女网站在线免费欧美精品| 欧美中文字幕在线观看| 欧美日韩精品二区第二页| 欧美国产激情| 国内外成人免费激情在线视频网站 | 亚洲欧美视频一区| 欧美福利精品| 欧美成人嫩草网站| 国产一区香蕉久久| 亚洲欧美国产精品va在线观看| 日韩视频一区二区| 牛牛国产精品| 欧美不卡在线| 亚洲成人原创| 久久视频这里只有精品| 久久久久久久久伊人| 国产精品欧美久久| 亚洲午夜电影| 欧美在线观看网址综合| 国产精品乱人伦一区二区| 日韩视频精品在线| 亚洲网站在线| 国产精品久久久久9999吃药| 亚洲免费成人| 亚洲综合欧美| 国产日韩欧美三级| 久久精品女人的天堂av| 久久午夜视频| 亚洲国产精品www| 欧美大片免费看| 亚洲精品免费一区二区三区| 夜夜嗨av一区二区三区网页| 欧美色大人视频| 亚洲女人av| 久久久水蜜桃| 亚洲欧洲精品一区二区精品久久久| 久久一区亚洲| 亚洲人成高清| 亚洲欧美国内爽妇网| 国产免费观看久久| 久久精品官网| 亚洲日本久久| 欧美一区二区视频免费观看| 一区二区三区自拍| 欧美精品在线播放| 亚洲一区二区在线看| 久久久久欧美精品| 亚洲精品美女久久7777777| 欧美日本在线播放| 香蕉国产精品偷在线观看不卡| 另类春色校园亚洲| 一本一本久久a久久精品牛牛影视| 国产精品久久久| 欧美中文字幕在线视频| 亚洲国产高清视频| 欧美一区激情| 亚洲片区在线| 国产亚洲欧美中文| 欧美激情一区二区久久久| 亚洲曰本av电影| 欧美国产成人在线| 欧美一级日韩一级| 亚洲精品系列| 国产主播一区二区三区| 欧美人成在线| 久久久一区二区| 亚洲午夜91| 亚洲精品国产欧美| 久久天天躁夜夜躁狠狠躁2022| 日韩一级大片| 在线播放日韩欧美| 国产欧美日韩综合| 欧美日韩精品伦理作品在线免费观看| 亚洲综合不卡| 99精品视频一区| 欧美成人视屏| 久久综合色天天久久综合图片| 亚洲一区bb| 99国产精品久久久久久久| 1024国产精品| 一区二区三区在线免费观看| 国产精品久久久久高潮| 欧美精品在线看| 麻豆av福利av久久av| 久久福利电影| 性8sex亚洲区入口| 亚洲一区二区三区在线视频| 亚洲狼人精品一区二区三区| 欧美成人蜜桃| 欧美成年人在线观看| 久久人人97超碰精品888| 午夜视频在线观看一区二区三区| 亚洲乱码日产精品bd| 亚洲黄色在线视频| 亚洲高清在线播放| 影音国产精品| 亚洲激情综合| 亚洲国产精品专区久久| 亚洲福利国产精品| 亚洲高清不卡| 亚洲精品乱码| 中国女人久久久| 亚洲一区二区伦理| 中文网丁香综合网| 亚洲香蕉网站| 亚洲欧美一区二区视频| 性欧美xxxx视频在线观看| 亚洲欧美激情一区| 欧美一区二区精美| 久久久国产精品一区| 久久久在线视频| 欧美国产欧美综合| 亚洲黄页一区| 在线视频欧美日韩| 亚洲欧美久久久| 久久免费99精品久久久久久| 久久综合中文| 欧美三级小说| 国产欧美一区二区精品忘忧草| 国产日韩在线一区| 亚洲东热激情| 亚洲五月婷婷| 久久精品夜夜夜夜久久| 欧美成人69| 99精品国产在热久久| 午夜日韩在线观看| 欧美14一18处毛片| 国产精品久久久久久久久久三级| 国产精品女人久久久久久| 国产综合色精品一区二区三区 | 欧美日韩国产综合新一区| 国产精品久线观看视频| 在线观看久久av| 在线视频一区二区| 久久婷婷国产综合尤物精品| 亚洲激情在线播放| 欧美亚洲日本网站| 欧美国产日韩一区| 国产视频在线观看一区二区| 亚洲精品国产精品国自产观看浪潮| 亚洲男人的天堂在线观看| 欧美91视频| 亚洲欧美日韩在线| 欧美黄色免费| 激情视频一区二区三区| 亚洲香蕉伊综合在人在线视看| 另类综合日韩欧美亚洲| 一本大道久久精品懂色aⅴ | 亚洲综合视频网| 欧美精品一区二| 精品成人a区在线观看| 亚洲综合国产| 亚洲激情电影在线| 久久蜜桃精品| 国产亚洲欧美一区| 亚洲欧美日韩在线| 亚洲精品一区二区在线| 久久综合亚洲社区| 国内精品**久久毛片app| 亚洲男人的天堂在线观看| 91久久国产自产拍夜夜嗨| 久久精彩免费视频| 国产一区二区毛片|