Как вы на самом деле применяете суффиксные массивы к любому виду текста?

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

Сравнивая каждую строку со строкой над ней, пока символы совпадают, мы обнаруживаем, что слова "верно" и "верно" являются повторяющимися образцами слов.

Этот метод основан на общей проблеме исследования ДНК, которая называется самой длинной проблемой повторяющихся подстрок: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem

Конечно, это возникает в других областях, чем генетическая наука.