从加权集中按权重顺序生成长度 L 的前 N ​​个组合

Question

我有一组带有权重的字母，这给出了它们出现在字符串中的概率：

a - 0.7
b - 0.1
c - 0.3
...
z - 0.01

因此，该词的aaaa概率为0.7*0.7*0.7*0.7 = 0.24。这个词aaac就有概率了0.7*0.7*0.7*0.3 = 0.10。同一单词的所有排列都有相同的概率，因此我们只需要担心组合。

我想按概率顺序生成第一个N长度唯一的字符串L（例如，这里有 4 个字母，长度为 4，应该是aaaa, aaac, aacc, aaab, accc, aabc,cccc等）。

假设生成所有组合及其概率并按权重排序的强力方法在这里是不可能的。该算法（如果存在）必须能够适用于任何集合大小和任何长度的字符串（例如，具有加权概率的所有 256 个字节、1024 长度的字符串，生成第一个万亿。）

Answer 1

下面是一些使用堆的枚举代码。实现原理与user3386109在评论中提出的略有不同。

\n

按概率递减对符号进行排序。\xe2\x80\x99 在 S 符号的长度为 L 的组合与长度为 S + L \xe2\x88\x92 1 和 L \xe2\x88\x92 1 个零的二进制字符串之间存在建设性的一一对应关系（使用 L \xe2\x88\x92 1 分隔符计算一元中的每个符号）。我们可以一次一点地枚举后者的可能性。

\n

让我们不必枚举每个组合的部分是，对于每个二进制前缀，可以通过重复仍然可用的最可能的字母来找到最可能的单词。通过将前缀存储在堆中，我们可以只打开出现在前 N 中的前缀。

\n

请注意，这使用的内存与枚举组合的数量成正比。这可能仍然太多，在这种情况下，您可能需要迭代加深深度优先搜索之类的东西。

\n

symbol_probability_dict = {"a": 0.7, "b": 0.1, "c": 0.3, "z": 0.01}\nL = 4\n\nimport heapq\nimport math\n\nloss_symbol_pairs = [(-math.log(p), c) for (c, p) in symbol_probability_dict.items()]\nloss_symbol_pairs.sort()\n\nheap = [(0, 0, "")]\nwhile heap:\n    min_loss, i, s = heapq.heappop(heap)\n    if len(s) < L:\n        heapq.heappush(heap, (min_loss, i, s + loss_symbol_pairs[i][1]))\n        if i + 1 < len(loss_symbol_pairs):\n            heapq.heappush(\n                heap,\n                (\n                    min_loss\n                    + (L - len(s))\n                    * (loss_symbol_pairs[i + 1][0] - loss_symbol_pairs[i][0]),\n                    i + 1,\n                    s,\n                ),\n            )\n    else:\n        print(s)\n

\n

输出：

\n

aaaa\naaac\naacc\naaab\naccc\naacb\ncccc\naccb\naabb\naaaz\ncccb\nacbb\naacz\nccbb\nabbb\naccz\naabz\ncbbb\ncccz\nacbz\nbbbb\nccbz\nabbz\naazz\ncbbz\naczz\nbbbz\ncczz\nabzz\ncbzz\nbbzz\nazzz\nczzz\nbzzz\nzzzz\n

\n