在构造后缀数组之前在 Python 中指定字符串结尾标记

Question

我正在 http://portal.acm.org/itation.cfm?id 中实现算法=1813708 利用后缀数组来查找最长公共子串。这些算法涉及为字符串构造一个后缀数组，该数组是一组给定字符串与称为哨兵的字符串分隔符的串联。例如，如果给定字符串 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 &教会？如果是这样，请在开始之前查看一些较新的文献。我推荐 Abouelhoda 等人的扩展后缀数组和 Kim, Kim & 。 Park，线性化后缀树。如果您喜欢组合学，请查看：Schürmann、Klaus-Bernd、后缀数组的理论和实践。

另外，我建议使用 3 路基数快速排序，而不是专门的后缀排序算法。仅在语料库出现冗余的情况下才需要后缀排序算法。但这些冗余是不必要的，而且会搞乱你的统计数据。

如果你做了一些有趣的事情，我有兴趣见到

戴尔·格德曼