Coincidencia de patrones comprimidos

En informática , la búsqueda de patrones comprimidos (abreviada como CPM ) es el proceso de búsqueda de patrones en datos comprimidos con poca o ninguna descompresión. La búsqueda en una cadena comprimida es más rápida que la búsqueda en una cadena sin comprimir y requiere menos espacio.

Si el archivo comprimido utiliza una codificación de ancho variable, podría presentar un problema: por ejemplo, sea "100" la palabra clave para "a" y "110100" la palabra clave para "b" . Si buscamos una ocurrencia de "a" en el texto, podríamos obtener como resultado una ocurrencia que se encuentre dentro de la palabra clave de "b" : a esto lo llamamos coincidencia falsa . Por lo tanto, debemos verificar si la ocurrencia detectada está efectivamente alineada con el límite de una palabra clave. Sin embargo, siempre podríamos decodificar todo el texto y luego aplicar un algoritmo clásico de coincidencia de cadenas , pero esto generalmente requiere más espacio y tiempo y a menudo no es posible, por ejemplo, si el archivo comprimido está alojado en línea. Este problema de verificar si la coincidencia devuelta por el algoritmo de coincidencia de patrones comprimidos es verdadera o falsa, junto con la imposibilidad de decodificar todo el texto, se denomina problema de coincidencia comprimida . ^{[ 1 ]}

Existen muchas estrategias para encontrar los límites de las palabras clave y evitar la descompresión completa del texto, por ejemplo:

• Lista de los índices del primer bit de cada palabra clave, donde podemos aplicar una búsqueda binaria;
• Lista de los índices del primer bit de cada palabra clave con codificación diferencial, para que podamos ocupar menos espacio dentro del archivo;
• Máscara de bits , donde el bit 1 marca el bit inicial de cada palabra clave;
• Subdivisión en bloques, para una descompresión parcial y dirigida.

Se introdujeron algoritmos que proporcionan un tiempo de ejecución que crece logarítmicamente con el aumento de la longitud de la cadena y del patrón. ^{[ 2 ]}

• Shmuel T. Klein y Dana Shapira, COINCIDENCIA DE PATRONES EN TEXTOS CODIFICADOS CON HUFFMAN (2003)
• Marek Karpinski, Wojciech Rytter y Ayumi Shinohara. UN ALGORITMO EFICIENTE DE BÚSQUEDA DE PATRONES PARA CADENAS CON DESCRIPCIONES CORTAS. Nordic Journal of Computing 4(2): pp.172-168 (1997).

• "Coincidencia de patrones casi óptima totalmente comprimida con LZW". 1999: 316–325 . CiteSeerX 10.1.1.44.5521 . {{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
• Un algoritmo de coincidencia de patrones comprimidos basado en diccionario (PDF) , archivado del original (PDF) el 13 de marzo de 2003.
• "Un marco unificador para la coincidencia de patrones comprimidos". 1999: 89– 96. CiteSeerX 10.1.1.50.1745 . {{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
• "Acelerando la búsqueda de patrones de cadenas mediante compresión de texto: el amanecer de una nueva era" (PDF) . Archivado del original (PDF) el 8 de agosto de 2007. Consultado el 22 de marzo de 2009 .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
• "Enfoque Shift-and para la coincidencia de patrones en texto comprimido LZW". 1999: 1– 13. CiteSeerX 10.1.1.15.4609 . {{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
• "Algoritmo LZW" (PDF) .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )