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

Im谩gen de pdf Algoritmos con Python - Cadenas de caracteres

Algoritmos con Python - Cadenas de caracteresgr谩fica de visualizaciones

Publicado el 7 de Marzo del 2021
1.942 visualizaciones desde el 7 de Marzo del 2021
435,5 KB
28 paginas
Creado hace 4a (26/02/2021)
Algoritmos con Python

Cadenas de caracteres

26 de febrero de 2021

脥ndice

1 Anagramas

1.1 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 T9: texto en 9 teclas

2.1 Aplicaci贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Revisi贸n ortogr谩铿乧a con un 谩rbol lexicogr谩铿乧o

3.1 Aplicaci贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 De铿乶ici贸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Correcci贸n ortogr谩铿乧a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 B煤squeda de patrones

4.1 De铿乶ici贸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 De铿乶ici贸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 De铿乶ici贸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谩-
铿乧a 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 codi铿乧ar con dos bytes para una codi铿乧a-
ci贸n Unicode, pero generalmente se codi铿乧an con un solo byte, utilizando la codi铿乧aci贸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 鈥檢鈥 y 鈥橝鈥 a 鈥橺鈥 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(鈥橝鈥). Por el contrario, la j-茅sima
letra may煤scula del alfabeto numerada desde 0 se obtiene con chr(j + ord(鈥橝鈥)).

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. De铿乶ici贸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 铿乺ma para cada palabra, de modo que dos palabras sean anagra-
mas entre s铆 si y solo si tienen la misma 铿乺ma. Esta 铿乺ma es simplemente una nueva
cadena formada por las mismas letras ordenadas en orden lexicogr谩铿乧o.

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

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 pre铿乯o de la palabra m谩s probable correspondiente a la secuencia de d铆gitos
introducida.

2.2. De铿乶ici贸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 pre铿乯o 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, 鈥檅onjour鈥 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 pre铿乯o p de una palabra del diccionario el
peso total de todas las palabras con pre铿乯o p. Este peso se almacena en un diccionario
total_weight. En una segunda fase, almacenamos en un diccionario prop[seq] el pre铿乯o
a proponer para una secuencia dada seq. Un escaneo sobre las claves en total_weight
permite determinar el pre铿乯o 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谩铿乧a con un 谩rbol lexicogr谩铿乧o

3.1. Aplicaci贸n

驴C贸mo se deben almacenar las palabras de un diccionario para implementar un corrector
ortogr谩铿乧o?

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谩铿乧o, tambi茅n
conocido como 谩rbol de pre铿乯os o trie (pronunciado como 鈥檛r谩i鈥).

3.2. De铿乶ici贸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
  • Links de descarga
http://lwp-l.com/pdf18966

Comentarios de: Algoritmos con Python - Cadenas de caracteres (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoraci贸n
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar im谩genes, archivos y/o videos.

Puedes registrarte o validarte desde aqu铆.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
gui帽o
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad