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

我试图在python中实现Burrows-Wheeler转换。 (这是在线类(class)中的一项作业，但我希望我已经做了一些工作，有资格寻求帮助)。

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

这给了我一个类轮:

''.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

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

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

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

P.S.只是想指出，这也可能看起来像是一个作业问题，我的解决方案已经通过了分级机，我正在寻找一种使速度更快的方法。同样，我不会破坏其他人的乐趣，因为如果他们想找到解决方案，那么Wiki文章中的文章与我的相似。我还检查了this questio n，它听起来很相似，但是回答了一个更棘手的问题，即如何解码用此算法编码的字符串。

最佳答案

用长字符串制作所有这些字符串切片需要很长时间。至少是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

当然，我们不需要是通用的(我们的“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时，该字符串仍然有效；)。 [但是，当我们进行前移时，我们仍然需要将字符串索引保持在边界内-因此，键函数中的模运算。

这是一个通用键函数，在转换text进行比较时需要将其传递到value中。这就是functools.partial出现的地方-您也可以把lambda弄乱，但这可以说是比较干净的，而且我发现它通常也更快。

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

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

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

关于python - python中的Burrows-Wheeler中的性能问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21297887/