busqueda+proyecto+texto

8/14/2019 Busqueda+Proyecto+Texto

1/18

Bsqueda Aproximada Directamente EnTexto Comprimido

Carlos Avendao Prez, Claudia Feregrino Uribe, GonzaloNavarro Badino.

Reporte Tcnico No. CCC-04-00722 de Julio de 2004

Coordinacin de Ciencias ComputacionalesINAOE

Luis Enrique Erro 1Sta. Ma. Tonantzintla,


2/18


3/18

La bsqueda de patrones dentro de un texto se define como:

Dado un patrn y un textomppP ...1= uttT ...1= , ambas secuencias de caracteressobre el alfabeto finito , encontrar todas las coincidencias de P en , es decir,

encontrar el conjunto

T

{ }xPyTx =, .

Sin embargo, es comn encontrar documentos que contienen palabras mal escritas,esto propiciado al capturar los documentos o a partir de software de reconocimientoptico, entre otros, lo cual hace imposible recuperar estos documentos a menos que secometa el mismo error en la consulta.

Una generalizacin del problema de bsqueda de patrones es la bsquedaaproximada de patrones [1], en la cual se tiene un patrn y un margen de error k, que esla mxima distancia permitida entre el patrn y sus coincidencias en el texto.

Formalmente, hay que encontrar el conjunto { yxPTxP ',' = y , dondees la distancia de edicin entre ambas cadenas. En este trabajo se considera la

distancia de Levenshtein [2], la cual se define como el menor nmero de inserciones,

eliminaciones, o reemplazos de caracteres necesarios para hacer iguales dos palabras.

}kPPed )',()',( PPed

Una parte del problema de bsqueda de patrones est relacionada con la compresin

de texto [3]. La compresin de texto es una opcin para reducir el espacio necesario parael almacenamiento de las colecciones de texto y su transmisin por la red. Existendiversos mtodos de compresin, entre ellos los de la familia Ziv-Lempel particularmenteLZ78 [4] y LZW [5], los cuales son muy populares por su buena razn de compresincombinados con un tiempo eficiente de compresin y descompresin.

El problema de bsqueda de patrones sobre texto comprimido fue definido por primeravez en el trabajo de Amir y Benson [6] de la siguiente manera:

Dado un texto , cuyo texto comprimido correspondiente es , y

un patrn , encontrar todas las coincidencias de enuttT ...1= nzzZ ...1=

mppP ...1= P T , usando

solamente Z .

Un excelente ejemplo donde el problema de bsqueda de patrones y la compresin detexto se combinan son las bases de datos de texto, dado que el texto debe estarcomprimido para ahorrar espacio de almacenamiento y tiempo de transmisin en la red y,al mismo tiempo se deben realizar bsquedas eficientes sobre ellas. La bsquedaaproximada de patrones directamente sobre texto comprimido fue tratada por primera vezen 1992 en [6]. Desde entonces han surgido soluciones [7, 8] que en la prctica resultanms lentas que descomprimir primero el texto y hacer la bsqueda despus.


4/18

solucin es hasta 3 veces ms rpida que los mejores algoritmos [10] y [11] parabsqueda aproximada que primero descomprimen el texto y despus ejecutan la

bsqueda.

2 Conceptos Bsicos

En esta seccin se esbozan conceptos y notaciones importantes necesarios paracomprender este trabajo. Se asume que el lector tiene conocimientos bsicos sobrealgoritmos de bsqueda de texto y compresin de texto. Se inicia con una breveexplicacin sobre algoritmos de bsqueda de patrones monopatrn, multipatrn ybsqueda aproximada. Despus se detallan los algoritmos de compresin LZ78 y LZW,finalizando con una breve explicacin sobre paralelismo de bits.

2.1 Bsqueda de patrones.

Bsqueda monopatrn. El problema de bsqueda de patrones trata de encontrar todaslas coincidencias de un patrn mppP ...1= en el texto uttT ...1= , donde tanto yP T son

secuencias de caracteres sobre un alfabeto finito .

Los algoritmos de bsqueda monopatrn se pueden clasificar de acuerdo a la formaen que buscan el patrn en el texto. Todos ellos utilizan una ventana de bsqueda deltamao del patrn, la cual se desliza de izquierda a derecha a lo largo del texto, y dentrode la cual se busca el patrn, el esquema general se muestra en la figura 1.

Figura 1. Bsqueda monopatrn: La bsqueda se realiza en una ventana que se desplazaa lo largo del texto. La ventana de bsqueda es del tamao del patrn.

La diferencia entre los algoritmos radica en la forma en que la ventana se desplaza.Dada una cadena , , y , se dice que es prefijo dex y z x xy , un sufijo de , y un factor

de . En base a esto ltimo la clasificacin de los algoritmos de bsqueda demonopatrn es la siguiente:

yx

yxz

Bsqueda por prefijo (figura 2) La bsqueda se hace hacia delante en la ventana de


5/18

Figura 2. Bsqueda monopatrn por prefijo: Se busca el prefijo ms largo del patrn en laventana de bsqueda.

Bsqueda por sufijo (figura 3). La bsqueda se hace hacia atrs a lo largo de la ventanade bsqueda, se lee el sufijo ms largo de la ventana que tambin es un sufijo del patrn.Este mtodo permite evitar leer algunos caracteres del texto. El algoritmo ms famosoque utiliza este mtodo es el de Boyer-Moore[9].

Figura 3. Bsqueda monopatrn por sufijo: Se busca un sufijo del patrn en la ventana debsqueda.

Bsqueda por Factor (figura 4). La bsqueda se hace hacia atrs en la ventana debsqueda, buscando el sufijo ms largo de la ventana que tambin es un factor del

patrn. La principal desventaja de este mtodo es que requiere una forma para reconocerel conjunto de factores del patrn, lo cual es bastante complejo.

Figura 4. Bsqueda monopatrn por factor: Se busca un factor del patrn en la ventana debsqueda.

Estas tres formas para buscar un patrn permiten a los algoritmos ser eficientes endistintos casos, dependiendo del tamao del patrn y el tamao del alfabeto.


6/18

hace sobre un texto . El objetivo es encontrar todos los pares tal queuttT ...1= ji,

jpjtt i ...

1+sea igual a .

ip

La solucin ms simple a este problema es realizar r bsquedas con alguno de los

algoritmos clsicos de bsqueda monopatrn. Esto lleva a una complejidad en el peor delos casos de . La complejidad de la fase de bsqueda se puede reducir a

(donde es el nmero total de coincidencias) usando algn tipo deextensin de los algoritmos de bsqueda monopatrn.

)(ru

)( noccu + nocc

Los tres esquemas para bsqueda monopatrn se aplican para bsqueda multipatrn.Para cada esquema existen diversas extensiones posibles de acuerdo a la forma en quese manipula el conjunto de patrones y a cmo se obtienen los desplazamientos.

Bsqueda aproximada. Una generalizacin del problema de bsqueda de patrones esla bsqueda aproximada de patrones o tambin conocida como bsqueda permitiendoerrores, en la cual se tiene un patrn P y un margen de error k.

Este problema tiene sentido slo si mk


7/18

Figura 5. Ejemplo del algoritmo de programacin dinmica para buscar incidir en el textocoincidencia permitiendo 2 errores. Los nmeros resaltados indican las posiciones

finales de las coincidencias en el texto.

Algoritmos basados en autmatas. El problema de bsqueda aproximada se puedereducir al problema de un autmata finito no determinstico (NFA). Por ejemplo, si setienen k= 2 errores tal como se muestra en la figura 6, cada fila representa el nmero deerrores obtenidos. La primera fila representa cero errores, la segunda 1 error y assucesivamente. Cada una de las columnas representa la coincidencia de un prefijo delpatrn.

|Figura 6. Un Autmata finito no determinstico para bsqueda aproximada de la cadenapatrn permitiendo 2 errores.

Cada que se lee un carcter del texto el autmata cambia de estado. Las flechas

horizontales representan la coincidencia de un carcter (es decir, si el carcter del patrny el texto coinciden, se avanza tanto en el patrn como en el texto), las flechas verticalesrepresentan inserciones en el patrn (se avanza en el texto pero no en el patrn), lasflechas diagonales slidas representan reemplazos (se avanza en el texto y en el patrn)y las flechas diagonales punteadas representan eliminaciones en el patrn (se considerantransiciones nulas, por lo tanto se avanza en el patrn pero no en el texto). El ciclo en elestado inicial permite que una coincidencia ocurra en cualquier parte del texto El


8/18

computadora y actualizar todos stos con una sola operacin. Tomando ventaja delparalelismo de bits, el nmero de operaciones que un algoritmo desempea se puedereducir por un factor de w, donde wes el nmero de bits de una palabra de computadora.En las arquitecturas actuales wes igual a 32 64, el incremento de velocidad es muysignificante en la prctica.

Algunas notaciones que se utilizan para describir los algoritmos de paralelismo de bitsson las siguientes: se usa exponenciacin para expresar repeticiones de bits, por ejemplo,031 = 0001. Una secuencia de bits b1bl, se conoce como mscara de bits de longitud l,la cual se almacena dentro de la palabra de computadora de longitud w. Generalmentese utiliza la sintaxis del lenguaje C para las operaciones sobre los bits, es decir, | es una

operacin OR, & es una operacin AND, ^ es una operacin XOR, ~ complementatodos los bits, y ) mueve los bits a la izquierda (derecha) e ingresa ceros a partirde la derecha (izquierda), por ejemplo, blbl-1b2b1


9/18

coincidencias previas de stas. A continuacin se describen a detalle los algoritmos LZ78y LZW.

LZ78. Este mtodo mantiene un diccionario de cadenas encontradas anteriormente. Eldiccionario inicialmente est vaco y su tamao mximo depende de la cantidad dememoria disponible. El codificador genera bloques de dos campos. El primer campo esun apuntador al diccionario, el segundo es el cdigo de un smbolo. Cada bloquecorresponde a una cadena de smbolos de entrada, y cada cadena se aade aldiccionario despus de que el bloque se escribe en la cadena comprimida. El diccionariocontiene en la posicin cero la cadena vaca. Conforme entran los smbolos y secodifican, las cadenas se aaden al diccionario en las posiciones 1,2, y as

sucesivamente.

El proceso de codificacin es el siguiente: el primer smbolo se lee y se convierte enuna cadena de un solo smbolo. El codificador trata de encontrarla en el diccionario. Si elsmbolo se encuentra en el diccionario, se lee el siguiente smbolo y se concatena con elprimero para formar una cadena de dos smbolos, que el codificador trata de localizar enel diccionario. Tan pronto como esas cadenas se encuentran en el diccionario, se leenms smbolos y se concatenan a la cadena. En cierto momento la cadena no seencuentra en el diccionario, entonces el codificador la aade al diccionario y genera unbloque con la ltima coincidencia del diccionario en su primer campo, y el ltimo smbolode la cadena (el que ha provocado que la bsqueda falle) en el segundo campo.

