jueves, 21 de febrero de 2013

Entrada # 2

Teoría de la Información y Métodos de Codificación

Para esta entrada se nos encargo una simulación utilizando los métodos de búsqueda para palabras.

El primer método es el de Boyer-Moore.

Es un Algoritmo de búsqueda de cadenas desarrollado por Bob Boyer y J Strother Moore en 1977.


El algoritmo funciona de esta manera:



  • Teniendo una frase o cadena de caracteres se pretende buscar una palabra en esta cadena.
  • La palabra se pre procesada  primero invierte la palabra: si la palabra es "perro" se convierte a "orrep".
  • Teniendo la palabra pre procesada se elimina el primer carácter de este.
  • Después se genera una especie de patrón, el cuál contiene la palabra y las letras de la frase que no están en la palabra.
  • Teniendo estos datos el proceso del algoritmo seria un ciclo repetitivo del siguiente paso hasta que se haya encontrado la palabra en la frase o ya se halla pasado por toda la frase.
  • Se colocan la palabra al principio de la frase y se hace una comparación de derecha a izquierda, si el ultimo elemento de la palabra es diferente a la letra de la frase que se encuentra en la misma posición 
Generalmente el algoritmo es más rápido cuanto más grande es la clave que es buscada, usa la información conseguida desde un intento para descartar tantas posiciones del texto como sean posibles en donde la cadena no coincida.

Solo tengo un mugrero de código.

1 comentario:

  1. Faltó el segundo algoritmo y el experimento. 2 pts código, 1 pt reporte.

    ResponderEliminar