En informática , la coincidencia de patrones comprimidos (abreviada como CPM ) es el proceso de búsqueda de patrones en datos comprimidos con poca o ninguna descompresión. Buscar en una cadena comprimida es más rápido que buscar en una cadena sin comprimir y requiere menos espacio.
Si el archivo comprimido utiliza una codificación de ancho variable, podría haber un problema: por ejemplo, sea "100" la palabra clave para a y "110100" sea la palabra clave para b . Si buscamos una aparición de a en el texto, podríamos obtener como resultado también una aparición que esté dentro de la palabra clave de b : a este evento lo llamamos coincidencia falsa . Por lo tanto, tenemos que verificar si la ocurrencia detectada está efectivamente alineada en el límite de una palabra de código. Sin embargo, siempre podemos decodificar el texto completo y luego aplicar un algoritmo clásico de coincidencia de cadenas , pero esto normalmente 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 que la coincidencia devuelta por el algoritmo de coincidencia de patrones comprimidos sea verdadera o falsa junto con la imposibilidad de decodificar un texto completo se denomina problema de coincidencia comprimida . [1]
Existen muchas estrategias para encontrar los límites de las palabras en clave y evitar la descompresión completa del texto, por ejemplo:
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]
{{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda )