迭代字符串替换后可能的最短结果长度

Question

如何合理有效地找到通过重复应用替换输入序列给出的最短可能输出？我相信(如果我错了,请纠正我),这是最坏情况下的指数时间,但由于下面的第二个限制,我不确定.天真的方法当然是.

我尝试编写天真的方法(对于所有可能的替换,对于所有有效位置,在该位置应用替换后递归输入的副本.返回所有有效递归中的最短和输入,并在函数上使用缓存捕获等效的替换序列),但它(不可行)缓慢,我很确定这是一个算法问题而不是实现.

可能(或可能不)产生影响的一些事情:

• 令牌是枚举类型.
• 地图中每个条目的输出长度严格小于条目的输入.
• 我并不需要做了哪里,只是结果序列什么替代品.

所以,作为一个例子,每个字符都是一个标记(为了简单起见),如果我有替换地图为aaba- > a,aaa- > ab和aba- > bb,我应用minimalString('aaaaa'),我想得到'a ".

实际的方法签名大致如下:

List<Token> getMinimalAfterReplacements(List<Token> inputList, Map<List<Token>, List<Token>> replacements) {
    ?
}

有比蛮力更好的方法吗？如果没有,例如,是否有可以利用的SAT库或类似物？是否有任何地图预处理可以通过不同的令牌列表多次调用但使用相同的替换映射来使其更快？

Answer 1

下面的代码是一个 Python 版本，用于查找尽可能短的缩减。它是非递归的，但与朴素算法相差不远。在每一步中，它都会尝试所有可能的单次归约，从而获得一组字符串以供下一步归约。

当存在“aa”->“a”等“符号吃掉”规则时，一种有用的优化是检查下一组字符串是否有重复项。

另一种优化（未在下面的代码中实现）是将替换规则处理为有限自动机，该自动机通过输入字符串的单次传递找到所有可能的单次归约的位置。但这对主树搜索算法的指数性质没有帮助。

class Replacer:
  def __init__(self, replacements):
    self.replacements = [[tuple(key), tuple(value)] for key, value in replacements.items()]

  def get_possible_replacements(self, input):
    "Return all possible variations where a single replacement was done to the input"
    result = []
    for replace_what, replace_with in self.replacements:
      #print replace_what, replace_with
      for p in range(1 + len(input) - len(replace_what)):
        if input[p : p + len(replace_what)] == replace_what:
          input_copy = list(input[:])
          input_copy[p : p + len(replace_what)] = replace_with
          result.append(tuple(input_copy))
    return result

  def get_minimum_sequence_list(self, input):
    "Return the shortest irreducible sequence that can be obtained from the given input"
    irreducible = []
    to_reduce = [tuple(input)]
    to_reduce_new = []
    step = 1
    while to_reduce:
      print "Reduction step", step, ", number of candidates to reduce:", len(to_reduce)
      step += 1
      for current_input in to_reduce:
        reductions = self.get_possible_replacements(current_input)
        if not reductions:
          irreducible.append(current_input)
        else:
          to_reduce_new += reductions
      to_reduce = set(to_reduce_new[:]) # This dramatically reduces the tree width by removing duplicates
      to_reduce_new = []

    irreducible_sorted = sorted(set(irreducible), key = lambda x: len(x))
    #print "".join(input), "could be reduced to any of", ["".join(x) for x in irreducible_sorted]
    return irreducible_sorted[0]

  def get_minimum_sequence(self, input):
    return "".join(self.get_minimum_sequence_list(list(input)))

input = "aaaaa"

replacements = {
  "aaba" : "a",
  "aaa" : "ab",
  "aba" : "bb",
}

replacer = Replacer(replacements)
replaced = replacer.get_minimum_sequence(input)
print "The shortest string", input, "could be reduced to is", replaced