Paralel Failure-Less Aho-Corasick
El algoritmo "Paralel Failure-less Aho-Corasick" (PFAC) es una versión paralela del algoritmo secuencial Aho-Corasick, esta versión permite aprovechar unidades de procesamiento gráfico de propósito general (GPGPU, por sus siglas en ingles) para paralelizar las operaciones realizadas, evitando así el uso de los "failure links", usados para manejar los casos en los que no hay una coincidencia entre el patrón y el carácter actual.
Para entender como funciona este algoritmo es necesario conocer su versión base, Aho-Corasick. Esta versión usa 3 funciones, la función goto, usada para verificar la coincidencia del carácter actual con el patrón evaluado en curso, la función failure, usada para encontrar el siguiente carácter dentro de la maquina luego de recibir un fallo en la función goto, y la función output, que marca los estados que representan la terminación de cada patrón.
El algoritmo Aho-Corasick consiste en construir una maquina de estados finitos creada usando los patrones que se quieren buscar en el texto. Para ello se parte del estado inicial y se crean conexiones a los siguientes estados, cada conexión representa la primera letra de cada patrón y a partir de cada nuevo estado generado se continua creando conexiones que representan las siguientes letras de cada patrón, esto se realiza hasta terminar con la construcción de todos los patrones, la sucesión de conexiones desde el estado inicial hasta un estado cualquiera conforma un prefijo de un patrón dado. Esta maquina generada es usada para obtener el resultado de la función goto.
Luego de construida la maquina de estados se calculan los failure-links para cada uno de los estados del grafo goto, estos enlaces son usados para determinar el siguiente estado en caso de que la función goto falle. Para determinar hacia que estado apuntará el enlace se verifica si algún sufijo del camino actual en la maquina coincide con algún camino que inicia desde el estado inicial, en tal caso, el failure-link apuntara hacia el estado al que conduce el camino coincidente.
A continuación se muestra un ejemplo de la maquina construida para los patrones CTG, CTGA, CTGT, ACGT, TGACCT, considerando que el alfabeto son las bases del ADN:
A partir de esta maquina se crean los failure-links para cada uno de los estados, finalmente la maquina quedaría de la siguiente manera:
Finalmente, para realizar la búsqueda de los patrones en el texto se recorre el texto y se utiliza el grafo con los failure-links generados para avanzar desde el estado inicial y verificar si se completa un patrón, además, se utilizan los failure-links en caso de fallo de la función goto, el algoritmo termina cuando se recorre todo el texto.
Algoritmo Paralel Failure-less Aho-Corasick
Ya habiendo entendido como funciona el algoritmo Aho-Corasick, ahora si podemos explicar las modificaciones que aplica la versión paralela de este. El funcionamiento base de Paralel Failure-less Aho-Corasick es idéntico a su versión secuencial, sin embargo esta nueva versión se deshace de los failure-links ya que no los usa para hacer backtracking hacia el siguiente punto de inicio, si no que utiliza hilos de GPGPUs para ejecutar paralelamente para cada carácter del texto una maquina de estado finito. El problema con esta solución es que normalmente no puede detectar subpatrones de los patrones más largos, a continuación se muestra una imagen que muestra la ejecución paralela de PFAC para los patrones dados y el texto T="GCATGACCTGT":
Ejemplo
La ejecución del algoritmo PFAC para el texto y los patrones mencionados sería la siguiente:
- Ejecución maquina desde carácter T[1] = 'G':
- No hay camino disponible así que finaliza el hilo.
- Ejecución maquina desde carácter T[2] = 'C':
- Se dirige al estado '6' mediante la arista 'C'.
- No hay camino disponible, finaliza el hilo.
- Ejecución maquina desde carácter T[3] = 'A':
- Se dirige al estado '2' mediante la arista 'C'.
- No hay camino disponible, finaliza el hilo.
- Ejecución maquina desde carácter T[4] = 'T':
- Se dirige al estado '12' mediante la arista 'T'.
- Se dirige al estado '13' mediante la arista 'G'.
- Se dirige al estado '14' mediante la arista 'A'.
- Se dirige al estado '15' mediante la arista 'C'.
- Se dirige al estado '16' mediante la arista 'C'.
- Se dirige al estado '11' mediante la arista 'T'.
- Se identifica el patrón 'TGACCT'.
- No hay camino disponible, finaliza el hilo.
- Ejecución maquina desde carácter T[5] = 'G':
- No hay camino disponible, finaliza el hilo.
- Ejecución maquina desde carácter T[6] = 'A':
- Se dirige al estado '2' mediante la arista 'A'.
- Se dirige al estado '3' mediante la arista 'C'.
- No hay camino disponible, finaliza el hilo.
- Ejecución maquina desde carácter T[7] = 'C':
- Se dirige al estado '6' mediante la arista 'C'.
- No hay camino disponible, finaliza el hilo.
- Ejecución maquina desde carácter T[8] = 'C':
- Se dirige al estado '6' mediante la arista 'C'.
- Se dirige al estado '7' mediante la arista 'T'.
- Se dirige al estado '8' mediante la arista 'G'.
- Se identifica el patrón 'CTG'.
- Se dirige al estado '10' mediante la arista 'T'.
- Se identifica el patrón 'CTGT'.
- No hay camino disponible, finaliza el hilo.
- Ejecución maquina desde carácter T[9] = 'T':
- Se dirige al estado '12' mediante la arista 'T'.
- Se dirige al estado '13' mediante la arista 'G'.
- No hay camino disponible, finaliza el hilo.
- Ejecución maquina desde carácter T[10] = 'G':
- No hay camino disponible. Finaliza el hilo.
- Ejecución maquina desde carácter T[11] = 'T':
- Se dirige al estado '12' mediante la arista 'T'.
- No hay más caracteres disponibles, finaliza el hilo.
- Se finaliza el algoritmo.
Implementación
La implementación de este algoritmo requiere conocimiento sobre paralelización mediante GPUs, la librería en la que se encuentra disponible se puede encontrar en las referencias.