Manera eficiente de encontrar la cadena duplicada más larga para Python (De Programación Pearls)

De la Sección 15.2 de Perlas de Programación

Los códigos C se pueden ver aquí: http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

Cuando lo implemento en Python usando suffix-array:

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

Lo encontré muy lento para el idx.sort paso. Creo que es lento porque Python necesita pasar la subcadena por valor en lugar de por puntero (como los códigos C anteriores).

El archivo probado se puede descargar desde aquí

Los códigos C necesitan solo 0,3 segundos para finalizar.

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

Pero para los códigos de Python, nunca termina en mi computadora (esperé 10 minutos y lo eliminé)

¿Alguien tiene ideas de cómo hacer que los códigos sean eficientes? (Por ejemplo, menos de 10 segundos)

Mi solución se basa en Arreglos de sufijos. Está construido por duplicación de prefijo la Prefijo común más largo. La complejidad del peor de los casos es O(n (log n)^2). El archivo “iliad.mb.txt” tarda 4 segundos en mi computadora portátil. Él longest_common_substring La función es corta y se puede modificar fácilmente, por ejemplo, para buscar las 10 subcadenas más largas que no se superponen. Este código Python es más rápido que el código C original de la pregunta, si las cadenas duplicadas tienen más de 10000 caracteres.

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

Prefiero esta solución a más complicado O(n log n) porque Python tiene un algoritmo de clasificación de listas muy rápido (Timsort). El tipo de Python es probablemente más rápido que las operaciones de tiempo lineal necesarias en el método de ese artículo, que debería ser O (n) bajo presunciones muy especiales de cadenas aleatorias junto con un alfabeto pequeño (típico para el análisis del genoma del ADN). leo en Gog 2011 que en el peor de los casos O (n log n) de mi algoritmo puede ser en la práctica más rápido que muchos algoritmos O (n) que no pueden usar la memoria caché de la CPU.

El código en otra respuesta basada en grow_chains es 19 veces más lento que el ejemplo original de la pregunta, si el texto contiene una cadena repetida de 8 kB de largo. Los textos repetidos largos no son típicos de la literatura clásica, pero son frecuentes, por ejemplo, en las colecciones de tareas escolares “independientes”. El programa no debe congelarse en él.

escribí un ejemplo y pruebas con el mismo código para Python 2.7, 3.3 – 3.6.

Esta versión tarda unos 17 segundos en mi escritorio de alrededor de 2007 usando un algoritmo totalmente diferente:

#!/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)

La idea básica es crear una lista de subcadenas y posiciones donde ocurren, eliminando así la necesidad de comparar las mismas cadenas una y otra vez. La lista resultante parece [('ind him, but', [466548, 739011]), (' bulwark bot', [428251, 428924]), (' his armour,', [121559, 124919, 193285, 393566, 413634, 718953, 760088])]. Se eliminan las cadenas únicas. Luego, cada miembro de la lista crece en 1 carácter y se crea una nueva lista. Las cadenas únicas se eliminan nuevamente. Y así sucesivamente y así sucesivamente…