algorithm - 从字典中查找所有子序列

Question

在一个程序中，我需要有效地回答以下形式的查询:

给定一组字符串 A 和一个查询字符串 q 返回所有 s ∈ A 使得 s 是 q 的子序列例如，给定 A = {"abc", "aaa", "abd"} 和 q = "abcd"，应返回 "abc"和 "abd"。

有没有比迭代 A 的每个元素并检查它是否是 q 的子序列更好的方法？

注意:我想到了 STRIPS 规划器或自动规划器。 STRIPS 规划器中的每个状态都是一组命题，如 {"(room rooma)"、"(at-robby rooma)"、"(at ball1 rooma)"}。我想找到适用于给定状态的所有地面 Action 。 STRIPS planner 中的 Action 基本上由两部分组成，先决条件和效果(这里并不真正相关)。先决条件是将 Action 应用于状态所需的一组命题。例如，要应用一个 Action “(move rooma roomb)”，它的先决条件 {"(room rooma)", "(room roomb)","(at-robby rooma)"} 必须在状态中全部为真。

Answer 1

如果您的集合 A 很大并且您有很多查询，您可以实现 trie-like structure ，其中级别 n 指的是字符串中的字符 n。在你的例子中:

trie = {
    a: {
        a: {
             a: { value: "aaa"}
        },
        b {
             c: { value: "abc"},
             d: { value: "abd"}
        }        
    }
}

这将使您能够通过 trie 查找 fork 路径中的匹配项:

function query(trie, q) {
    s = Set();

    if (q.isEmpty()) {
        if (trie.value) s.add(t.value);
    } else {
        s = s.union(query(trie, q[1:]));

        c = substr(q, 0, 1);
        if (t[c]) {
            s = s.union(query(t[c], substr(q, 1));
        }
    }
    return s;
}

实际上，您将生成 m 个字符的查询字符串的所有 2^m 个子集，但实际上，trie 是稀疏的，您最终检查的路径更少.

速度返回伴随着许多查找。构建 trie 比进行蛮力查找的成本更高。但是，如果您只构建一个 trie，或者有办法在更新集合 A 时更新 trie，您将获得良好的查找性能。

trie 节点的实际数据结构取决于项目可以有多少个可能的元素。在您的示例中，仅使用了四个字母。如果您的“字母”范围有限，则可以使用数组。否则你可能需要一种字典，这可能会使树在内存中变得非常大。