Эффективный способ найти самую длинную повторяющуюся строку для Python (From Programming Pearls)
Из раздела 15.2 "Программирование жемчужин"
С кодами C можно ознакомиться здесь: http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c
Когда я реализую это в Python, используя суффикс-массив:
example = open("iliad10.txt").read()
def comlen(p, q):
i = 0
for x in zip(p, q):
if x[0] == x[1]:
i += 1
else:
break
return i
suffix_list = []
example_len = len(example)
idx = list(range(example_len))
idx.sort(cmp = lambda a, b: cmp(example[a:], example[b:])) #VERY VERY SLOW
max_len = -1
for i in range(example_len - 1):
this_len = comlen(example[idx[i]:], example[idx[i+1]:])
print this_len
if this_len > max_len:
max_len = this_len
maxi = i
Я нашел это очень медленно для idx.sort шаг. Я думаю, что это медленно, потому что Python должен передавать подстроку по значению, а не по указателю (как код C выше).
Тестовый файл можно скачать здесь
Для кодов С требуется всего 0,3 секунды.
time cat iliad10.txt |./longdup
On this the rest of the Achaeans with one voice were for
respecting the priest and taking the ransom that he offered; but
not so Agamemnon, who spoke fiercely to him and sent him roughly
away.
real 0m0.328s
user 0m0.291s
sys 0m0.006s
Но для кодов Python это никогда не заканчивается на моем компьютере (я ждал 10 минут и убил его)
У кого-нибудь есть идеи, как сделать коды эффективными? (Например, менее 10 секунд)
4 ответа
Мое решение основано на массиве Suffix. Он построен путем удвоения префикса Longest общего префикса. Наихудшая сложность - O(n (log n)^2). Задача "iliad.mb.txt" занимает 4 секунды на моем ноутбуке. Код хорошо документирован внутри функций suffix_array а также longest_common_substring, Последняя функция короткая и может быть легко изменена, например, для поиска 10 самых длинных не перекрывающихся подстрок. Этот код Python быстрее, чем исходный код C (скопируйте здесь) из вопроса, если длина повторяющихся строк превышает 10000 символов.
from itertools import groupby
from operator import itemgetter
def longest_common_substring(text):
"""Get the longest common substrings and their positions.
>>> longest_common_substring('banana')
{'ana': [1, 3]}
>>> text = "not so Agamemnon, who spoke fiercely to "
>>> sorted(longest_common_substring(text).items())
[(' s', [3, 21]), ('no', [0, 13]), ('o ', [5, 20, 38])]
This function can be easy modified for any criteria, e.g. for searching ten
longest non overlapping repeated substrings.
"""
sa, rsa, lcp = suffix_array(text)
maxlen = max(lcp)
result = {}
for i in range(1, len(text)):
if lcp[i] == maxlen:
j1, j2, h = sa[i - 1], sa[i], lcp[i]
assert text[j1:j1 + h] == text[j2:j2 + h]
substring = text[j1:j1 + h]
if not substring in result:
result[substring] = [j1]
result[substring].append(j2)
return dict((k, sorted(v)) for k, v in result.items())
def suffix_array(text, _step=16):
"""Analyze all common strings in the text.
Short substrings of the length _step a are first pre-sorted. The are the
results repeatedly merged so that the garanteed number of compared
characters bytes is doubled in every iteration until all substrings are
sorted exactly.
Arguments:
text: The text to be analyzed.
_step: Is only for optimization and testing. It is the optimal length
of substrings used for initial pre-sorting. The bigger value is
faster if there is enough memory. Memory requirements are
approximately (estimate for 32 bit Python 3.3):
len(text) * (29 + (_size + 20 if _size > 2 else 0)) + 1MB
Return value: (tuple)
(sa, rsa, lcp)
sa: Suffix array for i in range(1, size):
assert text[sa[i-1]:] < text[sa[i]:]
rsa: Reverse suffix array for i in range(size):
assert rsa[sa[i]] == i
lcp: Longest common prefix for i in range(1, size):
assert text[sa[i-1]:sa[i-1]+lcp[i]] == text[sa[i]:sa[i]+lcp[i]]
if sa[i-1] + lcp[i] < len(text):
assert text[sa[i-1] + lcp[i]] < text[sa[i] + lcp[i]]
>>> suffix_array(text='banana')
([5, 3, 1, 0, 4, 2], [3, 2, 5, 1, 4, 0], [0, 1, 3, 0, 0, 2])
Explanation: 'a' < 'ana' < 'anana' < 'banana' < 'na' < 'nana'
The Longest Common String is 'ana': lcp[2] == 3 == len('ana')
It is between tx[sa[1]:] == 'ana' < 'anana' == tx[sa[2]:]
"""
tx = text
size = len(tx)
step = min(max(_step, 1), len(tx))
sa = list(range(len(tx)))
sa.sort(key=lambda i: tx[i:i + step])
grpstart = size * [False] + [True] # a boolean map for iteration speedup.
# It helps to skip yet resolved values. The last value True is a sentinel.
rsa = size * [None]
stgrp, igrp = '', 0
for i, pos in enumerate(sa):
st = tx[pos:pos + step]
if st != stgrp:
grpstart[igrp] = (igrp < i - 1)
stgrp = st
igrp = i
rsa[pos] = igrp
sa[i] = pos
grpstart[igrp] = (igrp < size - 1 or size == 0)
while grpstart.index(True) < size:
# assert step <= size
nextgr = grpstart.index(True)
while nextgr < size:
igrp = nextgr
nextgr = grpstart.index(True, igrp + 1)
glist = []
for ig in range(igrp, nextgr):
pos = sa[ig]
if rsa[pos] != igrp:
break
newgr = rsa[pos + step] if pos + step < size else -1
glist.append((newgr, pos))
glist.sort()
for ig, g in groupby(glist, key=itemgetter(0)):
g = [x[1] for x in g]
sa[igrp:igrp + len(g)] = g
grpstart[igrp] = (len(g) > 1)
for pos in g:
rsa[pos] = igrp
igrp += len(g)
step *= 2
del grpstart
# create LCP array
lcp = size * [None]
h = 0
for i in range(size):
if rsa[i] > 0:
j = sa[rsa[i] - 1]
while i != size - h and j != size - h and tx[i + h] == tx[j + h]:
h += 1
lcp[rsa[i]] = h
if h > 0:
h -= 1
if size > 0:
lcp[0] = 0
return sa, rsa, lcp
Я предпочитаю это решение более сложному O(n log n), потому что Python имеет очень быструю сортировку списка (list.sort), возможно, быстрее, чем необходимые операции линейного времени в методе из этой статьи, который должен быть O(n) при очень специальные предположения о случайных строках вместе с небольшим алфавитом (типично для анализа генома ДНК). Я прочитал в Gog 2011, что O(n log n) моего алгоритма в худшем случае может быть на практике быстрее, чем многие алгоритмы O(n), которые не могут использовать кэш памяти процессора.
Код в другом ответе, основанном на grow_chains, работает в 19 раз медленнее, чем исходный пример из вопроса, если текст содержит повторяющуюся строку длиной 8 кБ. Длинные повторяющиеся тексты не типичны для классической литературы, но они часто встречаются, например, в "независимых" школьных коллекциях домашних заданий. Программа не должна зависать на нем.
Я написал пример и тесты с тем же кодом для Python 2.7, 3.3 - 3.6.
Перевод алгоритма на Python:
from itertools import imap, izip, starmap, tee
from os.path import commonprefix
def pairwise(iterable): # itertools recipe
a, b = tee(iterable)
next(b, None)
return izip(a, b)
def longest_duplicate_small(data):
suffixes = sorted(data[i:] for i in xrange(len(data))) # O(n*n) in memory
return max(imap(commonprefix, pairwise(suffixes)), key=len)
buffer()позволяет получить подстроку без копирования:
def longest_duplicate_buffer(data):
n = len(data)
sa = sorted(xrange(n), key=lambda i: buffer(data, i)) # suffix array
def lcp_item(i, j): # find longest common prefix array item
start = i
while i < n and data[i] == data[i + j - start]:
i += 1
return i - start, start
size, start = max(starmap(lcp_item, pairwise(sa)), key=lambda x: x[0])
return data[start:start + size]
Это займет 5 секунд на моей машине дляiliad.mb.txt,
В принципе, можно найти дубликат во времени O(n) и памяти O(n), используя массив суффиксов, дополненный массивом lcp.
Замечания:*_memoryview()осуждается*_buffer() версия
Более эффективная для памяти версия (по сравнению с longest_duplicate_small()):
def cmp_memoryview(a, b):
for x, y in izip(a, b):
if x < y:
return -1
elif x > y:
return 1
return cmp(len(a), len(b))
def common_prefix_memoryview((a, b)):
for i, (x, y) in enumerate(izip(a, b)):
if x != y:
return a[:i]
return a if len(a) < len(b) else b
def longest_duplicate(data):
mv = memoryview(data)
suffixes = sorted((mv[i:] for i in xrange(len(mv))), cmp=cmp_memoryview)
result = max(imap(common_prefix_memoryview, pairwise(suffixes)), key=len)
return result.tobytes()
Это займет 17 секунд на моей машине для iliad.mb.txt, Результат:
На этом остальные ахейцы с одним голосом были за уважение священник и получение выкупа, который он предложил; но не так, как Агамемнон, который яростно говорил с ним и грубо отослал его.
Я должен был определить пользовательские функции для сравнения memoryview объекты, потому что memoryview Сравнение либо вызывает исключение в Python 3, либо дает неправильный результат в Python 2:
>>> s = b"abc"
>>> memoryview(s[0:]) > memoryview(s[1:])
True
>>> memoryview(s[0:]) < memoryview(s[1:])
True
Смежные вопросы:
Найдите самую длинную повторяющуюся строку и сколько раз она повторяется в данной строке
Кажется, главная проблема в том, что python выполняет нарезку по копии: /questions/11500058/piton-delaet-sektsiyu-po-ssyilke-na-stroki/11500067#11500067
Вы должны будете использовать обзор памяти, чтобы получить ссылку вместо копии. Когда я сделал это, программа зависла после idx.sort функция (которая была очень быстрой).
Я уверен, что немного поработав, вы можете заставить остальных работать.
Редактировать:
Вышеупомянутое изменение не будет работать в качестве замены, поскольку cmp не работает так же, как strcmp , Например, попробуйте следующий код C:
#include <stdio.h>
#include <string.h>
int main() {
char* test1 = "ovided by The Internet Classics Archive";
char* test2 = "rovided by The Internet Classics Archive.";
printf("%d\n", strcmp(test1, test2));
}
И сравните результат с этим питоном:
test1 = "ovided by The Internet Classics Archive";
test2 = "rovided by The Internet Classics Archive."
print(cmp(test1, test2))
Код C печатает -3 на моей машине, пока печатает версию Python -1, Похоже на пример C код злоупотребляет возвращаемым значением strcmp (это используется в qsort в конце концов). Я не мог найти документацию о том, когда strcmp вернет что-то кроме [-1, 0, 1], но добавив printf в pstrcmp в исходном коде показано много значений за пределами этого диапазона (3, -31, 5 были первыми 3 значениями).
Чтобы убедиться, что -3 не был какой-то код ошибки, если мы поменяем test1 и test2, мы получим 3,
Редактировать:
Вышесказанное является интересной мелочью, но на самом деле не является правильным с точки зрения воздействия на любой фрагмент кода. Я понял это так же, как я закрыл свой ноутбук и вышел из зоны Wi-Fi... Действительно, должен дважды проверить все, прежде чем я нажму Save,
FWIW, cmp наверняка работает на memoryview объекты (отпечатки -1 как и ожидалось):
print(cmp(memoryview(test1), memoryview(test2)))
Я не уверен, почему код не работает, как ожидалось. Распечатка списка на моей машине выглядит не так, как ожидалось. Я посмотрю на это и попытаюсь найти лучшее решение вместо того, чтобы хвататься за соломинку.
Эта версия занимает около 17 секунд на моем рабочем столе около 2007 года, используя совершенно другой алгоритм:
#!/usr/bin/env python
ex = open("iliad.mb.txt").read()
chains = dict()
# populate initial chains dictionary
for (a,b) in enumerate(zip(ex,ex[1:])) :
s = ''.join(b)
if s not in chains :
chains[s] = list()
chains[s].append(a)
def grow_chains(chains) :
new_chains = dict()
for (string,pos) in chains :
offset = len(string)
for p in pos :
if p + offset >= len(ex) : break
# add one more character
s = string + ex[p + offset]
if s not in new_chains :
new_chains[s] = list()
new_chains[s].append(p)
return new_chains
# grow and filter, grow and filter
while len(chains) > 1 :
print 'length of chains', len(chains)
# remove chains that appear only once
chains = [(i,chains[i]) for i in chains if len(chains[i]) > 1]
print 'non-unique chains', len(chains)
print [i[0] for i in chains[:3]]
chains = grow_chains(chains)
Основная идея заключается в создании списка подстрок и позиций, в которых они встречаются, что устраняет необходимость сравнивать одни и те же строки снова и снова. Полученный список выглядит как [('ind him, but', [466548, 739011]), (' bulwark bot', [428251, 428924]), (' his armour,', [121559, 124919, 193285, 393566, 413634, 718953, 760088])], Уникальные строки удалены. Затем каждый член списка увеличивается на 1 символ и создается новый список. Уникальные строки удаляются снова. И так далее...