Фактор оракула

Факторный оракул — это конечный автомат , который может эффективно искать факторы ( подстроки ) в тексте. Старые методы, такие как суффиксные деревья , были экономичными по времени, но требовали значительных объемов памяти. Факторные оракулы, напротив, могут быть построены в линейном времени и пространстве постепенно. ^{[ 1 ]}

Обзор

К более старым методам сопоставления строк относятся: суффиксные массивы , суффиксные деревья , суффиксные автоматы или ориентированные ациклические графы слов , а также факторные автоматы (Allauzen, Crochemore, Raffinot, 1999). В 1999 году Аллаузен, Крошмор и Раффино представили алгоритм факторного оракула как эффективное улучшение памяти по сравнению с более старыми методами сопоставления и сжатия строк. Начиная с середины 2000-х годов фактор-оракулы нашли применение и в компьютерной музыке. ^{[ 2 ]}

Реализации

Лаборатория компьютерного прослушивания предоставляет реализацию Matlab алгоритма факторного оракула.

См. также

Ссылки

^ Аллаузен К., Крошмор М., Раффино М., Факторный оракул: новая структура для сопоставления с образцом ; Материалы СОФСЭМ'99; Теория и практика информатики.
^ Ассаяг Г., Дубнов С., Использование факторных оракулов для машинной импровизации. Мягкие вычисления — сочетание основ, методологий и приложений. 01 сентября 2004 г. Шпрингер Берлин / Гейдельберг

[1] Аллаузен К., Крошмор М., Раффино М., Факторный оракул: новая структура для сопоставления с образцом ; Материалы СОФСЭМ'99; Теория и практика информатики.

[2] Ассаяг Г., Дубнов С., Использование факторных оракулов для машинной импровизации. Мягкие вычисления — сочетание основ, методологий и приложений. 01 сентября 2004 г. Шпрингер Берлин / Гейдельберг

[ 1 ]

[ 2 ]