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

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')"表示概率'word''abc',而"L(S ='abc')"是观察字符串'abc'的统计可能性.

Answer 1

一个动态规划的解决方案(如果我理解问题的权利):

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']
• 由于乘法和加法的分配属性,你可以将这两个加在一起,并将这个单独的和乘以它的所有连续.
• 对于每个可能的最后一个子字符串,它通过将其概率乘以先前路径的所有概率的总和来添加以该结尾的所有拆分的总和.(另外的措辞将不胜感激.我的python比我的英语好...)