oráculo de factores

Un oráculo de factores es un autómata de estados finitos que puede buscar eficientemente factores ( subcadenas ) en un texto. Las técnicas más antiguas, como los árboles de sufijos , eran eficientes en 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 forma incremental. ^{[ 1 ]}

Las técnicas más antiguas para la comparación de cadenas incluyen: arreglos de sufijos , árboles de sufijos , autómatas de sufijos o grafos de palabras acíclicos dirigidos y autómatas de factores (Allauzen, Crochemore, Raffinot, 1999). En 1999, Allauzen, Crochemore y Raffinot presentaron el algoritmo de oráculo de factores como una mejora eficiente en memoria de 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 de factores también han encontrado aplicación en la música por computadora. ^{[ 2 ]}

El Laboratorio de Audición Computarizada proporciona una implementación en Matlab del algoritmo del oráculo de factores.

• Matriz de sufijos
• Árbol de sufijos generalizado