Указание конца строковых сторожей в Python до построения массива суффиксов

Question

Я реализую алгоритмы в http://portal.acm.org/citation.cfm?id=1813708, которые используют суффиксные массивы для поиска самых длинных общих подстрок.Алгоритмы включают в себя создание массива суффиксов для строки, которая является конкатенацией набора заданных строк с разделителями строк, называемыми часовыми.Например, если нам даны строки a, b и c, создается новая строка d, представляющая собой $ 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, который вы хотите, и вы можете использовать один и тот же символ для всех них.

Реализуете ли вы Ямамото и Церковь? Если это так, взгляните на более новую литературу, прежде чем начать. Я рекомендую Abouelhoda и др. Расширенный суффиксный массив и Kim, Kim & Park, линеаризованные суффиксные деревья. А если вам нравится комбинаторика, посмотрите на: массивы Шюрмана, Клауса-Бернда, Суффикса в теории и на практике.

Кроме того, я рекомендую трехстороннюю радикальную сортировку, в отличие от специализированного алгоритма сортировки суффиксов. Вам нужен только алгоритм сортировки суффиксов в случае избыточности в вашем корпусе. Но эти избыточности не нужны и могут испортить вашу статистику.

А если сделать что-нибудь интересное, мне было бы интересно посмотреть

Дейл Гердеманн