10

这是在python中从字符串构建后缀数组的一种非常简单的方法：

def sort_offsets(a, b):
    return cmp(content[a:], content[b:])

content = "foobar baz foo"
suffix_array.sort(cmp=sort_offsets)
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

但是，“content[a:]”会复制内容，当内容变大时效率会非常低。所以我想知道是否有一种方法可以比较两个子字符串而不必复制它们。我尝试使用内置缓冲区，但没有奏效。

4

4 回答 4

6

缓冲区函数不会复制整个字符串，而是创建一个仅引用源字符串的对象。使用 interjay 的建议，那就是：

suffix_array.sort(key=lambda a: buffer(content, a))
于 2010-02-17T16:59:20.213 回答
5

key我不知道是否有一种比较子字符串的快速方法，但是您可以通过使用而不是使您的代码更快（更简单）cmp：

suffix_array.sort(key=lambda a: content[a:])

这将为 a 的每个值创建一次子字符串。

编辑：一个可能的缺点是子字符串需要 O(n^2) 内存。

于 2010-02-17T16:52:49.103 回答
3

+1 一个非常有趣的问题！我看不到任何直接执行此操作的明显方法，但是通过使用以下比较函数代替您的比较函数，我能够获得显着的加速（100000 个字符串的数量级）：

def compare_offsets2(a, b):
    return (cmp(content[a:a+10], content[b:b+10]) or
            cmp(content[a:], content[b:]))

换句话说，首先比较每个后缀的前 10 个字符；只有当该比较的结果为 0 时，表明您已经匹配了前 10 个字符，您才继续比较全部内容。

显然 10 可以是任何东西：尝试找到最佳值。

这个比较函数也是一个很好的例子，它不能轻易地用键函数代替。

于 2010-02-17T18:38:19.397 回答
0

你可以使用我写的blist 扩展类型。Ablist像 built-in 一样工作list，但（除其他外）使用写时复制，因此获取切片需要 O(log n) 时间和内存。

from blist import blist

content = "foobar baz foo"
content = blist(content)
suffix_array = range(len(content))
suffix_array.sort(key = lambda a: content[a:])
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

我能够在 5 秒内从随机生成的 100,000 个字符的字符串中创建一个 suffix_array，其中包括生成字符串。

于 2010-03-05T00:04:36.203 回答