字符串分析

Question

给定一系列操作:

A*B*A*B*A*A*B*A*B

有没有办法获得最佳细分以启用子串的重用.

制造

a*b*a*b*a*a*b*a*b => c*a*c,其中c = a*b*a*b

然后看到了

a*b*a*b => d*d,其中d = a*b

总而言之,将8个初始操作减少到这里描述的4个？

(c =(d = a*b)*d)*a*c

当然,目标是尽量减少操作次数

我正在考虑各种后缀.

我对线性时间启发式或解决方案特别感兴趣.'*'操作实际上是矩阵乘法.

Answer 1

整个问题被称为"常见的表达消除"或CSE.它是函数式编程语言编译器实现者面临的一个稍微小一点的问题,称为" 图形缩减 ".谷歌搜索"常见的Subexpression消除算法"提供了许多解决方案,但我没有看到特别是矩阵乘法给出的约束.

链接的页面提供了大量的参考.

我的回答如下.但是,经过多方面的研究,解决方案只是构建一个后缀树.这可以在O(N)时间内完成(维基百科页面上的大量参考文献).完成此操作后,子表达式(问题中的c,d等)只是后缀树中的节点 - 只需将它们拉出即可.

但是,我认为MarcoS正在寻找具有最长重复子字符串的建议,因为图形缩减优先级可能不允许在此处允许的优化.

算法草图:

optimise(s):
    let sub = longestRepeatingSubstring(s).
    optimisedSub = optimise(sub)
    return s with sub replaced by optimisedSub

每次运行最长的重复子字符串需要时间N.您可以重新使用您构建的后缀树来及时解决N的问题.

Answer 2

编辑:除了接受的答案之外,还需要此答案中的增长顺序才能运行CSE或矩阵链乘法

有趣的是,压缩算法可能是你想要的:压缩算法试图减少它压缩的大小,如果它能做到的唯一方法就是替换,你可以跟踪它并为你的算法获得必要的子组件.对于小输入,这可能不会给出好的结果.

在选择这样的算法时,您的操作的哪些子集是可交换的将是重要的考虑因素.[编辑:OP表示在他/她的情况下没有任何操作是可交换的]

如果我们忽略缓存等效果,我们也可以定义最佳解决方案:

input: [some product of matrices to compute]

given that multiplying two NxN matrices is O(N^2.376)
given we can visualize the product as follows:
    [[AxB][BxC][CxD][DxE]...]
we must for example perform O(max(A,B,C)^2.376) or so operations in order to combine
    [AxB][BxC] -> [AxC]

The max(...) is an estimate based on how fast it is to multiply two square matrices;
a better estimate of cost(A,B,C) for multiplying an AxB * BxC matrix can be gotten 
from actually looking at the algorithm, or running benchmarks if you don't know the
algorithm used.

However note that multiplying the same matrix with itself, i.e. calculating
a power, can be much more efficient, and we also need to take that into account.
At worst, it takes log_2(power) multiplies each of O(N^2.376), but this could be
made more efficient by diagonalizing the matrix first.

关于贪婪方法是否可行的问题是:一个人是否应该在每个步骤压缩重复的子串.例如,情况可能并非如此

aaaaabaab
compressing 'aa' results in ccabcb and compressing 'aab' is now impossible

但是我有一种预感,如果我们尝试所有压缩子串的命令,我们可能不会经常遇到这个问题.

因此,写下我们想要的东西(成本)并考虑可能的问题,我们已经有了一个可以做到这一点的强力算法,并且它将运行非常少量的矩阵:

# pseudocode

def compress(problem, substring)
    x = new Problem(problem)
    x.string.replaceall(substring, newsymbol)
    x.subcomputations += Subcomputation(newsymbol=substring)

def bestCompression(problem)
    candidateCompressions = [compress(problem,substring) for each substring in problem.string]
    # etc., recursively return problem with minimum cost
    # dynamic programming may help make this more efficient, but one must watch
    #   out for the note above, how it may be hard to be greedy

注意:根据Asgeir的另一个答案,这被称为矩阵链乘法优化问题.Nick Fortescue指出,这也被称为http://en.wikipedia.org/wiki/Common_subexpression_elimination - 因此可以从文献中找到任何通用的CSE或矩阵链乘法算法/库,并插入成本我前面提到过的数量级(你需要那些使用的解决方案).请注意,上述计算(乘法,取幂等)的成本假设它们使用最先进的算法有效地完成; 如果不是这种情况,请用适当的值替换指数,这些值对应于操作的执行方式.

Answer 3

如果你想使用最少的算术运算那么你应该看看矩阵链乘法,它可以减少到O(n log n)

Answer 4

从头顶看,NP中的问题似乎对我而言.根据您正在进行的替换,其他替代将是可能的或不可能的,例如对于字符串 d*e*a*b*c*d*e*a*b*c*d*e*a有几种可能性.

如果你采用最长的常用字符串,它将是:f = d*e*a*b*c你可以替换为最后f*f*e*a留下三次乘法和四次中间串 (总共七次).

如果您改为使用以下方式替换: f = d*e*a您f*b*c*f*b*c*f可以使用g = f*b*cto 进一步替换g*g*f为总共六次乘法.

这个问题还有其他可能的替代,但我现在没时间计算它们.

我猜测一个完整的最小替换,不仅需要找出最长的公共子串,而且还需要找出每个子串重复的次数,这可能意味着你必须跟踪到目前为止的所有替换并进行回溯.它仍然可能比实际乘法更快.

Answer 5

这不是最长的重复子串问题吗？