0

我已经从 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 - 目标字符串 - 模糊之一，

y - 第二个字符串 - 固定 Cx1, Cy1 - x 和 y 中的个数 Gx1, Gy1 - 向量列表，每个列表的长度等于给定序列中的组数，

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 表示 Levenshtein 距离。

我的方法是概括通常的动态程序。令 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 与使自动机处于最终状态之一的字符串集之间的距离，即语言 L。

D 的第一列由每个状态 q ∈ Q 的条目 D(q, 0) 组成。因为对于每个字符串 x ∈ Σ *它都认为 d(x, ε) = |x|，所以条目 D(q, 0) 是由转移函数 δ 定义的图中从 q 0到 q的最短路径的长度。通过从 q 0运行“Dijkstra 算法”来计算这些条目（实际上只是广度优先搜索，因为边长都是 1）。

D 的后续列是根据前一列计算的。首先通过最小化几种可能性来计算辅助量 D'(q, i)。

精确匹配对于每个状态 r ∈ Q 使得 δ(r, w[i]) = q，包括 D(r, i - 1)。

删除包括 D(q, i - 1) + 1。

代入对于每个状态 r ∈ Q 和每个字母 a ∈ Σ ∖ {w[i]} 使得 δ(r, a) = q，包括 D(r, i - 1) + 1。

请注意，我省略了Insertion。与第一列一样，这是因为可能需要在此处插入许多字母。要从 D'(i, q)s 计算 D(i, q)s，请在具有顶点 Q ∪ {s} 的隐式图上运行 Dijkstra，并且对于每个 q ∈ Q，边长为 D'(i, q) 从超级源 s 到 q，并且对于每个 q ∈ Q 和 a ∈ Σ，从 q 到 δ(q, a) 的边长度为 1。令 D(i, q) 为最终距离。

我相信这个算法，如果实现得好（使用专门支持具有单位长度的 Dijkstra 的堆），运行时间为 O(|Q||w||Σ|)，对于小字母 Σ，它与通常的Levenshtein DP。

于 2012-04-21T13:46:18.500 回答
0

我建议您为此使用动态编程。dp 是二维的：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 回答