Фактор оракул - Factor oracle
А фактор оракула это конечный автомат который может эффективно искать факторы (подстроки ) в основном тексте. Старые методы, такие как суффиксные деревья, были эффективными по времени, но требовали значительного объема памяти. Факторные оракулы, напротив, могут быть построены в линейном времени и пространстве поэтапно.[1]
Обзор
Старые методы сопоставления строк включают: массивы суффиксов, суффиксные деревья, суффиксные автоматы или же ориентированные ациклические графы слов, и факторные автоматы (Allauzen, Crochemore, Raffinot, 1999). В 1999 году Аллаузен, Крочемор и Раффино представили алгоритм факторного оракула как эффективное улучшение памяти по сравнению с этими старыми методами сопоставления и сжатия строк. Начиная с середины 2000-х годов, оракулы факторов нашли применение и в компьютерной музыке.[2]
Реализации
В Лаборатория компьютерного прослушивания предоставляет реализацию Matlab алгоритма факторного оракула.
Смотрите также
Рекомендации
- ^ Аллаузен К., Крочмор М., Раффино М., Factor oracle: новая структура для сопоставления с образцом; Труды СОФСЕМ’99; Теория и практика информатики.
- ^ Пробаяг Г., Дубнов С., Использование факторных оракулов для машинной импровизации. Мягкие вычисления - сочетание основ, методологий и приложений. 2004-09-01. Springer Berlin / Heidelberg