Python中的strcmp或如何高效排序子串（无复制）以构建后缀数组

Question

这里有一个非常简单的方法，可以用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:]" 这个写法会复制一份内容，当内容变得很大时，这样做就会变得非常低效。所以我在想有没有办法在不复制这两个子字符串的情况下进行比较。我试过使用内置的缓冲区，但没有成功。

Answer 1

这个问题真有意思，值得点赞！我找不到直接解决这个问题的明显方法，不过我用了一种新的比较方式，让处理速度大大提升（对于10万个字符的字符串，速度提升了十倍）。具体的比较函数是这样的：

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

简单来说，就是先比较每个后缀的前10个字符；只有当这10个字符完全相同的时候，才继续比较整个后缀。

当然，10这个数字可以换成其他的，建议你试着找出最合适的值。

这个比较函数也很有意思，因为它不容易用其他的关键函数来替代。

Answer 2

我不知道有没有快速的方法来比较子字符串，但你可以通过使用 key 来让你的代码变得更快（也更简单），而不是用 cmp：

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

这样做会让每个 a 的值只创建一次子字符串。

补充说明：一个可能的缺点是，这样会需要 O(n^2) 的内存来存储这些子字符串。

Answer 3

buffer这个函数并不是把整个字符串都复制一遍，而是创建了一个只指向原始字符串的对象。根据interjay的建议，可以这样做：

suffix_array.sort(key=lambda a: buffer(content, a))