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

Я внедряю алгоритмы в http://portal.acm.org/citation.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 — количество предоставленных строк?


python longest-substring suffix-array
person Chris    schedule 10.02.2011    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Я думаю, вам следует использовать токенизатор и заменить каждую строку целым числом. Тогда для часовых останется много целых чисел. Возможно, в качестве часовых удобнее использовать большие целые числа, а не маленькие. Для распечатки вы можете использовать любой символ Unicode, который вы хотите, и вы также можете использовать один и тот же символ для всех них.

Вы внедряете Yamamoto & Church? Если это так, взгляните на новую литературу, прежде чем начать. Я рекомендую Abouelhoda et al. Extended Suffix Array и Kim, Kim & Park, Linearized Suffix Trees. А если любите комбинаторику, посмотрите: Шюрманн, Клаус-Бернд, Массивы суффиксов в теории и на практике.

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

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

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

person Dale Gerdemann    schedule 15.02.2011
comment
Спасибо, Дейл. В настоящее время я повторно реализую свою версию Unicode, чтобы использовать целые числа, как вы предлагаете. Unicode ввел некоторые ограничения масштаба, которые мне необходимо преодолеть. Цените указатели на ссылки. Некоторые из них я еще не видел. Спасибо еще раз. - person Chris; 27.02.2011
comment
Пара мыслей: если у вас длинные повторы, вам нужен алгоритм сортировки суффиксов, а не сортировка строк. Но если вы используете сортировку строк, измените ее, чтобы сообщить, какая часть текста сортировалась непосредственно перед переполнением стека. Для текстов на естественном языке длинные повторы — это кавычки, вырезание-вставка, плагиат и т. д., которые, возможно, потребуется удалить, чтобы избежать искажения статистики ngram. Чтобы найти другие самые длинные повторы, пройдите по неявному дереву интервалов, соберите максимум с помощью doc_freq › k и поместите в очередь приоритетов. Это простая идея, но мне (пока) не ясно, что цитируемая статья работает лучше. - person Dale Gerdemann; 06.05.2011

arrow_upward
1
arrow_downward

Вы можете сделать это, используя строки 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'
person Greg Hewgill    schedule 10.02.2011
comment
Спасибо, Грег. Очень признателен! - person Chris; 10.02.2011