A continuacin se muestra la codificacin obtenida por LZ78 para el texto abracadabra_.

Figura 7. Codificacin obtenida con el algoritmo de compresin LZ78 para el textoabracadabra.

LZW. Es una variante popular del LZ78. Este mtodo elimina el segundo campo delbloque LZ78. Un bloque LZW consiste en un apuntador al diccionario. Como resultado, unbloque codifica siempre una cadena de ms de un smbolo. El mtodo LZW inicializa eldiccionario con todos los smbolos del alfabeto. El caso ms comn es contar con


10/18

apuntador de diccionario que apunta a la cadena I, almacena la cadena Ix en la siguienteentrada del diccionario disponible, y por ltimo inicializa la cadena Ial smbolo x.

A continuacin se muestra la codificacin obtenida por LZW para el textoabracadabra_.

97(a), 98(b), 114(r), 97(a), 99(c), 97(a), 100(d), 256(ab), 258(ra)

Figura 8. Codificacin con el algoritmo de compresin LZW para el texto abracadabra.Slo se toman los nmeros, no las cadenas entre parntesis.

Tanto LZ78 cmo LZW logran la compresin si el apuntador toma menos espacio quela cadena reemplazada. Por lo tanto, estos mtodos tienen mejores resultados si elarchivo de texto en grande (mayor a 10 MB), puesto que hay ms probabilidad de que las

