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

Question

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

我尝试编写朴素的方法(对于所有可能的替换，对于所有有效位置，在该位置应用替换后递归输入的副本。返回所有有效递归和输入中最短的，缓存在捕获等效替换序列的函数)，但它(无法正常工作)很慢，而且我很确定这是一个算法问题，而不是实现。

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

• Token是枚举类型。
• map中每个entry的输出长度严格小于entry的输入。
• 我不需要需要替换的内容和位置，只需要生成的序列。

因此，作为一个示例，其中每个字符都是一个标记(为简单起见)，如果我将替换映射作为 aaba -> a, aaa -> ab，和 aba -> bb，我应用了 minimalString('aaaaa')，我想得到 '一个'.

实际的方法签名如下:

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