algorithm - 对于不完整的字符串，是否有修改过的最小编辑距离(Levenshteina Distance)？

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 - 目标字符串 - 模糊的，

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

Gx1[i] 第i个向量，

Gx1[i]=(第i组的第一个，第i组的长度)

如果 Gx1 和 Gy1 的长度相同，那么我们就知道要从每个组中添加或删除多少个，但是有一个问题，因为我不知道简单的添加和删除是否给出了最小距离

Answer 1

令 (Q, Σ, δ, q₀, F) 为目标自动机，它接受常规语言 L ⊆ Σ^*，并令 w ∈ Σ ^* 是源字符串。您想计算 min_{x ∈ L} d(x, w)，其中 d 表示 Levenshtein 距离。

我的方法是概括通常的动态程序。设 D 是由 Q × {0, …, |w|} 索引的表。在计算结束时，D(q, i) 将是

min_{x : δ(q0, 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₀到q的最短路径的长度。通过从 q₀ 运行“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.

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

---

我相信这个算法，如果实现得好(有一个专门支持单位长度的 Dijkstra 的堆)，运行时间为 O(|Q| |w| |Σ|)，对于小字母 Σ，这是可比较的到通常的 Levenshtein DP。