3

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

例如，如果字符串是“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' 的统计似然度）。

4

5 回答 5

5

动态编程解决方案（如果我理解正确的问题）：

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 2 )，因此很容易解决 N=20 的问题。

这是如何工作的：

  • 你将乘以probs['a']*probs['b']你的一切也将乘以probs['ab']
  • 由于乘法和加法的分配属性，您可以将这两者相加，并将这个单一的和乘以它的所有延续。
  • 对于每个可能的最后一个子串，它通过将其概率乘以先前路径的所有概率之和来添加以该子串结尾的所有拆分的总和。（替代措辞将不胜感激。我的 python 比我的英语好..）
于 2009-08-03T15:57:35.237 回答
3

一是profile找瓶颈。

如果瓶颈仅仅是大量可能的分区，我建议并行化，可能通过multiprocessing. 如果这还不够，您可以查看Beowulf集群。

如果瓶颈只是计算速度慢，请尝试使用 C。通过ctypes.

另外，我不确定你是如何存储分区的，但你可以通过使用一个字符串和一个后缀数组来减少内存消耗。如果您的瓶颈是交换和/或缓存未命中，那可能是一个巨大的胜利。

于 2009-08-03T15:40:49.370 回答
1

您的子字符串将被较长的字符串一遍又一遍地重用，因此使用记忆技术缓存值似乎是显而易见的尝试。这只是时空权衡。最简单的实现是在计算值时使用字典来缓存值。对每个字符串计算进行字典查找；如果它不在字典中，请计算并添加它。后续调用将使用预先计算的值。如果字典查找比计算快，那么你很幸运。

我知道您正在使用 Python，但是...作为可能感兴趣的旁注，如果您在 Perl 中执行此操作，您甚至不必编写任何代码；内置的Memoize 模块将为您做缓存！

于 2009-08-03T15:58:10.807 回答
1

您可能会通过基于算术（和字符串连接）的关联属性的小重构来稍微减少计算量，尽管我不确定它是否会改变生活。核心思想如下：

考虑一个较长的字符串，例如 'abcdefghik'，长度为 10，以保证不失一般性的确定性。在一种天真的方法中，您会将 p(a) 乘以 9 尾的许多分区，将 p(ab) 乘以 8 尾的许多分区，等等；特别是 p(a) 和 p(b) 将乘以与 p(ab) 完全相同的 8 尾分区（所有这些分区） - 3 个乘法和两个总和。所以考虑到这一点：

(p(ab) + p(a) * p(b)) * (partitions of the 8-tail)

这部分我们减少到 2 个乘法和 1 个总和，保存了 1 个乘积和 1 个总和。以“b”右侧的分割点覆盖所有分区。当涉及到“c”右侧的分割分区时，

(p(abc) + p(ab) * p(c) + p(a) * (p(b)*p(c)+p(bc)) * (partitions of the 7-tail)

节省更多，部分归功于内部重构——当然，必须小心重复计算。我认为这种方法可能是通用的——从中点开始，考虑所有在那里有分裂的分区，分别（和递归地）左右部分，相乘和相加；然后添加所有没有拆分的分区，例如在示例中，左边是“abcde”，右边是“fghik”，第二部分是关于“ef”在一起而不是分开——所以通过将'ef'视为一个新的'超字母'X来“折叠”所有概率，你会得到一个更短的字符串，'abcdXghik'（当然，那个子字符串的概率直接映射到原件，例如 G。新字符串中的 p(cdXg) 正是原始字符串中的 p(cdefg)。

于 2009-08-03T15:58:36.530 回答
0

您应该查看该itertools模块。它可以为您创建一个非常快的生成器。给定您的输入字符串，它将为您提供所有可能的排列。根据您的需要，还有一个combinations()发电机。我不太确定您在查看“abc”时是否正在查看“b|ca”，但无论哪种方式，这个模块都可能对您有用。

于 2009-08-03T16:16:28.670 回答