PDF de programación - Algoritmos con Python - Cadenas de caracteres

Algoritmos con Python

Cadenas de caracteres

26 de febrero de 2021

Índice

1 Anagramas

1.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 T9: texto en 9 teclas

2.1 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Revisión ortográfica con un árbol lexicográfico

3.1 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Corrección ortográfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Búsqueda de patrones

4.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Algoritmo ingenuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
2
2

3
3
3
3

6
6
6
6

9
9
9
9

5 Límites máximos: Knuth-Morris-Pratt

10
5.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2 Algoritmo y prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.3 Ilustración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.4 Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.5 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.6 Aplicación: Encuentre el palíndromo de límite más largo . . . . . . . . . . . . . . 14
5.7 Aplicación: encuentre un patrón t en la cadena s . . . . . . . . . . . . . . . . . . 14
5.8 Método proporcionado por el lenguaje Python . . . . . . . . . . . . . . . . . . . . 15
5.9 Aplicación: Determine la mayor potencia entera de una palabra . . . . . . . . . 16
5.10Prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.11Aplicación: Conjugado de una palabra . . . . . . . . . . . . . . . . . . . . . . . . . 17

6 Coincidencia de patrones Rabin-Karp

18
6.1 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.2 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.3 Función Rolling Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.4 Variante: La búsqueda de múltiples patrones . . . . . . . . . . . . . . . . . . . . . 20
6.5 Variante: factor común . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.6 Variante: factor común con longitud máxima . . . . . . . . . . . . . . . . . . . . . 21

7 Palíndromo más largo de una cadena: Manacher

23
7.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

I

7.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.4 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

II

Introducción

La resolución de problemas relacionados con cadenas de caracteres (o simplemente cade-
nas) se convirtió rápidamente en un dominio importante en el estudio de algoritmos. Estos
problemas ocurren, por supuesto, en el procesamiento de texto, como la revisión ortográ-
fica y la búsqueda de factores (subcadenas) o patrones más generales. Con el desarrollo
de la bioinformática, surgieron nuevos problemas en la alineación de las cadenas de ADN.
Este texto presenta una selección de algoritmos de procesamiento de cadenas que consi-
deramos importantes.

Una cadena de caracteres podría representarse internamente mediante una lista de sím-
bolos, pero, en general, usamos el tipo nativo de Python str, que se comporta esencial-
mente como una lista. Los caracteres se pueden codificar con dos bytes para una codifica-
ción Unicode, pero generalmente se codifican con un solo byte, utilizando la codificación
ASCII: cada entero entre 0 y 127 corresponde a un carácter distinto, y los códigos están
organizados de tal manera que los símbolos sucesivos ’0’ a ’9’, ’a’ a ’z’ y ’A’ a ’Z’ son con-
secutivos. Por lo tanto, si una cadena s contiene solo mayúsculas, podemos recuperar el
rango de la i-ésima letra calculando ord(s[i]) - ord(’A’). Por el contrario, la j-ésima
letra mayúscula del alfabeto numerada desde 0 se obtiene con chr(j + ord(’A’)).

Cuando hablamos de un factor (o subcadena) de una cadena, requerimos que los caracte-
res sean consecutivos, en contraste con la noción más general de una subsecuencia.

1

1. Anagramas

1.1. Definición

Una palabra w es un anagrama de una palabra v si existe una permutación de las letras
que transforman w en v. Dado un conjunto de n palabras de longitud como máximo k, nos
gustaría detectar todos los anagramas posibles.

1.2. Complejidad

El algoritmo propuesto resuelve este problema en el tiempo O(n k log k) en promedio, y en
O(n2 k log k) en el peor de los casos, debido al uso de un diccionario.

1.3. Algoritmo

La idea es calcular una firma para cada palabra, de modo que dos palabras sean anagra-
mas entre sí si y solo si tienen la misma firma. Esta firma es simplemente una nueva
cadena formada por las mismas letras ordenadas en orden lexicográfico.

La estructura de datos utilizada es un diccionario que asocia a cada firma la lista de pala-
bras con esta firma.

def anagrams(S):

d = {}
for word in S:

# S is a set of strings
# maps s to list of words with signature s
# group words according to the signature

s = .join(sorted(word)) # calculate the signature
if s in d:

d[s].append(word)

# append a word to an existing signature

else:

d[s] = [word]

# add a new signature and its first word

# -- extract anagrams, ingoring anagram groups of size 1
return [d[s] for s in d if len(d[s]) > 1]

2

2. T9: texto en 9 teclas

Entrada: 2665687

Salida: bonjour

2.1. Aplicación

Los teléfonos móviles con teclas ofrecen un modo de entrada interesante, a veces llamado
T9. Las 26 letras del alfabeto se distribuyen entre las teclas 2 a 9, como en la Figura 1.

Para ingresar una palabra, basta con ingresar la correspondiente secuencia de dígitos. Sin
embargo, como varias palabras pueden comenzar con los mismos dígitos, se debe utili-
zar un diccionario para proponer la palabra más probable. En todo momento, el teléfono
muestra el prefijo de la palabra más probable correspondiente a la secuencia de dígitos
introducida.

2.2. Definición

La primera parte de la instancia del problema es un diccionario, compuesto de pares (m,
w) donde m es una palabra sobre el alfabeto de 26 letras minúsculas y w es un peso de la
importancia de la palabra. La segunda parte es una serie de secuencias de dígitos del 2
al 9. Para cada secuencia s, se mostrará la palabra del diccionario de peso máximo. Una
palabra m corresponde a s si s es un prefijo de la secuencia t obtenida de m reemplazando
cada letra por el dígito correspondiente, de acuerdo con la tabla de correspondencia que
se muestra en la Figura 1. Por ejemplo, ’bonjour’ corresponde a 26, pero también a 266 o
2665687.

2.3. Algoritmo

La complejidad es O(n k) para la inicialización del diccionario y O(k) para cada solicitud,
donde n es el número de palabras en el diccionario y k un límite superior en la longitud de
las palabras.

En una primera fase, calculamos para cada prefijo p de una palabra del diccionario el
peso total de todas las palabras con prefijo p. Este peso se almacena en un diccionario
total_weight. En una segunda fase, almacenamos en un diccionario prop[seq] el prefijo
a proponer para una secuencia dada seq. Un escaneo sobre las claves en total_weight
permite determinar el prefijo con mayor peso.

Un ingrediente principal es la función code_word, que para una palabra dada devuelve la
secuencia correspondiente de dígitos.

3

Figura 1: Las teclas de un teléfono móvil

Para mejorar la legibilidad, la implementación a continuación está en O(nk2).

t9 = "22233344455566677778889999"
#

abcdefghijklmnopqrstuvwxyz

mapping on the phone

def letter_to_digit(x):
assert a <= x <= z
return t9[ord(x) - ord(a)]

def code_word(word):

return .join(map(letter_to_digit, word))

def predictive_text(dic):

# total_weight[p] = total weight of words having prefix p
total_weight = {}
for word, weight in dic:

prefix = ""
for x in word:

prefix += x
if prefix in total_weight:

total_weight[prefix] += weight

else:

total_weight[prefix] = weight

4

prop[s] = prefix to display for s

#
prop = {}
for prefix in total_weight:
code = code_word(prefix)
if (code not in prop

or total_weight[prop[code]] < total_weight[prefix]):

prop[code] = prefix

return prop

def propose(prop, seq):

if seq in prop:

return prop[seq]

return None

5

3. Revisión ortográfica con un árbol lexicográfico

3.1. Aplicación

¿Cómo se deben almacenar las palabras de un diccionario para implementar un corrector
ortográfico?

Para una palabra determinada, nos gustaría encontrar rápidamente una palabra de dic-
cionario cercana a ella en el sentido de la distancia de edición de Levenshtein. Si alma-
cenamos las palabras del diccionario en una tabla hash, perdemos toda la información
de proximidad entre palabras. Es mejor almacenarlos en un árbol lexicográfico, también
conocido como árbol de prefijos o trie (pronunciado como ’trái’).

3.2. Definición

Un trie es un árbol que almacena un conjunto de palabras. Los bordes de un nodo hacia
sus hijos están etiquetados con letras distintas. Cada pa