cadenas apuntadas sean de una longitud mayor.

3 Trabajo Relacionado

En este apartado se mencionan algunos trabajos que se han desarrollado en el ambientede bsqueda de patrones en texto comprimido. Se describen brevemente las solucionespropuestas as como sus principales caractersticas, ventajas y desventajas.

Para bsqueda de patrones en texto comprimido sobresalen dos esquemas. Elprimero aplica mtodos de compresin basados en reemplazar slo smbolos, tal como lacodificacin de Fuman [15]. Mediante este esquema se han realizado trabajos queofrecen una solucin eficiente [16] y [17], pero en general la razn de compresin no esbuena o su funcionalidad est limitada.


11/18

O(m2 + n). Un algoritmo para LZ77 se present en [19], y resuelve el mismo problema enun tiempo de O(m+ nlog2(u/n)).

Por otra parte, en [20] se present una extensin de [18] que resuelve el problema debsqueda multipatrn sobre texto comprimido con LZ78/LZW. Este algoritmo se basa enel algoritmo Aho-Corasick[21], y encuentra todas las coincidencias del patrn en untiempo y espacio de O(M2 +n), donde Mes la suma de las longitudes de los patrones.

Un esquema general para bsqueda de patrones (simples y extendidos) directamenteen texto comprimido se present en [22], especializndose para algunos formatos enparticular (LZ77, LZ78, etc.). Este esquema se basa en paralelismo de bits, con esta

tcnica se logra empaquetar muchos valores en los bits de una palabra de computadorade wbits y actualizar todos ellos en paralelo. Un trabajo similar se present en [23] paratexto comprimido con LZW. Un algoritmo basado en el mtodo de Boyer-Moore parabsqueda en texto comprimido con LZ78/LZW se present en [24], el cual actualmente esel ms rpido para longitudes moderadas del patrn.

El problema de bsqueda aproximada sobre texto comprimido fue tratado por primeravez en [6]. Recientemente, este problema ha sido resuelto para los formatos LZW y LZ78en un tiempo de O(mkn+ R) (donde Res el nmero de coincidencias encontradas) en elpeor de los casos y O(k2n+R) en el caso promedio, utilizando tcnicas de programacindinmica [7] y tcnicas de paralelismo de bits [8]. Sin embargo, ambas soluciones sonmuy lentas. La primera solucin prctica a este problema se presenta en [25]. Estasolucin trabaja para texto comprimido con LZ78/LZW y se basa en dividir el patrn enk+1 subpatrones y realizar una bsqueda multipatrn de stos, seguida de unadescompresin local y una verificacin directa en las reas de texto candidatas. En estetrabajo se presenta una mejora al trabajo realizado en [25], en lugar de realizar unadescompresin y luego buscar el patrn en el rea descomprimida, se simulan dos

autmatas utilizando la tcnica de paralelismo de bits que reconozcan la coincidencia conkerrores a partir del subpatrn encontrado en la fase anterior, esto hace posible que laverificacin sea ms rpida y la bsqueda se acelere.

4 Solucin propuesta: Bsqueda aproximada en texto comprimido

La mayora de los algoritmos para bsqueda de patrones sobre texto comprimido

toman las ideas de los algoritmos clsicos de bsqueda para texto sin comprimir y lasadaptan para trabajar con secuencias de bloques de Ziv-Lempel en vez de una secuenciade caracteres. Las soluciones para bsqueda aproximada de patrones no son laexcepcin. Existen 4 diferentes esquemas para bsqueda aproximada de patrones [1],dos de las cuales son de inters en este trabajo: (1) Paralelismo de bits, y (2) Filtracin.En este trabajo se adapta una tcnica de filtracin para trabajar sobre texto comprimido.


