決定性非巡回有限状態オートマトン

文字列「tap」、「taps」、「top」、「tops」はトライ(左) と DAFSA (右) に格納されています。EOWはEnd-of-word (単語の終わり) を表します。

コンピュータサイエンスにおいて、決定性非巡回有限状態オートマトン（DAFSA）^{[ 1 ]} は、文字列の集合を表すデータ構造であり、与えられた文字列がその集合に属するかどうかをその長さに比例した時間でテストするクエリ操作を可能にする。このようなオートマトンを構築し、維持するためのアルゴリズムが存在する[ 1 ] 。DAFSA^{は、有向非巡回ワードグラフ（DAWG） [ 2 ]}と呼ばれるデータ構造の再発見であるが、同じ名前はサフィックスオートマトンに関連する別のデータ構造に既に与えられていた^{[ 3 ]}。

DAFSAは、有向非巡回グラフの形をとる有限状態認識器の特殊なケースであり、単一のソース頂点（入ってくる辺を持たない頂点）を持ち、グラフの各辺は文字または記号でラベル付けされ、各頂点は各文字または記号に対して最大で1つの出ていく辺を持つ。DAFSAによって表現される文字列は、ソース頂点から任意のシンク頂点（出ていく辺を持たない頂点）までのグラフ上のパス上の記号によって形成される。実際、決定性有限状態オートマトンが非巡回的であるためには、有限の文字列集合を認識する必要がある。^{[ 1 ]}

歴史

Blumerら^{[ 3 ]}は1983年に初めて有向非巡回ワードグラフ（DAWG）という用語を定義しました。AppelとJacobsen ^{[ 2 ]}は1988年に別のデータ構造に同じ名前を使用しました。それ以前の研究とは独立して、Daciukら^{[ 1 ]}は2000年に後者のデータ構造を再発見しましたが、DAFSAと呼びました

トライとの比較

DAFSAは、同じ頂点に複数のパスで到達できるようにすることで、強く関連するトライデータ構造よりも大幅に少ない頂点数で済みます。例えば、英語の4つの単語「tap」、「taps」、「top」、「tops」を考えてみましょう。これらの4つの単語のトライは12個の頂点を持ち、これらの単語の接頭辞として形成される文字列、または文字列終了マーカーが続く単語のそれぞれに1つずつ割り当てられます。しかし、DAFSAは、同じ4つの単語を、0 ≤ i ≤ 5の6つの頂点v i と、以下の辺のみで表現できます_{。v 0 からv 1}へ の「_t」ラベル_の辺、v 1 からv 2 への「a」および「o」ラベルの2つの辺 、v ₂から_v 3への_「p _」ラベルの辺、 v ₃からv ₄への「s」ラベルの辺、そしてv ₃とv _4からv ₅への「文字列終了マーカー」ラベルの辺です。メモリと機能性の間にはトレードオフがあります。標準の DAFSA では単語が存在するかどうかはわかりますが、その単語に関する補助情報を示すことはできません。一方、トライではそれが可能です。

DAFSAとトライ構造の主な違いは、文字列の保存時に接尾辞と中接辞の冗長性が排除される点です。トライ構造では、共通の接頭辞がすべて文字列間で共有されるため、接頭辞の冗長性が排除されます。例えば、「doctors」と「doctorate」では、 「doctor」という接頭辞が共有されます。DAFSAでは、接尾辞の可能な集合が同じ単語同士で共通の接尾辞も共有されます。一般的な英語の単語の辞書セットでは、これはメモリ使用量の大幅な削減につながります。

DAFSAの末端ノードには複数のパスで到達できるため、DAFSAは各パスに関連する補助情報（例えば、英語における単語の出現頻度など）を直接格納することはできません。しかし、各ノードについて、その点を通過する一意のパスの数を構造に格納すれば、単語のインデックス、あるいはインデックスが与えられた単語を取得することができます。^{[ 4 ]}補助情報は配列に格納できます。

参考文献

1. Jan Daciuk、Stoyan Mihov、Bruce Watson、Richard Watson (2000). 最小非巡回有限状態オートマトンの増加的構築. 計算言語学26 (1):3-16
2. アペル、アンドリュー；ヤコブセン、ガイ（1988）『世界最速のスクラブルプログラム』ACM通信誌、31（5）：572–578
3. Anselm Blumer, Janet Blumer, Andrzej Ehrenfeucht, David Haussler, Ross M. McConnell (1983). 単語のすべての部分語の集合に対する線形サイズ有限オートマトン - 結果の概要. Bull Europ. Assoc. Theoret. Comput. Sci, 21 : 12-20
4. Kowaltowski, T.; CL Lucchesi (1993). 「大規模語彙を表現する有限オートマトンの利用」. Software-Practice and Experience . 1993 : 15–30 . CiteSeerX  10.1.1.56.5272 .

• Blumer, A.; Blumer, J.; Haussler, D.; Ehrenfeucht, A.; Chen, MT; Seiferas, J. (1985)「テキストのサブワードを認識する最小のオートマトン」、理論計算機科学、40 : 31–55、doi : 10.1016/0304-3975(85)90157-4
• アペル、アンドリュー；ジェイコブセン、ガイ（1988）「世界最速のスクラブルプログラム」（PDF）、Communications of the ACM、31（5）：572–578、doi：10.1145/42411.42420データ構造に関する初期の言及の 1 つ。
• Jansen, Cees JA; Boekee, Dick E. (1990)「暗号学における有向非巡回語グラフの重要性について」Advances in Cryptology – AUSCRYPT '90、Lecture Notes in Computer Science、vol. 453、Springer-Verlag、pp.  318– 326、doi : 10.1007/BFb0030372、ISBN 3-540-53000-2。
• エピファニオ、キアラ；ミグノシ、フィリッポ；シャリット、ジェフリー；ヴェントゥリーニ、イラリア (2004)、「シュトゥルムグラフとモーザー予想」、カルード、クリスチャン S.；カルード、エレナ；ディニーン、マイケル J. (編)、言語理論の発展。議事録、第8回国際会議 (DLT 2004)、ニュージーランド、オークランド、2004年12月、コンピュータサイエンス講義ノート、第3340巻、シュプリンガー・フェアラーク、 175～ 187ページ 、 ISBN 3-540-24014-4、Zbl  1117.68454
• Tresoldi, Tiago (2020)、「DAFSA：決定性非巡回有限状態オートマトンのためのPythonライブラリ」、Journal of Open Source Software、5 (46): 1986、Bibcode : 2020JOSS....5.1986T、doi : 10.21105/joss.01986、hdl : 21.11116/0000-0005-AD0D-BオープンソースのPython実装。

外部リンク

• 「有向非巡回ワードグラフ（DAWG）」 – JohnPaul Adamovsky が整数配列を使って DAFSA を構築する方法を教えます（ 2022年7月22日Wayback Machineにアーカイブ）
• 「キャロラインワードグラフ（CWG）」 – JohnPaul Adamovskyが、複数の整数配列を使った新しいエンコーディングを使ってDAFSAハッシュ関数を構築する方法を教えています（ 2022年7月27日Wayback Machineにアーカイブ）