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：]”会复制content，当content变得很大时，这将变得非常低效。因此，我想知道是否有一种方法可以在不复制它们的情况下比较这两个子字符串。我尝试过使用内置的缓冲区（buffer-builtin），但它没有起作用。

- ephes

---

您的“content”通常是什么样子？是英文文本吗？还是随机序列？还是介于两者之间？在“content”中出现长（比如超过100个字符）重复的子字符串的概率是多少？ - Mark Dickinson

我写了这个Python代码，可以对长字符串的所有子字符串进行排序，并在5秒内找到最长的重复子字符串。 - hynekcer

Answer 1

缓冲区 (buffer) 函数不会复制整个字符串，而是创建一个仅引用源字符串的对象。使用 interjay 的建议，代码如下：

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

- AndiDog

---

我也尝试过缓冲区，但没有得到正确的后缀数组。这行代码看起来非常有前途，但它也不起作用（我的简短示例可以工作，但在更大的示例上会出错）。一旦我知道它为什么会出错，我会再次评论。 - ephes

哈！这是因为str != unicode。我的较大字符串是unicode，因此我应该写成：sizeof_pointer = len(str(buffer(u'a'))) suffix_array.sort(key=lambda a: buffer(content, a * sizeof_pointer))为了避免这种丑陋的情况，我将使用规范化的utf8编码字符串代替unicode。奇怪。 - ephes

Answer 2

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

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

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

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

- interjay

---

在3.x中，sort的cmp参数已经被删除。 - Cat Plus Plus

在我的机器上，对于长度为75000的字符串，这需要15秒钟，因此这不会扩展 - 但是想法很好。 - ephes

Answer 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可以是任何值：尝试实验以找到最佳值。

这个比较函数也是一个很好的例子，说明它不容易用键函数替代。

- Mark Dickinson

---

我首先使用关键字为lambda a: content[a:a+10]的基于键的排序，然后再执行上述基于cmp的排序，可以获得更好的结果。对于几乎有序的列表，Python的排序算法表现尤为出色。 - Mark Dickinson

好主意！真正的用例是查找所有与某个字母数字子串匹配的文档。 "内容" 是所有文档的串联，由于我知道每个文档在内容中的偏移量，所以我使用二进制搜索（在偏移列表中）来查找我需要复制的最大字符数。但它仍然相当慢。可能我需要用 C 来完成它... - ephes

在您尝试使用 C 之前，还有一种可能性：您可以尝试使用 ctypes 模块来获取 C 的 strcmp 并从 Python 中使用它。Python 字符串中的嵌入式空字符可能会导致困难，但实际上可能不是问题。但我同意这似乎正是重写 C 的缓慢部分适当的任务类型。 - Mark Dickinson

Answer 4

你可以使用我编写的扩展类型 blist。一个blist的工作方式类似于内置的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秒钟的时间内从随机生成的10万个字符的字符串中创建出一个后缀数组，这还包括生成字符串的时间。

- Daniel Stutzbach

---

测试了一个包含1200万个字符的测试字符串。在经过一小时的CPU时间后，我放弃了。此时内存使用量为21GByte，并且不断增长。缓冲区解决方案使用了6.7GByte，并在8分钟后完成。由于我的真实数据大约有5亿个字符，这两种解决方案都行不通。目前我使用http://sites.google.com/site/yuta256/sais来获取排序后的后缀数组，并使用array.array.fromfile将其读回Python中... - ephes

我建议您更新原始问题，提到您的真实数据包含5亿个字符。仅存储后缀数组在排序之前需要多少内存？对于如此大的数据，我肯定会使用C来减少内存开销。 - Daniel Stutzbach