国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

編輯距離及編輯距離算法

leejan97 / 396人閱讀

摘要：無意間看到了有人問編輯距離算法，當時對這個概念很陌生，也就去學習了下，做下總結，記錄下，好記性不如爛筆頭。編輯距離又稱距離，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數(shù)。

無意間看到了有人問編輯距離算法，當時對這個概念很陌生，也就去學習了下，做下總結，記錄下，好記性不如爛筆頭。

編輯距離（Edit Distance）：又稱Levenshtein距離，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符，用數(shù)據(jù)庫的說法就是改、增、刪；一般來說就是字符串編輯距離離越小，兩個串的相似度越大。

舉個例子：S1=“eeba” S2="abac" 我們可以按照這樣的步驟轉變：

(1) 將S1中的第一個e變成a;

(2) 刪除S1中的第二個e;

(3)在S1中最后添加一個c; 那么S1到S2的編輯路徑就等于3。

當然，這種變換并不是唯一的，但如果3是所有變換中最小值的話。那么我們就可以說S1和S2的編輯距離等于3了。

聽說這個概念是由俄羅斯科學家Vladimir Levenshtein在1965年提出這個概念

概念的東西，說多了也只是理論，還是上代碼吧！

先來份java的吧，這是我工作時用的第一個編程語言：

publicclassStringSimilar{

//編輯距離求串相似度

publicdoublegetStringSimilar(Strings1,Strings2){

double d[][];//matrix

int n;//lengthofs

int m;//lengthoft

int i;//iteratesthroughs

int j;//iteratesthrought

char s_i;//ithcharacterofs

char t_j;//jthcharacteroft

double cost;//cost

//第1步

n=s1.length();

m=s2.length();

if(n==0){

return m;

}

if(m==0){

return n;

}

d=new double[n+1][m+1];

//第2步

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

d[i][0]=i;

}

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

d[0][j]=j;

}

//第3步

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

s_i=s1.charAt(i-1);

//第4步

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

t_j=s2.charAt(j-1);

//第5步

if(s_i==t_j){cost=0;}else{cost=1;}

//第6步

d[i][j]=Minimum(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost);

}

}

//第7步

return d[n][m];

}

//求最小值

privatedoubleMinimum(doublea,doubleb,doublec){

        double mi;

         mi=a;

        if(b

在來一份我最近學習的Python的


#!/user/bin/env python

# -*- coding: utf-8 -*-

class arithmetic():

    def __init__(self):

        pass

        def levenshtein(self,first,second):

        if len(first) > len(second):

                first,second = second,first

        if len(first) == 0:

                return len(second)

        if len(second) == 0:

                return len(first)

        first_length = len(first) + 1

        second_length = len(second) + 1

        distance_matrix = [range(second_length) for x in range(first_length)]

        for i in range(1,first_length):

            for j in range(1,second_length):

                 deletion = distance_matrix[i-1][j] + 1

                 insertion = distance_matrix[i][j-1] + 1

                 substitution = distance_matrix[i-1][j-1]

                 if first[i-1] != second[j-1]:

                     substitution += 1

                  distance_matrix[i][j] = min(insertion,deletion,substitution)

         print distance_matrix

         return distance_matrix[first_length-1][second_length-1]

if __name__ == "__main__":

    arith = arithmetic()

    print arith.levenshtein( "latino","larou"  )


吐槽下：Python語法縮進真是蛋疼，用4個空格縮進來確定。累的很啊


我的本行iOS的我就不上代碼了，代碼風格太菜同行到笑話就不好了。可以看出是動態(tài)規(guī)劃解決編輯距離，明白算法原理寫出算法函數(shù)方法還是不難的；大概的公式也就是：例S1=“eeba”  S2="abac"


如果i=0且j=0        edit(0, 0)=1

如果i=0且j>0        edit(0, j )=edit(0, j-1)+1

如果i>0且j=0        edit( i, 0 )=edit(i-1, 0)+1

如果i>0且j>0        edit(i, j)=min(edit(i-1, j)+1, edit(i,j-1)+1, edit(i-1,j-1)+f(i , j) )


這就是將長字符串間的編輯距離問題一步一步轉換成短字符串間的編輯距離問題，直至只有1個字符的串間編輯距離為1

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/40875.html

相關文章

  • 編輯距離及編輯距離算法

    摘要：無意間看到了有人問編輯距離算法，當時對這個概念很陌生，也就去學習了下，做下總結，記錄下，好記性不如爛筆頭。編輯距離又稱距離，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數(shù)。 無意間看到了有人問編輯距離算法，當時對這個概念很陌生，也就去學習了下，做下總結，記錄下，好記性不如爛筆頭。 編輯距離（Edit Distance）：又稱Levenshtein距離，是指兩個字串之間，由一個...

    zollero 評論0 收藏0

  • 文本相似度 余弦值相似度算法 VS L氏編輯距離（動態(tài)規(guī)劃）

    摘要：本文對兩種文本相似度算法進行比較。余弦值相似度算法最小編輯距離法氏編輯距離基于詞條空間編輯距離，又稱距離，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數(shù)。但是同時也可以看出余弦相似度得到的結果相對比較高一些。 本文由作者祝娜授權網(wǎng)易云社區(qū)發(fā)布。 本文對兩種文本相似度算法進行比較。余弦值相似度算法 VS 最小編輯距離法1、L氏編輯距離（基于詞條空間）編輯距離（Edit Dist...

    fxp 評論0 收藏0

  • lucene的查詢與排序

    摘要：序本文主要記錄一下的另外兩個要點的使用查詢與排序。在指定距離可以找到第一個單詞的查詢。查詢的幾個語句之間保持者一定的距離。同時查詢幾個詞句查詢。從一個詞距查詢結果中，去除一個詞距查詢。 序 本文主要記錄一下lucene的另外兩個要點的api使用：查詢與排序。 查詢 完全匹配查詢 /** * 查找指定field中包含某個關鍵字 * @throws IOExcep...

    baoxl 評論0 收藏0

  • [轉載] Python的字符串相似度檢測

    摘要：要求和必須長度一致。是描述由一個字串轉化成另一個字串最少的操作次數(shù)，在其中的操作包括插入刪除替換。計算距離，其中的為的匹配長度，當某位置的認為匹配當該位置字符相同，或者在不超過是調換次數(shù)的一半計算距離原文相似度計算轉載自蔡尐的博客 安裝python-Levenshtein模塊 pip install python-Levenshtein 使用python-Levens...

    biaoxiaoduan 評論0 收藏0

  • [Leetcode] Edit Distance 最小編輯距離

    摘要：動態(tài)規(guī)劃復雜度時間空間思路這是算法導論中經(jīng)典的一道動態(tài)規(guī)劃的題。 Edit Distance Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You h...

    zhangke3016 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<