Эффективный способ найти длинную повторяющуюся строку для 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 выше).

Исследуемый файл можно скачать здесь

Кодам 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 Solutions collect form web for “Эффективный способ найти длинную повторяющуюся строку для Python (From Programming Pearls)”

Основная проблема заключается в том, что python делает нарезку по копии: https://stackoverflow.com/a/5722068/538551

Вы должны будете использовать memoryview вместо этого, чтобы получить ссылку вместо копии. Когда я это сделал, программа зависала после функции 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)); } 

И сравните результат с этим python:

 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))) 

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

Мое решение основано на массиве Суффикса . Он строится с помощью удвоения префикса самого длинного общего префикса . Наихудшей сложностью является 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, eg 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), которые не могут использовать кеш памяти CPU.

Код в другом ответе, основанный на grow_chains, в 19 ​​раз медленнее исходного примера из вопроса, если текст содержит повторяющуюся строку длиной 8 кбайт. Длинные повторяющиеся тексты не типичны для классической литературы, но часто встречаются, например, в «независимых» школьных сборниках домашних заданий. Программа не должна зависеть от нее.

EDIT: изменена одна строка для совместимости с Python 2.6, 2.7 и 3.3

Я написал пример и тесты с тем же кодом .

Перевод алгоритма в 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 сравнение с memoryview вызывает либо исключение в Python 3, либо создает неправильный результат в Python 2:

 >>> s = b"abc" >>> memoryview(s[0:]) > memoryview(s[1:]) True >>> memoryview(s[0:]) < memoryview(s[1:]) True 

Связанные вопросы:

Найдите самую длинную повторяющуюся строку и количество повторений в заданной строке

нахождение длинных повторных подстрок в массивной струне

Эта версия занимает около 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 символ и создается новый список. Уникальные строки снова удаляются. И так далее…

  • Преобразование функции Python в C ++ с использованием Boost.Python
  • существует ли эквивалент Python для Memcpy
  • Встраивание matplotlib в C ++
  • Как реализовать интерфейсы в python?
  • Должны ли пользователи TensorFlow использовать SavedModel через контрольную точку или GraphDef?
  • Объединение Cython с MKL
  • Как проверить подписанные данные с помощью библиотеки PyKCS11
  • Могу ли я заставить numpy ndarray взять на себя ответственность за свою память?
  • Boost python обертывание виртуального метода
  • Как я могу написать функцию C, которая принимает либо int, либо float?
  • Портирование оптимизированного сита эратосфенов от Python до C ++
  • Python - лучший язык программирования в мире.