Un oráculo de factores es un autómata de estados finitos que puede buscar de manera eficiente factores ( subcadenas ) en un cuerpo de texto. Las técnicas más antiguas, como los árboles de sufijos , eran eficientes en términos de tiempo pero requerían cantidades significativas de memoria. Los oráculos de factores, por el contrario, se pueden construir en tiempo y espacio lineales de manera incremental. [1]
Las técnicas más antiguas para hacer coincidir cadenas incluyen: matrices de sufijos , árboles de sufijos , autómatas de sufijos o gráficos de palabras acíclicos dirigidos y autómatas factoriales (Allauzen, Crochemore, Raffinot, 1999). En 1999, Allauzen, Crochemore y Raffinot presentaron el algoritmo de oráculo factorial como una mejora eficiente en el uso de la memoria con respecto a estas técnicas más antiguas para la comparación y compresión de cadenas. A partir de mediados de la década de 2000, los oráculos factoriales también han encontrado aplicación en la música por computadora. [2]
El Laboratorio de Audición Computacional proporciona una implementación de Matlab del algoritmo factorial.