string - 您实际上如何将后缀数组应用于任何类型的文本？

Question

我正在阅读有关 Suffix Arrays 的内容，构建一个的代码很简单。但是我找到的所有资源通常都使用一个简单的示例文本(通常是 banana)来解释这个概念。
因此，尽管示例文本很简单，并且显示了后缀数组 (a,ana,anana,banana, na,nana) 据我所知，这可以应用于任何类型的文本。
但是我不明白，因为文本有空格，换行符，标点符号等。
那么这如何适用于任何类型的文本呢？

Answer 1

对于更长的字符串，您的后缀数组将如下所示:

[01] banana split, yum!
[02] anana split, yum!
[03] nana split, yum!
[04] ana split, yum!
[05] na split, yum!
[06] a split, yum!
[07]  split, yum!
[08] split, yum!
[09] plit, yum!
[10] lit, yum!
[11] it, yum!
[12] t, yum!
[13] , yum!
[14]  yum!
[15] yum!
[16] um!
[17] m!
[18] !

然后您可以按字母顺序对其进行排序，以找到最长的重复子字符串，这是后缀数组的常见用法。

我还记得我做过类似的事情，在长文本中查找单词的重复模式，我使用空格字符作为分隔符，而不是遍历每个字符:

[01] if it is true it is true
[02] it is true it is true
[03] is true it is true
[04] true it is true
[05] it is true
[06] is true
[07] true

虽然这不是后缀数组，但按字母顺序排序后，可以找到重复的单词模式:

[01] if it is true it is true
[06] is true
[03] is true it is true
[05] it is true
[02] it is true it is true
[07] true
[04] true it is true

通过将每一行与它上面的行进行比较，只要字符匹配，我们发现'is true'和'it is true'是重复的单词模式。

此方法的灵感来自一个常见的 DNA 研究问题，称为最长重复子串问题:http://en.wikipedia.org/wiki/Longest_repeated_substring_problem

当然，它确实出现在遗传科学以外的其他领域。