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]
Однако "содержание [a:]" делает копию содержания, которое становится очень неэффективным, когда содержание становится большим. Таким образом, я задаюсь вопросом, существует ли способ сравнить эти две подстроки, не имея необходимость копировать их. Я попытался использовать буферно-встроенное, но это не сделало работавший.
4 ответа
Я не знаю, есть ли быстрый способ сравнения подстрок, но вы можете сделать свой код намного быстрее (и проще), используя ключ вместо cmp :
suffix_array.sort(key=lambda a: content[a:])
Это создаст подстроку только один раз для каждого значения a.
Изменить: Возможным недостатком является то, что для подстрок потребуется O (n ^ 2) памяти.
Функция buffer не копирует всю строку, а создает объект, который ссылается только на исходную строку. Используя предложение interjay, это будет:
suffix_array.sort(key=lambda a: buffer(content, a))
+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 может быть чем угодно: экспериментируйте, чтобы найти наилучшее значение.
Эта функция сравнения также является хорошим примером того, что нелегко заменить ключевой функцией.
Вы можете использовать написанный мной тип расширения блистера . Блист работает аналогично встроенному списку , но (среди прочего) использует копирование при записи, так что взятие среза занимает 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]
Мне удалось создать суффикс_массив из случайно сгенерированной 100000-символьной строки менее чем за 5 секунд, включая создание строки.