Búsqueda flexible y eficiente en texto con paralelismo de Bits

Abstract

El emparejamiento de secuencias se puede entender como el problema de encontrar un patrón con una cierta característica dentro de una secuencia dada de símbolos. El caso más simple es el de encontrar una secuencia dada dentro de la otra secuencia más larga. Este es uno de los más viejos y más penetrantes problemas en informática. Los usos que requieren una cierta forma de emparejamiento de secuencias se pueden encontrar virtualmente por todas partes. Sin embargo, los años recientes han atestiguado un aumento dramático en interés en problemas que emparejan secuencias, especialmente dentro de las comunidades que han crecido más rápidamente como la recuperación de datos y la Biocomputacion. Estas comunidades están haciendo frente no solamente a un aumento drástico en los tamaños del texto que tienen que manejar, sino que también están exigiendo búsquedas más rápidas y sofisticadas. Los patrones de interés no son secuencias simples, sino que también incluyen comodines, boquetes, y expresiones regulares. La definición de un calce puede también permitir diferencias leves entre el patrón y su ocurrencia en el texto. Esto se llama “emparejamiento aproximado” y es especialmente interesante en la recuperación del texto y la biología de cómputo El objetivo de esta investigación es el diseño, análisis e implementación de nuevos algoritmos de búsqueda flexible y eficiente en texto mediante el uso de una nueva técnica que hace uso inherente de la capacidad que tienen las computadoras para hacer operaciones de bits en forma paralela. El objetivo de este trabajo de investigación es el desarrollo y análisis de nuevos algoritmos para resolver el problema de búsqueda aproximada en texto bajo distintas condiciones, así como una mejor comprensión del problema mismo y su comportamiento estadístico. Si bien nuestros resultados pueden ser validos en diversas áreas, centramos nuestra atención en la búsqueda en texto típica de las aplicaciones de recuperación de información.