對於不完整的弦是否有修改的最小編輯距離（Levenshteina距離）？

Question

我的序列是從0和1開始構建的。我想以某種方式測量它們與目標字符串的距離。但目標字符串不完整。

數據我有，其中，x是目標串，的實施例中，[0]表示的至少一個'0'的次數：

x =11[0]1111[0]1111111[0]1[0]`, the length of x is fixed and eaquel to length of y. 

y1=11110111111000000101010110101010111 

y2=01101000011100001101010101101010010 
all y's have the same length 

很容易地看到，x可以確實解釋爲字符串集，但是這個集合可能非常大，可能只需要從該集合中抽取樣本，並取平均最小編輯距離，但這又是一個大計算問題。

我試圖找出算法中，但我疊，它的步驟是這樣的： X - 目標字符串 - 模糊一片，

Ÿ - 第二個字符串 - 固定 CX1，CY1 - 數字那些在x和y的 GX1，GY1 - 載體的列表，每個列表的長度是等於那些在給定序列的羣的數目，

GX1 [I]的第i個矢量，

GX1 [ i] =（第i組的第1組，第i組的長度）

如果GX1和GY1的長度相同，則我們知道有多少的人添加或從每個組中刪除，但有一個問題，因爲我不知道，如果簡單的添加和刪除也給出了最小距離

Answer 1

我會建議你使用dynamic programming這個。 dp是二維的：xi - 您所在的xpattern字符串中的索引，yi - 您所在的y字符串中的索引，每個子問題的值是子串x [xi..x之間的最小編輯距離。 size-1]和y [yi ... y.size-1]。

下面介紹如何在解釋固定y字符串時給出x模式之間的最小編輯距離。我將假設x-模式中的符號@表示任意正數的零。此外，我將使用一些全局變量來使代碼更易於閱讀。

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


const int max_len = 1000; 
const int NO_SOLUTION = -2; 
int dp[max_len][max_len]; 

string x; // pattern; 
string y; // to compute minimum edit distance to 
int solve(int xi /* index in x */, int yi /* index in y */) { 
    if (yi + 1 == y.size()) { 
    if (xi + 1 != x.size()) { 
     return dp[xi][yi] = NO_SOLUTION; 
    } else { 
     if (x[xi] == y[yi] || (y[yi] == '0' && x[xi] == '@')) { 
     return dp[xi][yi] = 0; 
     } else { 
     return dp[xi][yi] = 1; // need to change the character 
     } 
    } 
    } 
    if (xi + 1 == x.size()) { 
    if (x[xi] != '@') { 
     return dp[xi][yi] = NO_SOLUTION; 
    } 
    int number_of_ones = 0; 
    for (int j = yi; j < y.size(); ++j) { 
     if (y[j] == '1') { 
     number_of_ones++; 
     } 
    } 
    return dp[xi][yi] = number_of_ones; 
    } 
    int best = NO_SOLUTION; 
    if (x[xi] != '@') { 
    int temp = ((dp[xi + 1][yi + 1] == -1)?solve(xi + 1, yi +1):dp[xi + 1][yi +1]); 
    if (temp != NO_SOLUTION && x[xi] != y[yi]) { 
     temp++; 
    } 
    best = temp; 
    } else { 
    int temp = ((dp[xi + 1][yi + 1] == -1)?solve(xi + 1, yi +1):dp[xi + 1][yi +1]); 
    if (temp != NO_SOLUTION) { 
     if (y[yi] != '0') { 
     temp++; 
     } 
     best = temp; 
    } 

    int edit_distance = 0; // number of '1' covered by the '@' 

    // Here i represents the number of chars covered by the '@' 
    for (int i = 1; i < y.size(); ++i) { 
     if (yi + i >= y.size()) { 
     break; 
     } 
     int temp = ((dp[xi][yi + i] == -1)?solve(xi, yi + i):dp[xi][yi + i]); 
     if (temp == NO_SOLUTION) { 
     continue; 
     } 
     if (y[yi] != '0') { 
     edit_distance++; 
     } 
     temp += edit_distance; 
     if (best == NO_SOLUTION || temp < best) { 
     best = temp; 
     } 
    } 
    } 
    return best; 
} 

int main() { 
    memset(dp, -1, sizeof(dp)); 
    cin >> x >> y; 
    cout << "Minimum possible edit distance is: " << solve(0,0) << endl; 
    return 0; 
} 

希望這會有所幫助。

Answer 2

設（Q，Σ，δ，Q ，F）是目標自動機，它接受一個正則語言L＆subseteq; Σ ^*，並讓w ∈ Σ ^*是源字符串。你想計算最小值 _{x ∈ d} d（x，w），其中d表示Levenshtein距離。

我的方法是推廣通常的動態程序。設D是由Q × {0，＆hellip; | w |}索引的表格。在計算的結尾，d（Q，I）將是

分鐘 _{X：δ（Q ，X）= Q} d（X，W [0＆hellip; I]），

其中w [0]表示w的長度 - （i + 1）前綴。換句話說，D（q，i）是w [0]和離開處於q狀態的自動機的字符串之間的距離。整體答案是

分鐘 _{q ∈˚F} d（Q，| W |），

或W和組離開自動機中的最終狀態中的一個字符串，即之間的距離，語言L.

---

d的第一列包含條目d的（q，0）爲每一個狀態q ∈ Q.由於每串x ∈ Σ ^*它認爲d（X， ＆epsilon;）= | x |，條目D（q， 0）是由轉換函數δ定義的圖中q從q 到q的最短路徑的長度。通過運行來自q （實際上僅僅是廣度優先搜索，因爲邊長全部爲1）的「Dijkstra算法」來計算這些條目。

D的後續列從前一列計算。首先通過最小化幾種可能性來計算輔助量D'（q，i）。

精確匹配對於每一個狀態R ∈ Q如下δ（R，W [1]）= Q，包括d（R，I - 1）。

缺失包含d（Q，I - 1）+ 1

換人對於每一個狀態R ∈ Q和每個字母一個∈ Σ＆setminus; {r [i]}使得δ（r，a）= q包括D（r，i-1）+1。

請注意，我已經排除了插入。與第一列一樣，這是因爲可能需要在此處插入許多字母。爲了從D'（i，q）s計算D（i，q）s，在具有頂點Q的隱式圖上運行Dijkstra，並且對於每個q'邊長爲D'（i， q）從超級源s到q，並且對於每個q ∈ Q和一個∈ Σ，長度爲1的邊從q到δ（q，a）。設D（i，q）爲最終距離。

---

我相信這個算法，如果能實現得很好（有專門的支持Dijkstra算法與單位長度堆），具有運行時間O（| Q | | W^| | Σ |），其中，對於小字母與通常的Levenshtein DP相當。