Loading article…
Sequitur（またはNevill-Manning-Wittenアルゴリズム）は、 1997年にCraig Nevill-ManningとIan H. Wittenによって開発された再帰アルゴリズムです[1] 。これは、離散シンボルのシーケンスから階層構造（文脈自由文法）を推論します。このアルゴリズムは線形空間と時間で動作します。データ圧縮ソフトウェアアプリケーションで使用できます。 [2]
制約
sequiturアルゴリズムは、与えられたシーケンス内の繰り返しフレーズを新しいルールに置き換えることで文法を構築し、シーケンスの簡潔な表現を生成します。たとえば、シーケンスが
- S→abcab、
アルゴリズムは
- S→AcA、A→ab。
入力シーケンスをスキャンする際、アルゴリズムは、対字句の一意性と規則の有用性という2 つの制約に従って文法を効率的に生成します。
ダイグラムの一意性
シーケンスから新しいシンボルがスキャンされるたびに、最後にスキャンされたシンボルが追加され、新しい対字が形成されます。この対字が以前に形成されている場合は、対字の両方の出現を置き換える新しい規則が作成されます。したがって、文法で対字が複数回出現しないことが保証されます。たとえば、シーケンスS→abaabaでは、最初の 4 つのシンボルがすでにスキャンされている場合、形成される対字はab、ba、aaです。5 番目のシンボルが読み取られると、すでに存在する新しい対字「ab」が形成されます。したがって、「ab」の両方のインスタンスは、S内の新しい規則 (たとえば、A) に置き換えられます。これで、文法はS→AaAa、A→abになり、文法に重複する対字が存在しなくなるまでプロセスが続行されます。
ルールユーティリティ
この制約は、すべての規則が文法のすべての生成の右側で複数回使用されることを保証します。つまり、規則が 1 回だけ出現する場合は、その規則を文法から削除し、その出現をその規則の作成元のシンボルに置き換える必要があります。たとえば、上記の例では、最後のシンボルをスキャンして 'Aa' の二字形一意性を適用すると、文法はS→BB、A→ab、B→Aaを生成します。ここで、規則 'A' は文法のB→Aaで 1 回だけ出現します。したがって、A は削除され、最終的に文法は次のようになります。
- S→BB、B→aba。
この制約は、文法のルールの数を減らすのに役立ちます。
方法の概要
このアルゴリズムは、終端記号のシーケンスをスキャンし、読み取ったすべての記号ペアのリストを作成することで機能します。ペアの 2 回目の出現が見つかるたびに、シーケンス内の 2 つの出現が、考案された非終端記号に置き換えられ、記号ペアのリストが新しいシーケンスと一致するように調整され、スキャンが続行されます。ペアの非終端記号が、作成されたばかりの記号の定義でのみ使用されている場合、使用されている記号はその定義に置き換えられ、定義された非終端記号からその記号が削除されます。スキャンが完了すると、変換されたシーケンスは、元のシーケンスの文法の最上位ルールとして解釈できます。それに含まれる非終端記号のルール定義は、記号ペアのリストにあります。これらのルール定義自体には、追加の非終端記号が含まれている可能性があり、そのルール定義は、記号ペアのリストの他の場所から読み取ることもできます。[3]
参照
参考文献
- ^ Nevill-Manning, CG ; Witten, IH (1997). 「シーケンス内の階層構造の識別: 線形時間アルゴリズム」. arXiv : cs/9709102 . Bibcode :1997cs.......9102N.
{{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です - ^ Nevill-Manning, CG ; Witten , IH (1997). 「圧縮のための線形時間増分階層推論」。Proceedings DCC '97。データ圧縮会議。pp . 3–11。CiteSeerX 10.1.1.30.2305。doi :10.1109/DCC.1997.581951。ISBN 978-0-8186-7761-8. S2CID 14324301。
- ^ GrammarViz 2.0 – Sequitur と Java での並列 Sequitur 実装、Sequitur ベースの時系列パターン検出
外部リンク
- sequitur.info – C++、Java、その他の言語での Sequitur アルゴリズムの実装リファレンス