在构建后缀数组前指定Python中字符串结束标记

Question

我正在实现一些算法，这些算法使用后缀数组来找到最长的公共子串。具体来说，这些算法需要为一个新字符串构建后缀数组，这个新字符串是将一组给定字符串连接在一起，并用一些特殊字符（称为哨兵）分隔开。举个例子，如果我们有字符串a、b和c，那么我们会创建一个新字符串d，格式是a$1b$2c$3，其中$1、$2、$3是标记每个字符串结束的哨兵字符。这些哨兵字符必须是独一无二的，并且在字典顺序上要比a、b和c中的所有其他字符都小。

我想问的是，在Python中如何表示这些哨兵字符。如果a、b和c是ASCII字符串，我在想是否需要把这些字符串转换成UTF-8格式，并将它们的范围从0-127移动到一个更高的范围，这样就能有一些字符在字典顺序上比这些字符串中的字符更小。如果这样做合理的话，如何在Python中最有效地重新映射这些字符，使它们的范围变成N-127+N，其中N是提供的字符串数量？

Answer 1

你可以使用Unicode字符串（不是UTF-8）来做到这一点。在Python 3中，所有字符串都是Unicode格式的，但在Python 2中，你需要在字符串前加上u这个前缀（也就是说，"hello" 不是Unicode字符串，但u"world" 是）。

>>> s = u"string one"
>>> N = 3
>>> "".join(unichr(ord(x) + N) for x in s)
u'vwulqj#rqh'

对于Python 3来说，这个过程会简单一些：

>>> s = "string one"
>>> N = 3
>>> "".join(chr(ord(x) + N) for x in s)
'vwulqj#rqh'

Answer 2

我觉得你应该使用一个分词器，把每个字符串替换成一个整数。这样的话，作为标记的整数就会有很多剩余。可能用较大的整数作为标记会比用小的整数更方便。至于打印输出，你可以使用任何你想要的Unicode字符，甚至可以用同一个字符来表示所有的标记。

你是在实现Yamamoto和Church的算法吗？如果是的话，建议你在开始之前先看看一些新的文献。我推荐Abouelhoda等人的《扩展后缀数组》和Kim、Kim & Park的《线性后缀树》。如果你对组合数学感兴趣，可以看看Schürmann, Klaus-Bernd的《后缀数组的理论与实践》。

另外，我推荐使用三路基数快速排序，而不是专门的后缀排序算法。你只在你的数据中有重复内容时才需要后缀排序算法。但这些重复内容其实是多余的，会影响你的统计结果。

如果你做出了一些有趣的东西，我很想看看。

戴尔·格尔德曼