python - python中Burrows-Wheeler的性能问题

Question

我试图实现 Burrows-Wheeler在python中转换。 (这是网课的作业之一，但希望自己做了一些功课，才有资格求助)。

该算法的工作原理如下。取一个以特殊字符(在我的例子中是 $)结尾的字符串，并从这个字符串创建所有循环字符串。按字母顺序对所有这些字符串进行排序，特殊字符总是小于任何其他字符。在此之后获取每个字符串的最后一个元素。

这给了我一个单行:

''.join([i[-1] for i in sorted([text[i:] + text[0:i] for i in xrange(len(text))])]

对于相当大的字符串(这足以解决问题)，这是正确且相当快的:

 60 000 chars - 16 secs
 40 000 chars - 07 secs
 25 000 chars - 02 secs

但是当我试图处理一个包含数百万个字符的非常大的字符串时，我失败了(处理时间太长)。

我认为问题在于在内存中存储了太多字符串。

有什么办法可以克服这个问题吗？

附言只是想指出这也可能看起来像一个家庭作业问题，我的解决方案已经通过了评分者，我只是在寻找一种方法来让它更快。此外，我不会破坏其他人的乐趣，因为如果他们想找到解决方案，维基文章中有一个与我的类似。我也查了 this questio n 听起来很相似，但回答了一个更难的问题，如何解码用这个算法编码的字符串。

Answer 1

用长字符串制作所有这些字符串切片需要很长时间。它至少是 O(N^2)(因为您创建了 N 个长度为 N 的字符串，并且每个字符串都必须从原始数据中复制到内存中)，这会破坏整体性能并使排序变得无关紧要。更不用说内存要求了!

下一个想法不是对字符串进行实际切片，而是对用于创建循环字符串的 i 值进行排序，按照结果字符串的比较顺序 - 无需实际创建它。事实证明这有点棘手。 (在这里删除/编辑了一些错误的内容；请参阅@TimPeters 的回答。)

我在这里采用的方法是绕过标准库 - 这使得很难(尽管并非不可能)“按需”比较这些字符串 - 并进行我自己的排序。这里算法的自然选择是 基数排序 ，因为无论如何我们都需要一次考虑一个字符的字符串。

让我们先设置一下。我正在为 3.2 版编写代码，所以请品尝一下。 (特别是在 3.3 及更高版本中，我们可以利用 yield from 。)我正在使用以下导入:

from random import choice
from timeit import timeit
from functools import partial

我写了一个通用的基数排序函数，如下所示:

def radix_sort(values, key, step=0):
    if len(values) < 2:
        for value in values:
            yield value
        return

    bins = {}
    for value in values:
        bins.setdefault(key(value, step), []).append(value)

    for k in sorted(bins.keys()):
        for r in radix_sort(bins[k], key, step + 1):
            yield r

当然，我们不需要通用(我们的“bins”只能用单个字符标记，大概你 真的 意味着将算法应用于 字节 的序列，但是它；)不痛。也可以有一些可重复使用的东西，对吧？无论如何，这个想法很简单:我们处理一个基本情况，然后我们根据键函数的结果将每个元素放入一个“bin”中，然后我们按照排序的 bin 顺序从 bin 中取出值，递归地对每个元素进行排序bin 的内容。

该接口(interface)要求 key(value, n) 为我们提供 n 的第 value 个“基数”。所以对于简单的情况，比如直接比较字符串，这可能是一个简单的 lambda v, n: return v[n] 。但是，这里的想法是根据当时字符串中的数据(循环考虑)将索引与字符串进行比较。所以让我们定义一个键:

def bw_key(text, value, step):
    return text[(value + step) % len(text)]

现在获得正确结果的诀窍是记住我们在概念上连接了我们实际上没有创建的字符串的最后一个字符。如果我们考虑使用索引 n 制作的虚拟字符串，它的最后一个字符位于索引 n - 1 处，因为我们如何环绕 - 稍等片刻就会向您确认这在 n == 0 时仍然有效;)。 [然而，当我们向前换行时，我们仍然需要保持字符串索引在边界内 - 因此在 key 函数中进行模运算。]

这是一个通用的关键函数，需要传入 text 中，在转换 value 进行比较时会引用该函数。这就是 functools.partial 的用武之地——你也可以把 lambda 弄得一团糟，但这可以说更干净，而且我发现它通常也更快。

无论如何，现在我们可以使用 key 轻松编写实际的转换:

def burroughs_wheeler_custom(text):
    return ''.join(text[i - 1] for i in radix_sort(range(len(text)), partial(bw_key, text)))
    # Notice I've dropped the square brackets; this means I'm passing a generator
    # expression to `join` instead of a list comprehension. In general, this is
    # a little slower, but uses less memory. And the underlying code uses lazy
    # evaluation heavily, so :)

好看又好看。让我们看看它是怎么做的，好吗？我们需要一个标准来比较它:

def burroughs_wheeler_standard(text):
    return ''.join([i[-1] for i in sorted([text[i:] + text[:i] for i in range(len(text))])])

还有一个计时例程:

def test(n):
    data = ''.join(choice('abcdefghijklmnopqrstuvwxyz') for i in range(n)) + '$'
    custom = partial(burroughs_wheeler_custom, data)
    standard = partial(burroughs_wheeler_standard, data)
    assert custom() == standard()
    trials = 1000000 // n
    custom_time = timeit(custom, number=trials)
    standard_time = timeit(standard, number=trials)
    print("custom: {} standard: {}".format(custom_time, standard_time))

请注意我为决定 trials 的数量所做的数学运算，与 test 字符串的长度成反比。这应该将用于测试的总时间保持在一个合理的狭窄范围内 - 对吗？ ;)(当然是错误的，因为我们确定 standard 算法至少是 O(N^2)。)

让我们看看它是怎么做的(*drumroll*):

>>> imp.reload(burroughs_wheeler)
<module 'burroughs_wheeler' from 'burroughs_wheeler.py'>
>>> burroughs_wheeler.test(100)
custom: 4.7095093091438684 standard: 0.9819262643716229
>>> burroughs_wheeler.test(1000)
custom: 5.532266880287807 standard: 2.1733253807396977
>>> burroughs_wheeler.test(10000)
custom: 5.954826800612864 standard: 42.50686064849015

哇，这跳跃有点吓人。无论如何，正如您所看到的，新方法在短字符串上增加了大量开销，但使实际排序成为瓶颈，而不是字符串切片。 :)