12/18

notarlo puesto que cada error puede alterar en el peor caso un subpatrn. La bsquedacontina con la ejecucin de una bsqueda multipatrn de los subpatrones resultantes, lacual se explica en la siguiente seccin. Cada que se encuentra un subpatrn, se verificamediante dos autmatas la coincidencia del patrn completo permitiendo k diferencias,uno verifica hacia la izquierda y otro hacia la derecha del subpatrn encontrado, estosautmatas se simulan mediante paralelismo de bits. A continuacin se explica a detalle laetapa de bsqueda multipatrn y la etapa de verificacin.

4.2 Bsqueda multipatrn Boyer-Moore.

El algoritmo multipatrn que se ejecuta en esta fase, es una adaptacin del algoritmo

Boyer-Moore (BM) monopatrn [24]. El algoritmo BM consiste en alinear el patrn en unaventana de texto y comparar de derecha a izquierda los caracteres de la ventana con loscorrespondientes al patrn. Si ocurre una desigualdad se calcula un desplazamientoseguro el cual permitir desplazar la ventana hacia delante del texto sin riesgo de omitiralguna coincidencia. Si se alcanza el inicio de la ventana y no ocurre ningunadesigualdad, entonces se reporta una coincidencia y la ventana se desplaza.

Se han presentado algunos trabajos para adaptar esta idea a texto comprimido conZiv-Lempel [24]. La figura 9 representa una ventana hipottica de un texto comprimidocon LZ78 o con LZW. En el caso de LZ78, El cuadro oscuro representa el carcterexplcito c del bloque b = (s,c), mientras que las lneas que unen a los cuadrosrepresentan los caracteres implcitos, es decir el texto que se obtiene de los bloquesprevios referenciados(s, luego el bloque referenciado por s, y as sucesivamente). En elcaso de LZW la caja representa el primer carcter del bloque siguiente. Por cada bloqueledo se almacena su ltimo carcter, su longitud, el bloque al que referencia y algn otrodato dependiente del algoritmo.

Figura 9. Ventana de un texto comprimido con LZ78 o LZW. Los cuadros oscurosrepresentan los caracteres explcitos al final de cada bloque (o al principio del bloque

siguiente en LZW) y las lneas que unen los cuadros representan los caracteres implcitosdel bloque.

El algoritmo de bsqueda monopatrn BM lee desde el archivo comprimido tantosbloques como sea necesario para completar la ventana. Aplicar BM puro es costosodebido a la necesidad de acceder a los caracteres dentro de los bloques. Un carcter a

di t i i d l lti t d bl it i i bl t l d d


13/18

La cual da el mximo desplazamiento seguro dado que en la posicin iel carcter enel texto es c.

Al encontrar el primer carcter explcito que permita un desplazamiento mayor quecero, se desplaza la ventana. Si no es as, se comienzan a considerar los caracteresimplcitos. La figura 10 muestra el orden en que se consideran los bloques.

Figura 10. Orden en que se evalan los bloques. Primero se leen los caracteres explcitosde derecha a izquierda, luego los implcitos de derecha a izquierda dejando al final elltimo bloque.

Si despus de considerar todos los bloques no se obtiene un desplazamiento mayorque cero, se reporta una coincidencia del patrn en la posicin de la ventana actual y laventana se desplaza una posicin hacia la derecha del texto.

Para la versin multipatrn, se generaliza la bsqueda de un solo patrn a labsqueda de varios patrones, es decir, en lugar de buscar un patrn P en el textocomprimido, se buscan r patrones P1 Pr simultneamente. Para conocer eldesplazamiento posible para cada carcter ledo de un bloque se redefine B de la

siguiente manera:

B(i,c) = min (min({i} U {i-j,1 ji ^ Pkj= c}), 1 kr) (3)

Es decir, dado que el carcter en la posicin i es c, se calcula el desplazamientomximo seguro para cada patrn y se toma el menor de ellos. Con esto se obtiene eldesplazamiento mximo seguro para todos los patrones.

Una vez que se encuentra una coincidencia de un subpatrn es necesario realizar unafase de verificacin para comprobar si el subpatrn encontrado corresponde a una partede la coincidencia del patrn buscado. En caso de no ser as, la ventana se desplaza ycontina la bsqueda de otro subpatrn.


14/18

Se inicia el reconocimiento con P1, pues resulta menos costoso en tiempo verificar losbloques hacia la izquierda dado que estos han sido desenrollados. Se inicia con el bloqueen donde comienza el subpatrn F, en la figura 11 el bloquejrepresenta el bloque dondeinicia el subpatrn, el cual est contenido dentro del bloque jj. A partir del bloque jseobtienen todos los caracteres explcitos de los bloques referenciados porjhasta encontrarun bloque de longitud menor o igual a 1, luego se obtienen todos los caracteresreferenciados por el bloquejj-1,jj-2 y as sucesivamente, alimentando el autmata con loscaracteres que se van obteniendo. El proceso se detiene cuando el autmata muere.

Figura 11. Orden en que se obtienen los caracteres para alimentar al autmata en elproceso de verificacin.

Si el nmero de errores encontrados en este proceso k > k, se detiene el proceso ycontinua la bsqueda de otro subpatrn. Si k kse reconfigura el autmata P2 para quepermita k = k k errores.

Para el reconocimiento de P2 se inicia con el bloque en donde finaliza F. En la figura11 este bloque esta representado por i, el cual est contenido dentro del bloque ii.Ahora, obtener los caracteres es ms difcil, pues hay que ir hacia atrs en la cadena dereferenciamiento a partir del bloque ii hasta encontrar el bloque i, almacenando en unarreglo los caracteres explcitos de los bloques que se van recorriendo. Una vez que seencontr el bloque i, se alimenta el autmata con los caracteres almacenados iniciandocon el ltimo carcter obtenido. Si los caracteres obtenidos no son suficientes para llegara un estado final del autmata, se lee un nuevo bloque ii= ii+1 y se procesa de igualmanera, es decir, se van almacenando los caracteres explcitos de los bloques a los quereferencia ii, esta vez mientras que la longitud del bloque referenciado sea mayor que 1.Al llegar a este bloque se alimenta el autmata con los caracteres almacenados iniciando

con el ltimo carcter obtenido. El proceso continua hasta que el autmata muere.

Si al finalizar la verificacin el nmero total de errores encontrados es menor o igual ak, se reporta una coincidencia del patrn completo.


15/18

270 revistas mdicas coleccionados en un periodo de 5 aos (1987-1991). Los patronesse escogieron de forma aleatoria y se experiment con longitudes del patrn de 10 hasta30 caracteres, y con kigual a 0, 1, 2 y 3, ya que son los casos ms comunes.

El algoritmo de bsqueda aproximada se implement en un software llamado alzgrep(lzgrep extendido con bsqueda aproximada), los resultados que se obtuvieron secompararon con agrep y nrgrep, que son en la actualidad las mejores herramientas debsqueda que permiten realizar bsqueda aproximada pero que deben descomprimir elarchivo antes de efectuar la bsqueda. Por esta razn, a los tiempos de bsqueda quelograban se les sum el tiempo necesario para llevar a cabo la descompresin delarchivo.

La figura 12 muestra los tiempos obtenidos en la bsqueda de patrones de longitudmenor a 15 y entre 15 y 30. Como se puede observar, el algoritmo propuesto en estetrabajo es hasta 3 veces ms rpido que el mejor software que primero descomprime elarchivo y realiza la bsqueda despus. Los patrones con los que se experiment y losdatos obtenidos se muestran en el anexo A.

Figura 12. Tiempo de bsqueda en segundos para los diferentes algoritmos sobre unarchivo de texto, para m


16/18

Figura 13. Tiempo de bsqueda en segundos para los diferentes algoritmos sobre unarchivo de texto, para k= 0, 1, 2 y 3 y m= 10, 15, 20, 25 y 30.

6 Conclusiones

En este trabajo se ha presentado una solucin al problema de bsqueda aproximadadirectamente sobre texto comprimido con LZ78 y LZW. Con los resultados que seobtuvieron de los experimentos realizados, se puede concluir que con el algoritmopropuesto se puede efectuar la bsqueda aproximada de patrones simples hasta 3 vecesms rpido que con la mejor herramienta disponible para bsqueda aproximada, la cualprimero tiene que realizar una descompresin del archivo y luego realizar la bsqueda.Para llevar a cabo los experimentos, se implement una herramienta la cual de denominalzgrep, y que posteriormente estar pblicamente disponible. Contar con unaherramienta de este tipo es muy importante ya que adems de la ventaja que se obtiene

en el tiempo necesario para ejecutar la bsqueda, se ahorra espacio para almacenar lacoleccin, y tiempo de transmisin en la red.

Referencias


17/18

6. A. Amir and G. Benson. Efficient two-dimensional compressed matching. In Proc. DCC92,pages 279-288, 1992.

7. J. Krkkinen, G. Navarro, and E. Ukkonen. Approximate string matching Over Ziv-Lempel

compressed text. In Proc. CPM2000, LNCS 1848, pages 195-209, 2000.8. T. Matsumoto, T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Bit-parallel approach to

approximate string matching in compressed texts. In Proc. SPIRE2000, pages 221-228.IEEE CS Press, 2000.

9. R. S. Boyer and J. S. Moore. A fast string searching algorithm. Communications of theACM, 20(10):772, 1977.

10. S. Wu and U. Manber. Agrep- a fast approximate pattern-matching tool. In Proc. USENIXTechnical Conference, pages 153-162, 1992.

11. G. Navarro, NR-grep: a fast and flexible pattern-matching tool. Software-Practice &

Experience, v.31 n.13, p.1265-1312, November 10, 2001.12. D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAMS Journalon Computing, 6(1):323-350, 1977.

13. S. Wu and U. Manber. Fast text searching allowing errors. Communications of the ACM,35(10):83-91, 1992.

14. R. A. Baeza-Yates and G. H. Gonnet. A new approach to text searching. In N. J. Belkin andC. J. Van Rijsbergen, Editors, 12th, pages 168-175, 1989.

15. D. Huffman. A method for the construction of minimum-redundancy codes. Proc. Of The I.R. E., 40(9):1090-1101, 1952.

16. U. Manber. A text compression scheme that allows fast searching directly in the

compressed file. ACM TOIS, 15(2):124-136, 1997.17. E. Moura, G. Navarro, N. Ziviani, and R. Baeza-Yates. Fast and flexible word searching on

compressed text. ACM TOIS, 18(2):113-139, 2000.18. A. Amir, G. Benson, and M. Farach. Let Sleeping Files Lie: Pattern Matching In Z-

compressed Files. J. Of Comp. And Sys. Sciences, 52(2):299-307, 1996.19. M. Farach and M. Thorup. String matching in Lempel-Ziv compressed strings. Algoritmica,

20:388-404, 1998.20. T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa. Multiple pattern matching

in LZW compressed text. In Proc. DCC98, pages 103-112, 1998.

21. A. Aho and M. Corasick. Efficient string matching: an aid to bibliographic search. Comm. Ofthe ACM, 18(6):333-340, June 1975.22. G. Navarro and Raffinot. A general practical approach to pattern matching over Ziv-Lempel

compressed text. In Proc. CPM99, LNCS 1645, pages 14-36, 1999.23. T. Kida, M. Takeda, A. Shinohara, M. Miyasaki, and S. Arikawa. Shift-and approach to

pattern matching in LZW compressed text. In Proc. CPM99, LNCS 1645, pages 1-13,1999.

24. G. Navarro and J. Tarhio. Boyer-Moore string matching over Ziv-Lempel compressed text.In Proc. CPM2000, LNCS, 2000.

25. G. Navarro, T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Faster approximate stringmatching over compressed text. In Proc. 11th IEEE Data Compression Conference(DCC01), pages 459-468, 2001.
https://portal.acm.org/poplogin.cfm?dl=ACM&coll=portal&comp_id=COMPONENT030&want_href=citation%2Ecfm%3Fid%3D511284&CFID=24165261&CFTOKEN=38192004https://portal.acm.org/poplogin.cfm?dl=ACM&coll=portal&comp_id=COMPONENT030&want_href=citation%2Ecfm%3Fid%3D511284&CFID=24165261&CFTOKEN=38192004https://portal.acm.org/poplogin.cfm?dl=ACM&coll=portal&comp_id=COMPONENT030&want_href=citation%2Ecfm%3Fid%3D511284&CFID=24165261&CFTOKEN=38192004


18/18

Anexo A.

En la siguiente tabla se muestran los patrones con los cuales se llev a cabo los experimentos, as como la longitud de cada uno deellos y el tiempo necesario para encontrar todas las coincidencias del patrn en el texto con cada uno de los algoritmos.

m Patrn a buscar agrep nrgrep alzgrep

k = 0 2 3 0 2 3 0 2 31 1 1

10 Associated 21.16 21.34 21.6 23.3 21.2 22.08 29.75 24.05 7.99 13.32 19.82 27.19

10 Hemorrhage 21.14 21.29 21.48 22.89 21.14 21.41 24.63 24.18 7.82 13.2 19.85 26.8612 Pneumathorax 21.12 21.21 21.28 21.67 21.18 21.34 21.89 26.18 7.53 11.73 16.92 21.06

13 Resuscitation 21.13 21.46 21.8 22.21 21.14 21.46 25.07 25.62 7.31 12.23 17.84 23.07

13 Ethchlorvynol 21.11 21.26 21.25 21.86 21.11 21.26 21.47 24.92 7.08 11.19 16.23 20.75

13 Approximately 21.15 21.22 21.46 21.79 21.16 21.29 21.77 25.2 7.3 11.83 16.58 20.85

15 Cerebral anoxia 21.13 21.24 21.34 22.25 21.12 21.27 21.83 25.62 6.9 11.02 15.3 22.85

15 Cerebral artery 21.14 21.21 21.33 22.12 21.12 21.3 21.82 22.58 6.98 10.69 14.76 22.6

19Electrocardiography

21.1 21.18 21.32 21.64 21.1 21.24 21.67 21.73 6.34 9.19 12.53 17.8820 Immunohistochemistry 21.1 21.18 21.3 21.57 21.08 21.26 21.39 21.72 6.43 8.6 12.45 15.03

20 Globotriosylceramide 21.11 21.18 21.44 21.55 21.09 21.29 21.3 21.52 6.49 8.73 12.53 14.77

21 Possible appendicitis 21.01 21.18 21.35 21.55 21.09 21.21 21.36 21.87 6.32 8.86 12 16.34

23 Electroencephalographic 21.1 21.16 21.3 21.51 21.09 21.18 21.39 21.55 6.06 8.63 11.19 15.22

25 Immunodeficiency syndrome 21.09 21.27 21.43 21.62 21.08 21.17 21.36 21.62 5.99 7.92 10.33 13.76

26 Magnetic resonante imaging 21.1 21.28 21.47 21.67 21.09 21.37 21.25 21.55 6.06 8.29 11.34 13.78

27 Macroscopic and microscopic 21.08 21.24 21.37 21.54 21.06 21.15 21.25 21.34 5.9 7.77 10.13 13.56

28 Oromandibular reconstruction 21.09 21.24 21.37 21.54 21.07 21.31 21.29 21.41 6.07 7.84 10.52 12.6428 Electrohydraulic ventricular 21.1 21.22 21.33 21.49 21.07 21.32 21.29 21.53 6.1 7.65 10.12 12.82

29 Possible mode of transmissin 21.1 21.23 21.38 21.52 21.07 21.34 21.26 21.42 6.09 8.12 10.37 13.31

30 Abdominal and gastrointestinal 21.09 21.25 21.36 21.49 21.08 21.27 21.25 21.52 6.01 7.86 9.88 13.44

Tiempo de la bsqueda en segundos

17

busqueda+proyecto+texto

Documents