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

11 minutos de lectura

avatar de usuario
sol hanfei

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)

  • ¿Cuánto tarda el código C? ¿Cuánto tarda tu código?

    – beatgammit

    26 de noviembre de 2012 a las 7:00

  • Los códigos @tjameson C usan 0.3 segundos. No sé cuánto tardan mis códigos, ya que nunca termina (al menos 10 minutos).

    – Hanfei Sol

    26 de noviembre de 2012 a las 7:02


  • El código C es lento porque no puede realizar un seguimiento de la “coincidencia más larga hasta el momento” al ordenar y tiene que verificar todo por segunda vez. Python es lento por la misma razón, además porque está operando en cadenas y no en punteros a cadenas, además porque es Python.

    – Brendan

    26 de noviembre de 2012 a las 7:21

  • example[a:] copia una cadena cada vez (O(N)). Entonces tu tipo es O(N*N*logN). Para la ilíada es ~10**12 operación que es lenta.

    – jfs

    26 de noviembre de 2012 a las 7:28

  • Dado que Programación Swines, err, lo siento, Pearls, se basa en gran medida en varias formas de comportamiento indefinido, no especificado e imp.definido, no puede traducir fácilmente el código a otro idioma que no tenga el mismo tipo de comportamiento no especificado.

    – Lundin

    26 de noviembre de 2012 a las 8:00

avatar de usuario
hynekcer

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.

  • el enlace anterior del ejemplo con pruebas está roto. ¿Podrías por favor actualizarlo?

    – gkoul

    11 de enero de 2018 a las 1:32

  • Arreglé los enlaces a mi código y a la C original pegando mis copias.

    – Hynekcer

    12 de enero de 2018 a las 2:47

  • ¡Gracias, tjameson! Pero incluso usando memoryviewaún necesita pasar la cadena a cmp, ¿derecho? Entonces, ¿todavía necesita pasar por valor?

    – Hanfei Sol

    26 de noviembre de 2012 a las 10:46

  • Este no funciona. Como cmp no se puede usar para memoryview objeto

    – Hanfei Sol

    26 de noviembre de 2012 a las 11:27

  • El código de Bentley sí no abuso strcmp. Simplemente lo usa para comparar cadenas en qsortque a su vez nunca se basa en nada más que en el señal del valor de retorno.

    – Fred Foo

    26 de noviembre de 2012 a las 19:51

  • @larsmans: como mencioné en mi comentario, me di cuenta de esto unos 5 minutos después de publicar. Justo cuando dejé de mirar el código… Revisando la respuesta.

    – beatgammit

    26 de noviembre de 2012 a las 20:07

  • la comparación de vista de memoria no funciona. Ver ejemplo en mi respuesta

    – jfs

    26 de noviembre de 2012 a las 23:19


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…

  • Si más de una subcadena repetida tiene la misma longitud máxima, no se devuelve nada. Ejemplo: ex = 'ABCxABCyDEFzDEF'

    – Hynekcer

    26 de noviembre de 2012 a las 12:57

  • @hynekcer el último conjunto siempre está vacío (esa es la condición de parada del ciclo), pero el anterior contiene: ['ABC', 'DEF'] — no veo por qué esto está mal? hay limitaciones obvias en mi código, solo se imprimen las 3 primeras cadenas, si hay más, tiene que modificar el código o algo así, la impresión bonita nunca fue mi objetivo.

    – Lenik

    26 de noviembre de 2012 a las 13:20

  • Espero que el resultado esté finalmente en la variable de la cadena, pero se pierden. La impresión de depuración no es importante para un algoritmo.

    – Hynekcer

    26 de noviembre de 2012 a las 13:28

  • La impresión de depuración de @hynekcer ayuda a comprender cómo funciona. si solo necesita la respuesta, guarde el resultado del filtrado en la variable temporal y cuando esté vacío, imprima lo que tenga en chains — eso debería funcionar bien para cualquier cantidad de subcadenas de cualquier longitud.

    – Lenik

    26 de noviembre de 2012 a las 13:31

  • El mayor problema es que su algoritmo puede requerir más de N * N / 4 bytes de memoria donde N es la longitud de la cadena de entrada. Ejemplo: ex = ' '.join('%03s' % i for i in range(500)) Yo imprimo sum(len(string) for string in chains) y veo que el mayor valor es 1001000. El tiempo requerido es proporcional a N * N * N.

    – Hynekcer

    26 de noviembre de 2012 a las 13:47


  • Si más de una subcadena repetida tiene la misma longitud máxima, no se devuelve nada. Ejemplo: ex = 'ABCxABCyDEFzDEF'

    – Hynekcer

    26 de noviembre de 2012 a las 12:57

  • @hynekcer el último conjunto siempre está vacío (esa es la condición de parada del ciclo), pero el anterior contiene: ['ABC', 'DEF'] — no veo por qué esto está mal? hay limitaciones obvias en mi código, solo se imprimen las 3 primeras cadenas, si hay más, tiene que modificar el código o algo así, la impresión bonita nunca fue mi objetivo.

    – Lenik

    26 de noviembre de 2012 a las 13:20

  • Espero que el resultado esté finalmente en la variable de la cadena, pero se pierden. La impresión de depuración no es importante para un algoritmo.

    – Hynekcer

    26 de noviembre de 2012 a las 13:28

  • La impresión de depuración de @hynekcer ayuda a comprender cómo funciona. si solo necesita la respuesta, guarde el resultado del filtrado en la variable temporal y cuando esté vacío, imprima lo que tenga en chains — eso debería funcionar bien para cualquier cantidad de subcadenas de cualquier longitud.

    – Lenik

    26 de noviembre de 2012 a las 13:31

  • El mayor problema es que su algoritmo puede requerir más de N * N / 4 bytes de memoria donde N es la longitud de la cadena de entrada. Ejemplo: ex = ' '.join('%03s' % i for i in range(500)) Yo imprimo sum(len(string) for string in chains) y veo que el mayor valor es 1001000. El tiempo requerido es proporcional a N * N * N.

    – Hynekcer

    26 de noviembre de 2012 a las 13:47


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad