ファクターオラクル

ファクターオラクルとは、テキスト本文内のファクター（部分文字列）を効率的に検索できる有限状態オートマトンです。サフィックスツリーなどの古い手法は時間効率は良いのですが、大量のメモリを必要とします。対照的に、ファクターオラクルは線形時間と空間で増分的に構築できます。^[1]

概要

文字列をマッチングする古い技術には、サフィックス配列、サフィックスツリー、サフィックスオートマトンまたは有向非巡回ワードグラフ、ファクターオートマトンなどがあります (Allauzen、Crochemore、Raffinot、1999)。1999 年に、Allauzen、Crochemore、および Raffinot は、文字列のマッチングと圧縮のためのこれらの古い技術をメモリ効率よく改良したファクターオラクルアルゴリズムを発表しました。2000 年代半ばから、ファクターオラクルはコンピューター音楽にも応用されています。^[2]

実装

Computer Audition Laboratory は、factor oracle アルゴリズムの Matlab 実装を提供します。

参照

参考文献

^ Allauzen C.、Crochemore M.、Raffinot M.、「Factor oracle: パターンマッチングの新しい構造」、SOFSEM'99 の議事録、情報科学の理論と実践。
^ Assayag G.、Dubnov S.、「ファクターオラクルを使用したマシンの即興化」。 ソフトコンピューティング - 基礎、方法論、アプリケーションの融合。2004-09-01。Springer Berlin / Heidelberg

[1] Allauzen C.、Crochemore M.、Raffinot M.、「Factor oracle: パターンマッチングの新しい構造」、SOFSEM'99 の議事録、情報科学の理論と実践。

[2] Assayag G.、Dubnov S.、「ファクターオラクルを使用したマシンの即興化」。 ソフトコンピューティング - 基礎、方法論、アプリケーションの融合。2004-09-01。Springer Berlin / Heidelberg