python - 是否有任何巧妙有效的算法来对字符串的分区空间执行计算？

Question

我正在从事一个统计项目，该项目涉及迭代所有可能的方法来划分字符串集合，并对每个字符串运行简单的计算。具体来说，每个可能的子串都有一个与之关联的概率，我试图获得分区中子串概率乘积的所有分区的总和。

例如，如果字符串是“abc”，则“a”、“b”、“c”、“ab”、“bc”和“abc”的概率。字符串有四种可能的分区:'abc'、'ab|c'、'a|bc' 和 'a|b|c'。该算法需要找到每个分区的组件概率的乘积，然后将四个结果相加。

目前，我已经编写了一个 python 迭代器，它使用整数的二进制表示作为分区(例如，上面示例中的 00、01、10、11)并简单地遍历整数。不幸的是，这对于超过 20 个字符的字符串来说非常慢。

有人能想出一种巧妙的方法来执行此操作，而无需一次一个地遍历每个分区吗？我已经坚持了好几天了。

为了回应一些评论，这里有更多信息:
该字符串几乎可以是任何内容，例如“foobar(foo2)”——我们的字母表是小写字母数字加上所有三种类型的大括号(“(”、“[”、“{”)、连字符和空格。
目标是在给定单个“单词”可能性的情况下获得字符串的可能性。所以 L(S='abc')=P('abc') + P('ab')P('c') + P('a')P('bc') + P('a')P ('b')P('c') (这里"P('abc')"表示'词''abc'的概率，而"L(S='abc')"是观察的统计似然字符串“abc”)。

Answer 1

A Dynamic Programming解决方案(如果我理解正确的话):

def dynProgSolution(text, probs):
  probUpTo = [1]
  for i in range(1, len(text)+1):
    cur = sum(v*probs[text[k:i]] for k, v in enumerate(probUpTo))
    probUpTo.append(cur)
  return probUpTo[-1]

print dynProgSolution(
  'abc',
  {'a': 0.1, 'b': 0.2, 'c': 0.3,
   'ab': 0.4, 'bc': 0.5, 'abc': 0.6}
  )

复杂度为 O(N²) 所以很容易解决 N=20 的问题。

这是如何工作的:

• 您将乘以 probs['a']*probs['b'] 的所有内容您还将乘以 probs['ab']
• 感谢 Distributive Property乘法和加法，您可以将这两者相加，然后将这个总和乘以它的所有延续。
• 对于每个可能的最后一个子字符串，它通过将其概率乘以先前路径的所有概率之和来添加以该子字符串结尾的所有拆分的总和。 (其他措辞将不胜感激。我的 python 比我的英语好..)