Publicado · en mejora
Algorithm
Los algoritmos de cadenas buscan patrones en textos y palabras por prefijo; KMP, Rabin-Karp, los tries y el algoritmo Z son las técnicas clave.
Los algoritmos de cadenas son métodos para comparar y buscar secuencias de caracteres de forma rápida y correcta. El problema central es la búsqueda de patrones: encontrar todas las posiciones en las que un patrón corto aparece dentro de un texto largo. También forman parte de este campo buscar todas las palabras de un diccionario que empiezan por un prefijo y localizar muchos patrones a la vez. El método ingenuo, que compara en cada posición, puede tardar un tiempo proporcional al producto de la longitud del texto y la del patrón.
La búsqueda en editores, la búsqueda en registros, el autocompletado, la detección de intrusiones, la sincronización de archivos y el análisis de genomas se apoyan en algoritmos de cadenas. KMP reutiliza las comparaciones ya hechas mediante una tabla de fallos y garantiza tiempo lineal, Rabin-Karp desliza un hash rodante por el texto para evitar la mayoría de las comparaciones, y un trie comparte los prefijos comunes, de modo que buscar un prefijo solo depende de la longitud de la palabra. Además, es un tema habitual en entrevistas técnicas.
Conviene empezar por el vocabulario de prefijos, sufijos y bordes, y comprobar a mano por qué la búsqueda ingenua es lenta. Después, calcule usted mismo la función de prefijos de un patrón pequeño, implemente la búsqueda KMP y un trie, y compare los resultados con la biblioteca estándar. Por último, revise las trampas que estropean los resultados en la práctica, como las colisiones de hash y la normalización Unicode.
Se calcula de antemano el borde más largo de cada prefijo del patrón; ante un desajuste se salta a un borde más corto sin retroceder en el texto, con un coste de O(n + m).
Rabin-Karp actualiza en O(1) el hash de cada ventana de longitud m, lo compara con el hash del patrón y solo compara caracteres cuando los hashes coinciden.
Un árbol que se recorre carácter a carácter; los prefijos comunes se guardan una sola vez, así que la búsqueda por prefijo y el autocompletado dependen solo de la longitud de la palabra.
El arreglo Z da, para cada posición y en tiempo lineal, el prefijo común más largo con la cadena completa. Con texto real hay que cuidar la normalización y las unidades de índice.
prefix_function calcula el borde más largo de cada prefijo del patrón, y kmp_search usa esa tabla para leer el texto una sola vez, de izquierda a derecha, y reunir todas las posiciones de inicio. Como k vuelve a pi[k - 1] tras cada coincidencia, también encuentra apariciones solapadas como las de 0 y 2. Ejecute python string_search.py para ver ambos resultados.
string_search.py
def prefix_function(p: str) -> list[int]:
"""pi[i] = length of the longest proper border of p[:i + 1]."""
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp_search(text: str, pattern: str) -> list[int]:
"""Start positions of every (possibly overlapping) occurrence."""
if not pattern:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
hits, k = [], 0
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = pi[k - 1]
if ch == pattern[k]:
k += 1
if k == len(pattern):
hits.append(i - k + 1)
k = pi[k - 1]
return hits
if __name__ == "__main__":
print(prefix_function("ababaca")) # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("abababcabab", "abab")) # [0, 2, 7]
python string_search.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Algoritmos de cadenas.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Algoritmos de cadenas.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.