Factor oracle

A '''factor oracle''' is a finite-state automaton that can efficiently search for factors (substrings) in a body of text. Older techniques, such as suffix trees, were time-efficient but required significant amounts of memory. Factor oracles, by contrast, can be constructed in linear time and space in an incremental fashion.<ref>Allauzen C., Crochemore M., Raffinot M., ''[http://www.lsi.upc.edu/~marias/teaching/bom.pdf Factor oracle: a new structure for pattern matching] {{Webarchive|url=https://web.archive.org/web/20120415142426/http://www.lsi.upc.edu/~marias/teaching/bom.pdf |date=2012-04-15 }}; Proceedings of SOFSEM’99; Theory and Practice of Informatics.''</ref>

== Overview ==

Older techniques for matching strings include: suffix arrays, suffix trees, suffix automata or directed acyclic word graphs, and factor automata (Allauzen, Crochemore, Raffinot, 1999). In 1999, Allauzen, Crochemore, and Raffinot, presented the factor oracle algorithm as a memory efficient improvement upon these older techniques for string matching and compression. Starting in the mid-2000s, factor oracles have found application in computer music, as well.<ref>Assayag G., Dubnov S., ''Using Factor Oracles for Machine Improvisation.'' Soft Computing - A Fusion of Foundations, Methodologies and Applications. 2004-09-01. Springer Berlin / Heidelberg</ref>

== Implementations == The [https://web.archive.org/web/20111129201351/http://cosmal.ucsd.edu/cal/projects/CATbox/catboxdownload.htm Computer Audition Laboratory] provides a Matlab implementation of the factor oracle algorithm.

==References== <references />

Category:Automata (computation) Category:Substring indices