Tarea 2

Tarea 2 - String matching

Hola, esta actividad consiste en realizar un programa en python sobre el tema de string matching. String matching son las coincidencias u ocurrencias de palabras (no necesariamente palabras) en una cadena de texto (no necesariamente de texto XD).

El escenario es el siguiente:

Dada una cadena de texto (T), y una cadena patrón (P), vamos a encontrar las ocurrencias presentadas. Por ejemplo:

T = (issttstsisitstsisitstttits)

P = (its)

Vamos a encontrar las veces que se hace un match, en el ejemplo anterior tendriamos 3 matches.

Los algoritmos que usaremos para la búsqueda de cadenas serán el de Boyer-Moore y el de Knuth-Morris-Pratt.

A continuación explicaré el funcionamiento del algoritmo Boyer-Moore

Boyer-Moore

El algoritmo Boyer-Moore es un algoritmo de búsqueda de cadenas desarrollado por Bob Boyer y J Strother Moore en 1977. Lo que este algoritmo hace es buscar la coincidencia del último elemento de la cadena patrón con un elemento cualquiera de una cadena de texto; por ejemplo si la cadena patrón es 'a,b,c' y la cadena de texto es 'ccbacababca', el algoritmo realiza una comparación entre c (último elemento de la cadena patrón) y la cadena de texto. En caso de que ocurra una coincidencia, ahora se comparará la penúltima posición de la cadena patrón con la ocurrencia en la cadena de texto-1. Luego si también hay concidencia se compara la antepenúltima posición de la cadena patrón con la posición de la cadena de texto-2 y así sucesivamente, lo que provoca un buen ahorro de tiempo en ejecución debido a que no tiene . En conclusión y resumidas cuentas, el algoritmo hace una verificación hacia atrás.

Yo realicé el código en python de manera sencilla, lo que hice fue iterar el recorrido de toda la cadena de texto, luego cuando enontraba match de una letra de la cadena con la última posición de la cadena patrón, tomaba una sub cadena de la cadena de texto, donde esa subcadena se compone de la letra match más las posiciones anteriores correspondientes a la cadena patrón, al final comparé la subcadena con la cadena patrón. Si la comparación arroja un "True" pues cuento un match. Y así hasta recorrer toda la cadena de texto.

A continuación el código:

import random 
from sys import argv
import string
import time

def boyer(largoM, largoN):

 #Para m = largo de texto, n = largo de patron
 archi=open('BM.dat','a') #Abro el archivo
 #largoM = int(argv[1]) 
 #largoN = int(argv[2])
 newporcent = 0.0
 M = []
 N = []
 com = []
 # Llenando listas ------------------------------------
 for i in range(largoM):
  let = random.choice(string.ascii_lowercase)
  M.append(let) #Rellenando la cadena de texto
  
 for j in range(largoN):
  let = random.choice(string.ascii_lowercase)
  N.append(let) #Rellenando el patron
 #print M
 #print N, "\n\n"

 # Algoritmo Boyer-Moore -------------------------------
 tiempoInicial = time.time()

 for x in range(largoM):
  if x >= largoN:
   if M[x] == N[-1]:
    miLargo = (x)-(largoN-1)
    com = M[miLargo:x+1]
    #print "i = ",x,  "  -  M[x] = ", M[x], " - com = ", com     
    print com
    if com == N:
     print "match: com = ", com, " - N = ", N 
     
    else:
     print "No exito :("

 tiempoFinal = time.time()
 d = tiempoFinal - tiempoInicial
 diferencia = round(d, 6) 
 
 newlargoM = str(largoM)
 newlargoN = str(largoN)   #Para poder meter los datos al dat
 newdiferencia = str(diferencia)
   
 if largoN != 10:  # Cuando el largo del patron es 9, saltamos 2 lineas en el dat
  archi.write(newlargoM) #Escribe largo de texto
  archi.write(' ')
  archi.write(newlargoN) # Escribiendo largo del patron 
  archi.write(' ')
  archi.write(newdiferencia) #Escribiendo los promedios de tiempo
  archi.write('\n')

 else:
  archi.write(newlargoM) #Lo mismo que arriba
  archi.write(' ')
  archi.write(newlargoN)
  archi.write(' ')  
  archi.write(newdiferencia)
  archi.write('\n\n')
 
 archi.close()   # Cerrando el archivo, se abre cada vez que se ejecuta esta subrutina

 
def main():
  for i in range(10): #Correr distintos tipos de largo de texto
   for j in range(10): #Correr distintos tipos de largo de patron  
    print "\nTransmitiendo con largo de texto = ", i+1, "y con patron = ", j+1      # Meramente informativo para el programador
    boyer(i+1, j+1) 
  

if __name__ == "__main__":
 main() 

Para poder graficar los tiempos hice que en un dat se fueran guardando los largos de cadena de texto y largos de cadena patrón, luego obtuve los tiempos para cada combinación. Al final realicé un plot con los datos obtenidos (como en la tarea anterior):

A continuación los datos obtenidos (en primera columna los largos de M ó largos de texto, en segunda columna los largos de N o patrón, y al final los tiempos obtenidos):

1 1 3e-06
1 2 3e-06
1 3 2e-06
1 4 3e-06
1 5 2e-06
1 6 2e-06
1 7 3e-06
1 8 2e-06
1 9 1e-06
1 10 2e-06

2 1 3e-06
2 2 2e-06
2 3 2e-06
2 4 2e-06
2 5 2e-06
2 6 2e-06
2 7 2e-06
2 8 2e-06
2 9 3e-06
2 10 2e-06

3 1 3e-06
3 2 2e-06
3 3 3e-06
3 4 2e-06
3 5 3e-06
3 6 2e-06
3 7 2e-06
3 8 3e-06
3 9 3e-06
3 10 2e-06

4 1 2e-06
4 2 2e-06
4 3 2e-06
4 4 2e-06
4 5 2e-06
4 6 3e-06
4 7 2e-06
4 8 2e-06
4 9 2e-06
4 10 2e-06

5 1 2e-06
5 2 3e-06
5 3 3e-06
5 4 2e-06
5 5 2e-06
5 6 2e-06
5 7 2e-06
5 8 2e-06
5 9 2e-06
5 10 2e-06

6 1 5.4e-05
6 2 4e-06
6 3 4.3e-05
6 4 2e-06
6 5 2e-06
6 6 2e-06
6 7 2e-06
6 8 2e-06
6 9 2e-06
6 10 2e-06

7 1 4.5e-05
7 2 2e-06
7 3 3e-06
7 4 2e-06
7 5 3e-06
7 6 2e-06
7 7 3e-06
7 8 2e-06
7 9 2e-06
7 10 1e-06

8 1 2e-06
8 2 1.8e-05
8 3 2e-06
8 4 1.8e-05
8 5 1.9e-05
8 6 1.8e-05
8 7 2e-06
8 8 1e-06
8 9 2e-06
8 10 2e-06

9 1 2e-06
9 2 2e-06
9 3 2e-06
9 4 1.9e-05
9 5 2e-06
9 6 2e-06
9 7 1e-06
9 8 2e-06
9 9 1e-06
9 10 2e-06

10 1 3e-06
10 2 2e-06
10 3 3e-06
10 4 2e-06
10 5 2e-06
10 6 2e-06
10 7 2e-06
10 8 2e-06
10 9 2e-06
10 10 2e-06


 

A continuación la gráfica obtenida:

Los resultados son tiempos bastante cortos y aceptables, donde es más tardado con largos 6 y 8 de texto y patrón respectivamente.

En la siguiente liga   se menciona más a detalle el funcionamiento de este algoritmo.

Quedo pendiente con el algoritmo Knuth-Morris-Pratt por falta de tiempo. 

Liga a mi git (se encuetra el archivo py, dat y el plot): https://github.com/eddypre/M-todosCodificaci-n

Bibliografía:

http://banyut.obolog.com/python-listas-115312
http://techerald.com/page/python-generacin-cadena-aleatoria-de-letras-maysculas-y-cifras.html

Cualquier duda o aclaración pueden dejarla en comentarios.

Saludos para todos!

Tarea 1

Tarea 1 - Transmisor de palabras

Hola, para esta primera tarea de la materia de métodos de transmisión se nos pidió realizar en python un programa generador y transmisor de palabras, la idea es que determináramos el porcentaje de éxito con el que se mandaban las palabras, es decir tiene que haber un match entre la palabra generada y la palabra transmitida. Y las palabras generadas y transmitidas se componen de cadenas binarias (0 y 1)

Para obtener los porcentajes de éxito debemos primero darle parámetros a nuestro transmisor, los parámetros con los que el generador/transmisor trabaja son:

- Largo de la palabra

- Frecuencia de ceros

- Porcentaje de ceros correctos

- Porcentaje de unos correctos  

El proceso que sigue mi transmisor es el siguiente:

El generador produce palabras de largo 2^0, 2^1, 2^2 ... 2^9, luego realiza el proceso de transmisión con frecuencias de cero de 0.1%, 0.2% ... 0.9% (obviando que las frecuencias de 1 es 1-frecuencia de ceros), los porcentajes de ceros y unos correctos se definen como parámetros al ejecutar el programa. Seguido de eso se empiezan a transmitir las palabras, luego se comparan las palabras generadas con las palabras transmitidas. Al final se obtienen porcentajes de éxito.

Todos estos valores antes mencionados se van grabando en un archivo .dat para luego ser graficados en un gnuplot y ser analizados más fácilmente.

A continuación les dejo con el código que realicé (generador y transmisor).

Parte del generador:

#Generador y transmisor de palabras
#Autor: Eduardo Triana
#FIME - ITS

import random 
from sys import argv

def generador(l, cer): #Generador y transmisor de palabras
 
 #freqzero = 0
 freqzero = (cer/10.0) + 0.1  
 
 #z = 1
 #for a in range(9):
 archi=open('canalTriana.dat','a') #Abro el archivo donde se almacenaran todas las probabilidades de exito, junto con los largos y frecuencias
 #length = int(argv[1])
 length = pow(2,l) #El largo del archivo lo elevamos a la "l", necesito l para generar el dat
 
 #freqzero = float(argv[1]) Esto ya va arriba, y ya no es con parametro
 zerocorrect = float(argv[1])
 onecorrect = float(argv[2]) # El orden de parametros por consola es: 1) Porcentaje de ceros correctos. 2) Porcentaje de unos correctos. 3) Repeticiones
 repet = int(argv[3])

 conteo0 = 0
 conteo1 = 0

 freqzeroProduct = freqzero*length
 listaG = []
  
 for i in range(length): #Todo esto es para generar cada una de las palabras
  bit = int(random.randint(0,1))
  if bit == 0:  
   if freqzeroProduct > conteo0: #Agregando los bits para formar las cadenas de palabras
    listaG.append(0)
    conteo0 = conteo0 + 1
   else:
    listaG.append(1)
  else:
   listaG.append(1)
 print "Generated:  " ,listaG  #Imprimiendo la palabra generada

Parte del transmisor:

#Transmision de palabras
 
 zerocorrect = zerocorrect*length  
 onecorrect = onecorrect*length    
 exitos = 0.0
 #print "zerocorrect:", zerocorrect
 #print "onecorrect: ", onecorrect, "\n"

 # Todo lo que sigue corresponde a la transmision de las palabras

 for j in range(repet):
  conteo0 = 0
  contCorr0 = 0
  contCorr1 = 0
  listaT = []
  for k in range(length):
   bitransmited = int(random.randint(0,1))
   if bitransmited == 0:  
    if freqzeroProduct > conteo0:
     if zerocorrect > contCorr0:
      listaT.append(0)  #Esto es para que la frecuencia de ceros corresponda a la que indicamos
      conteo0 = conteo0 + 1
      contCorr0 = contCorr0 + 1
     else:
      listaT.append(1)
      contCorr1 = contCorr1 + 1
    else:
      listaT.append(1)
   else:
    if onecorrect > contCorr1:
     listaT.append(1)
     contCorr1 = contCorr1 + 1  #Si ya rebasamos el limite de ceros creados, ahora ponemos unos
    else:
     listaT.append(0)
     contCorr0 = contCorr0 + 1
  if listaT == listaG:  #Comparamos el contenido de las listas de palabras transmitidas con las generadas
   exitos = exitos + 1 #Elevamos en 1 el exito obtenido
  print "Transmited: ", listaT
 porcent = (exitos/repet) #Creamos el porcentaje de exito, esto sera la columna 3 de nuestro archivo dat, es lo mero mero
 print "\n", repet
 print exitos 
 print porcent
 
 newl = str(l)    #
 newfreqzero = str(freqzero)  # Convirtiendo a string todos los datos para poder escribirlos en nuestro dat
 newporcent = str(porcent)  #
   
 if cer != 8:    # Cuando la frecuencia de ceros ya sea 0.9, saltamos 2 lineas en el dat
  archi.write(newl)
  archi.write(' ')
  archi.write(newfreqzero) # Escribiendo en el dat 
  archi.write(' ')
  archi.write(newporcent)
  archi.write('\n')

 else:
  archi.write(newl)
  archi.write(' ')
  archi.write(newfreqzero)
  archi.write(' ')  #Escribiendo en el dat
  archi.write(newporcent)
  archi.write('\n\n')
 
 archi.close()   # Cerrando el archivo, se abre cada vez que se ejecuta esta subrutina

Llamando a la función que genera/transmite con largo de palabras desde potencia 0,1,2 hasta 9, y con valores de frecuencias de 0 desde 0.1, 0.2 hasta 0.9:

def main():

 for i in range(10):  #Para poder correr el transmisor con potencias desde 0 hasta la 9
  for j in range(9): #Para poder correr el transmisor con frecuencias de zero desde 0.1 hasta 0.9  
   print "\nTransmitiendo con largo = ", i, "y con freqzero = ", j      # Meramente informativo para el programador
   generador(i, j) #Correr el generador/transmisor con largos y frecuencias distintas

 #i = 1
 #while i <= 512:
  #generador(i)
 # i = i*2

if __name__ == "__main__":
 main()

Ejecutando mi generador/transmisor con los parámetros 0.8 y 0.8 20, que corresponden a la porcentaje de ceros correctos, unos correctos y repeticiones(esto es las veces con las que se promedia el experimento, es decir, se transmite 20 veces las palabras y se obtiene un promedio de éxito, decidí que lo pusiera como parametro el usuario para tener escenarios más amplios):

Algo de lo que se ve cuando se está ejecutando el transmisor, son las palabras generadas y transmitidas, esto lo hace para cada iteración de largo de palabras (esto no es tan relevante).

Ahora les muestro el archivo dat obtenido:

Esto es el archivo dat resultante con valores 0.8, 0.8 y 20, que corresponde a porcentajes de cero correctos, unos correctos y repeticiones respectivamente. Va con largos de palabra desde potencia 0 hasta 9 (con base 2, primera columna) y frecuencias desde 0.1 hasta 0.9 (segunda columna), la tercera columna corresponde a los porcentajes de éxito.

0 0.1 0.55
0 0.2 0.45
0 0.3 0.45
0 0.4 0.6
0 0.5 0.5
0 0.6 0.7
0 0.7 0.5
0 0.8 0.35
0 0.9 0.55

1 0.1 0.55
1 0.2 0.15
1 0.3 0.35
1 0.4 0.5
1 0.5 0.4
1 0.6 0.2
1 0.7 0.05
1 0.8 0.35
1 0.9 0.25

2 0.1 0.1
2 0.2 0.3
2 0.3 0.35
2 0.4 0.0
2 0.5 0.0
2 0.6 0.05
2 0.7 0.1
2 0.8 0.1
2 0.9 0.05

3 0.1 0.45
3 0.2 0.0
3 0.3 0.0
3 0.4 0.0
3 0.5 0.0
3 0.6 0.0
3 0.7 0.0
3 0.8 0.0
3 0.9 0.0

4 0.1 0.25
4 0.2 0.0
4 0.3 0.0
4 0.4 0.0
4 0.5 0.0
4 0.6 0.0
4 0.7 0.0
4 0.8 0.0
4 0.9 0.0

5 0.1 0.0
5 0.2 0.0
5 0.3 0.0
5 0.4 0.0
5 0.5 0.0
5 0.6 0.0
5 0.7 0.0
5 0.8 0.0
5 0.9 0.0

6 0.1 0.0
6 0.2 0.0
6 0.3 0.0
6 0.4 0.0
6 0.5 0.0
6 0.6 0.0
6 0.7 0.0
6 0.8 0.0
6 0.9 0.0

7 0.1 0.0
7 0.2 0.0
7 0.3 0.0
7 0.4 0.0
7 0.5 0.0
7 0.6 0.0
7 0.7 0.0
7 0.8 0.0
7 0.9 0.0

8 0.1 0.0
8 0.2 0.0
8 0.3 0.0
8 0.4 0.0
8 0.5 0.0
8 0.6 0.0
8 0.7 0.0
8 0.8 0.0
8 0.9 0.0

9 0.1 0.0
9 0.2 0.0
9 0.3 0.0
9 0.4 0.0
9 0.5 0.0
9 0.6 0.0
9 0.7 0.0
9 0.8 0.0
9 0.9 0.0

Al final así es como se ve la gráfica generada en gnuplot:

Ahora hago el experimento con probabilidades menores de obtener ceros y unos correctos, con la misma cantidad de repeticiones:

El siguiente es el archivo dat obtenido tras correr el experimento con los parámetros mencionados:

0 0.1 0.5
0 0.2 0.6
0 0.3 0.6
0 0.4 0.65
0 0.5 0.5
0 0.6 0.5
0 0.7 0.6
0 0.8 0.6
0 0.9 0.5

1 0.1 0.7
1 0.2 0.45
1 0.3 0.55
1 0.4 0.0
1 0.5 0.6
1 0.6 0.0
1 0.7 0.0
1 0.8 0.0
1 0.9 0.0

2 0.1 0.15
2 0.2 0.25
2 0.3 0.0
2 0.4 0.0
2 0.5 0.5
2 0.6 0.3
2 0.7 0.1
2 0.8 0.0
2 0.9 0.0

3 0.1 0.45
3 0.2 0.0
3 0.3 0.0
3 0.4 0.15
3 0.5 0.0
3 0.6 0.0
3 0.7 0.0
3 0.8 0.0
3 0.9 0.0

4 0.1 0.0
4 0.2 0.0
4 0.3 0.0
4 0.4 0.0
4 0.5 0.0
4 0.6 0.0
4 0.7 0.0
4 0.8 0.0
4 0.9 0.0

5 0.1 0.0
5 0.2 0.0
5 0.3 0.0
5 0.4 0.0
5 0.5 0.0
5 0.6 0.0
5 0.7 0.0
5 0.8 0.0
5 0.9 0.0

6 0.1 0.0
6 0.2 0.0
6 0.3 0.0
6 0.4 0.0
6 0.5 0.0
6 0.6 0.0
6 0.7 0.0
6 0.8 0.0
6 0.9 0.0

7 0.1 0.0
7 0.2 0.0
7 0.3 0.0
7 0.4 0.0
7 0.5 0.0
7 0.6 0.0
7 0.7 0.0
7 0.8 0.0
7 0.9 0.0

8 0.1 0.0
8 0.2 0.0
8 0.3 0.0
8 0.4 0.0
8 0.5 0.0
8 0.6 0.0
8 0.7 0.0
8 0.8 0.0
8 0.9 0.0

9 0.1 0.0
9 0.2 0.0
9 0.3 0.0
9 0.4 0.0
9 0.5 0.0
9 0.6 0.0
9 0.7 0.0
9 0.8 0.0
9 0.9 0.0

Y la gráfica resultante con los datos obtenidos es la siguiente:

Ahora el código para realizar el plot en gnuplot:

set term postscript eps color 10
set view map
set pm3d map
set cbrange[0:100]
set xlabel 'Word length (power of 2)'
set ylabel 'Frequency of zeroes'
set title 'Avg. prob. of correct transmission'
set output "canalTriana.eps"
set palette color positive
set key off
set size square
set yrange [0.05:0.95]
set xrange [-0.75:9.75]
set xtics 0, 1
set ytics 0.1, 0.1
splot "canalTriana.dat" using ($1-0.5):($2+0.05):($3*100.0)

En la bibliografía agrego una liga que me sirvió a la hora de implementar archivos de texto en python (lectura, escritura).

Liga a mi git: https://github.com/eddypre/M-todosCodificaci-n

PD: Traduje del libro de Shannon de la página 41 a la página 45. 

Bibliografía:

http://pythonya.appspot.com/detalleconcepto?deta=Creaci%C3%B3n,%20carga%20y%20lectura%20de%20archivos%20de%20texto

Cualquier duda o aclaración pueden ponerla en comentarios. 

Saludos a todos!