使用类似语法规则来缩减一个字符串

Question

我正在寻找一个适合简化字符串的DP算法。例如，我有一个字符串 a b a b 和一系列规则：

1. a b -> b
2. a b -> c
3. b a -> a
4. c c -> b

目的是使用这些规则获得可以从给定字符串中接收的所有单个字符。对于此示例，它将是b, c。给定字符串的长度可以高达200个符号。您能否提示一个有效的算法？

规则始终为2 -> 1。我想到了创建一个树的想法，根是给定的字符串，每个子节点是一个经过一次转换后的字符串，但我不确定这是否是最佳方法。

- user2875945

---

你需要展示一些努力。你考虑过如何解决这个问题吗？给我们你的想法。试试看吧。当你遇到困难时，向我们展示你尝试过什么，并解释问题所在。 - Jim Mischel

@Bas 可能是动态规划。 - Dialecticus

@cerkiewny 是的，规则总是2比1。没有最佳解决方案，目的是获得所有可能的解决方案。 - user2875945

@Jongware 'a b' 可以转换为 'b' 或 'c'，因此有两个规则。我不确定我是否正确理解了您的第二个问题，但如果 'b' 可以以两种不同的方式接收，那么唯一重要的是它可以被接收。 - user2875945

CKY 对于这个基本未修改的问题不会起作用吗？ - harold

Answer 1

对于一个DP问题，您总是需要理解如何通过小的子问题构建大问题的答案。假设您有一个名为simplify的函数，该函数以长度n的输入调用。有n-1种方法可以将输入分成第一部分和最后一部分。对于这些拆分中的每一个，您都应该在第一部分和最后一部分上递归调用您的simplify函数。长度为n的输入的最终答案是所有符合规则的第一部分和最后部分答案的可能组合的集合。

在Python中，可以这样实现：

rules = {'ab': set('bc'), 'ba': set('a'), 'cc': set('b')}
all_chars = set(c for cc in rules.values() for c in cc)

@ memoize
def simplify(s):
    if len(s) == 1:  # base case to end recursion
        return set(s)

    possible_chars = set()

    # iterate over all the possible splits of s
    for i in range(1, len(s)):
        head = s[:i]
        tail = s[i:]

        # check all possible combinations of answers of sub-problems
        for c1 in simplify(head):
            for c2 in simplify(tail):
                possible_chars.update(rules.get(c1+c2, set()))

                # speed hack
                if possible_chars == all_chars: #  won't get any bigger
                    return all_chars

    return possible_chars

快速检查：

In [53]: simplify('abab')
Out[53]: {'b', 'c'}

为了让这个算法能够处理大字符串（避免指数级别的时间复杂度），你应该使用记忆化装饰器。这是解决动态规划问题的关键步骤，否则你只是在进行蛮力计算。当possible_chars == set('abc')时，函数可以立即返回，因为此时你已经确定可以生成所有可能的结果，从而进一步提高速度。

时间复杂度分析：对于长度为n的输入，有O(n^2)个子问题，其中长度为n-1的子串有2个，长度为n-2的子串有3个，以此类推到长度为1的子串共有n个。由于记忆化，每个子问题最多只被调用一次。每个子问题的最大运行时间为O(n)，因为存在for i in range(len(s))循环，所以总运行时间最多为O(n^3)。

- Bas Swinckels

---

我对Python不太擅长，有几个问题。head = s[:i]; tail = s[i:] 这段代码是在索引 i 处将字符串分成两部分，还是从字符串的两端取 i 个字符？而 possible_chars.update(rules.get(c1+c2, set())) 是什么意思？ - user2875945

这是切片符号，s[:i] == s[0:i]，对应于前i个字符，而s[i:] == s[i:len(s)]则取除了前i个字符之外的所有字符。因此，对于输入abcd，循环i将把它分成head，tail = 'a'，'bcd'，head，tail = 'ab'，'cd'和head，tail ='abc'，'d'。 - Bas Swinckels

这是一种简洁的方式：连接字符 c1 和 c2，在规则字典中查找此组合的可能答案集，并将 possible_chars 设为其自身和规则中可能答案集的 并集。字典上的 get(key, default) 方法会在字典中查找某个键，如果未找到则返回默认值。我使用它来返回一个空集合 set()，以防这两个字母的组合不在规则中，因此与之的并集不起作用。 - Bas Swinckels

一个更明确的方法是写成 if c1+c2 in rules: possible_chars = possible_chars.union(rules[c1+c2])。 - Bas Swinckels

为了代码的完整性，我认为最好加入一个“memoize”的定义。或者这是从我不知道的某个Python库中取的？ - Adam Stelmaszczyk

Answer 2

如果你从右到左阅读这些规则，它们看起来就像上下文无关文法的规则，并且基本上具有相同的含义。你可以将一个自底向上的解析算法（例如Earley算法）应用于你的数据，以及一个适当的起始规则；例如：

start <- start a
       | start b
       | start c

然后只需检查解析森林中最短的一串start。当然，最坏情况仍然是O（n^3），但Earley算法现在相当有效。

您还可以在使用导数进行解析时生成解析森林。您可能能够高效地检查它们以获取start的短链。

- Jay Kominek

Answer 3

给定字符串长度为N，规则数量为R。

自上而下扩展树，在最坏情况下（输入字符串类型为aaa...且规则为aa -> a），计算复杂度为O(NR^N)。

证明：

树的根节点有(N-1)R个子节点，每个子节点有(N-1)R^2个子节点，...，每个叶子节点有(N-1)R^N个子节点。因此，总复杂度为O((N-1)R + (N-1)R^2 + ... (N-1)R^N) = O(N(1 + R^2 + ... + R^N)) = （使用二项式定理）= O(N(R+1)^N) = O(NR^N)。

这种朴素方法的递归Java实现：

public static void main(String[] args) {
    Map<String, Character[]> rules = new HashMap<String, Character[]>() {{
        put("ab", new Character[]{'b', 'c'});
        put("ba", new Character[]{'a'});
        put("cc", new Character[]{'b'});
    }};
    System.out.println(simplify("abab", rules));
}

public static Set<String> simplify(String in, Map<String, Character[]> rules) {
    Set<String> result = new HashSet<String>();
    simplify(in, rules, result);
    return result;
}

private static void simplify(String in, Map<String, Character[]> rules, Set<String> result) {
    if (in.length() == 1) {
        result.add(in);
    }
    for (int i = 0; i < in.length() - 1; i++) {
        String two = in.substring(i, i + 2);
        Character[] rep = rules.get(two);
        if (rep != null) {
            for (Character c : rep) {
                simplify(in.substring(0, i) + c + in.substring(i + 2, in.length()), rules, result);
            }
        }
    }
}

---

Bas Swinckels的O(RN^3) Java实现（使用HashMap作为记忆化缓存）：

public static Set<String> simplify2(final String in, Map<String, Character[]> rules) {
    Map<String, Set<String>> cache = new HashMap<String, Set<String>>();
    return simplify2(in, rules, cache);
}

private static Set<String> simplify2(final String in, Map<String, Character[]> rules, Map<String, Set<String>> cache) {
    final Set<String> cached = cache.get(in);
    if (cached != null) {
        return cached;
    }
    Set<String> ret = new HashSet<String>();
    if (in.length() == 1) {
        ret.add(in);
        return ret;
    }
    for (int i = 1; i < in.length(); i++) {
        String head = in.substring(0, i);
        String tail = in.substring(i, in.length());
        for (String c1 : simplify2(head, rules)) {
            for (String c2 : simplify2(tail, rules, cache)) {
                Character[] rep = rules.get(c1 + c2);
                if (rep != null) {
                    for (Character c : rep) {
                        ret.add(c.toString());
                    }
                }
            }
        }
    }
    cache.put(in, ret);
    return ret;
}

---

两种方法的输出结果：

[b, c]

- Adam Stelmaszczyk

---

我在Java方面并不是非常熟练，但你的第二种实现是否使用了记忆化（即缓存固定输入的结果）呢？如果没有，那么它不是O(n^3)，而是指数级别的。 - Bas Swinckels

谢谢，两个算法都完美地运行了，但我需要一些优化的帮助。第二个算法很快，但我需要它更快一点。也许你可以给我一些优化建议，例如使用更快的数据结构或更有效的循环？ - user2875945

@user2875945，我没有实现Bas Swinckels的“加速技巧”（请查看他的代码），这应该有助于提高性能。 - Adam Stelmaszczyk