strcmp для python или как эффективно (без копирования) сортировать подстроки при построении массива суффиксов

Вот очень простой способ построить массив суффиксов из строки в python:

def sort_offsets(a, b):
    return cmp(content[a:], content[b:])

content = "foobar baz foo"
suffix_array.sort(cmp=sort_offsets)
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

Однако «content[a:]» создает копию содержимого, что становится очень неэффективным, когда содержимое становится большим. Поэтому мне интересно, есть ли способ сравнить две подстроки без их копирования. Я пытался использовать встроенный буфер, но это не сработало.


python string sorting suffix-array
person ephes    schedule 17.02.2010    source источник
comment
Как обычно выглядит ваш «контент»? Английский текст? Случайная последовательность? Что-то среднее? Каковы шансы длинных (скажем, более 100 символов) повторяющихся подстрок в «контенте»?   -  person Mark Dickinson    schedule 17.02.2010
comment
Я написал этот код Python, который может сортировать все подстроки длинной строки (1000000 символов) и находить самую длинную повторяющуюся подстроку за 5 секунд. .   -  person hynekcer    schedule 06.12.2012

Ответы (4)


arrow_upward
6
arrow_downward

Функция buffer не копирует всю строку, а создает объект который ссылается только на исходную строку. Используя предложение interjay, это будет:

suffix_array.sort(key=lambda a: buffer(content, a))
person AndiDog    schedule 17.02.2010
comment
Я тоже поиграл с буфером, но не получил правильный массив суффиксов. Эта строка выглядит очень многообещающе, но она тоже не работает (мой короткий пример выше работает, но ломается на больших). Как только я узнаю, почему он ломается, я снова прокомментирую. - person ephes; 17.02.2010
comment
Ха! Это потому, что str != unicode. Мои большие строки имеют юникод, и поэтому я должен был написать: sizeof_pointer = len(str(buffer(u'a'))) suffix_array.sort(key=lambda a: buffer(content, a * sizeof_pointer)) Чтобы избежать этого уродства, я буду использовать нормализованные строки в кодировке utf8 вместо unicode. Странный. - person ephes; 18.02.2010

arrow_upward
5
arrow_downward

Я не знаю, есть ли быстрый способ сравнения подстрок, но вы можете сделать свой код намного быстрее (и проще), используя key вместо cmp:

suffix_array.sort(key=lambda a: content[a:])

Это создаст подстроку только один раз для каждого значения a.

Изменить. Возможным недостатком является то, что для подстрок потребуется память O (n ^ 2).

person interjay    schedule 17.02.2010
comment
И аргумент cmp sort исчез в 3.x. - person Cat Plus Plus; 17.02.2010
comment
Это занимает 15 секунд для строки длиной 75000 на моей машине, так что это не будет масштабироваться, но хорошая идея. - person ephes; 17.02.2010

arrow_upward
3
arrow_downward

+1 за очень интересную проблему! Я не вижу никакого очевидного способа сделать это напрямую, но мне удалось получить значительное ускорение (на порядок для 100000 строк символов), используя следующую функцию сравнения вместо вашей:

def compare_offsets2(a, b):
    return (cmp(content[a:a+10], content[b:b+10]) or
            cmp(content[a:], content[b:]))

Другими словами, начните со сравнения первых 10 символов каждого суффикса; только если результат этого сравнения равен 0, что указывает на то, что у вас есть совпадение для первых 10 символов, вы продолжаете сравнивать все достаточности.

Очевидно, что 10 может быть чем угодно: поэкспериментируйте, чтобы найти наилучшее значение.

Эта функция сравнения также является хорошим примером того, что нелегко заменить ключевой функцией.

person Mark Dickinson    schedule 17.02.2010
comment
Я получаю еще лучшие результаты, если сначала выполняю сортировку на основе ключа с ключом = lambda a: content[a:a+10], а затем использую сортировку на основе cmp, описанную выше. Алгоритм сортировки Python особенно хорош для списков, которые уже почти отсортированы. - person Mark Dickinson; 17.02.2010
comment
Хорошая идея! Реальный вариант использования — найти все документы, соответствующие некоторой буквенно-цифровой подстроке. Содержимое представляет собой объединение всех документов, и, поскольку я знаю, какое смещение для каждого документа в содержимом, я использую двоичный поиск (в списке смещений), чтобы найти максимальное количество символов, которые мне придется копировать. Но это все еще довольно медленно. Наверное, мне придется сделать это в... - person ephes; 17.02.2010
comment
Еще одна возможность, прежде чем вы прибегнете к C: возможно, вы сможете использовать модуль ctypes, чтобы получить strcmp C, и использовать его из Python. Встроенные нулевые символы в строки Python могут вызвать трудности, но на практике это может не быть проблемой. Но я согласен, что это похоже на задачу, для которой уместно переписать медленную часть на C. - person Mark Dickinson; 18.02.2010

arrow_upward
0
arrow_downward

Вы можете использовать тип расширения blist, который я написал. blist работает так же, как встроенный list, но (среди прочего) использует копирование при записи, так что создание среза занимает O(log n) времени и памяти.

from blist import blist

content = "foobar baz foo"
content = blist(content)
suffix_array = range(len(content))
suffix_array.sort(key = lambda a: content[a:])
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

Мне удалось создать suffix_array из случайно сгенерированной строки из 100 000 символов менее чем за 5 секунд, включая генерацию строки.

person Daniel Stutzbach    schedule 05.03.2010
comment
Протестированный блист с тестовой строкой из 12 миллионов символов. Я сдался после одного часа процессорного времени. На тот момент использование памяти составляло 21 ГБ и росло. Буферное решение использует 6,7 ГБ и завершается через 8 минут. Поскольку мои реальные данные содержат около 500 миллионов символов, оба решения не будут работать. Я использую sites.google.com/site/yuta256/sais для получения отсортированных suffix_array и прочитать его обратно в python с помощью array.array.fromfile... - person ephes; 05.03.2010
comment
Я предлагаю вам обновить исходный вопрос, указав, что ваши реальные данные содержат 500 миллионов символов. Сколько памяти требуется только для хранения suffix_array перед сортировкой? Для таких больших данных я бы определенно использовал C, чтобы сократить накладные расходы памяти. - person Daniel Stutzbach; 05.03.2010