0

私は0と1から構築されたシーケンスを持っています。どういうわけか、ターゲットストリングからの距離を測定したいと思います。しかし、ターゲット文字列は不完全です。

私が持っているデータの例。ここで、xはターゲット文字列です。ここで、[0]は少なくとも1つの出現を意味します'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-ターゲット文字列-ファジーなもの、

y-2番目の文字列-固定Cx1、Cy1-xおよびyの1の数Gx1、Gy1-ベクトルのリスト、各リストの長さは、指定されたシーケンスの1のグループの数に等しい。

Gx1 [i] i番目のベクトル、

Gx1 [i] =（i番目のグループの最初のもの、i番目のグループの長さ）

Gx1とGy1の長さが同じである場合、各グループに追加または削除するものの数はわかりますが、単純な追加と削除で最小距離が得られるかどうかわからないため、問題があります。

4

2 に答える 2

1

(Q, Σ, δ, q 0 , F) をターゲット オートマトンとし、正規言語 L ⊆ Σ *を受け入れ、 w ∈ Σ *をソース文字列とします。min x ∈ L d(x, w)を計算したいとします。ここで、d はレーベンシュタイン距離を示します。

私のアプローチは、通常の動的プログラムを一般化することです。D を Q × {0, …, |w|} でインデックス付けされたテーブルとする。計算の最後に、D(q, i) は次のようになります。

最小x : δ(q 0 , x) = q d(x, w[0…i]),

ここで、w[0…i] は、w の長さ (i + 1) のプレフィックスを示します。言い換えれば、D(q, i) は w[0…i] と状態 q でオートマトンを離れる文字列のセットとの間の距離です。全体的な答えは

min q ∈ F D(q, |w|),

または w と、オートマトンを最終状態の 1 つ、つまり言語 L に残す文字列のセットとの間の距離。

D の最初の列は、すべての状態 q ∈ Q のエントリ D(q, 0) で構成されます。すべての文字列 x ∈ Σ *について、d(x, ε) = |x| が成り立つため、エントリ D(q, 0) は、遷移関数 δ によって定義されるグラフのq 0から qまでの最短経路の長さです。q 0から「ダイクストラのアルゴリズム」を実行して、これらのエントリを計算します(実際には、辺の長さがすべて 1 であるため、幅優先探索のみです)。

D の後続の列は、前の列から計算されます。最初に、いくつかの可能性を最小化することによって、補助量 D'(q, i) を計算します。

完全一致δ(r, w[i]) = q となるすべての状態 r ∈ Q について、D(r, i - 1) を含めます。

削除には D(q, i - 1) + 1 が含まれます。

代入δ(r, a) = q となるすべての状態 r ∈ Q およびすべての文字 a ∈ Σ ∖ {w[i]} について、D(r, i - 1) + 1 を含めます。

Insertionを省略していることに注意してください。最初の列と同様に、これはここに多くの文字を挿入する必要がある場合があるためです。D'(i, q) から D(i, q) を計算するには、頂点 Q ∪ {s} と、すべての q ∈ Q について、長さ D'(i, q) スーパーソース s から q まで、およびすべての q ∈ Q および a ∈ Σ について、q から δ(q, a) までの長さ 1 のエッジ。D(i, q) を最終的な距離とします。

このアルゴリズムが適切に実装された場合 (ユニット長のダイクストラをサポートするように特化されたヒープを使用して)、実行時間は O(|Q| |w| |Σ|) になり、小さなアルファベット Σ の場合、通常のアルゴリズムに匹敵すると思います。レーベンシュタインDP。

于 2012-04-21T13:46:18.500 に答える
0

これには動的計画法を使用することをお勧めします。dpは2次元です：xi-現在のxpattern文字列のインデックスとyi-現在のy文字列のインデックスであり、各サブ問題の値は、サブ文字列x[xi..x間の最小編集距離です。 size-1]およびy[yi...y.size-1]。

固定されたy文字列を説明するときに、与えられたaxパターン間の最小編集距離を見つける方法は次のとおりです。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;
}

お役に立てれば。

于 2012-04-21T13:04:59.180 に答える