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

コンピュータサイエンスにおいて、決定性非巡回有限状態オートマトン（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 つの接頭辞として形成された文字列、または文字列の終了マーカーが続く単語の 1 つに 1 つずつあります。ただし、DAFSA は、0 ≤  i _{≤ 5 の 6 つの頂点}v _i と、次のエッジのみを使用して、同じ 4 つの単語を表すことができます。v 0 から v 1 へのエッジは「t _」というラベルが付けられ、v _1からv ₂への2 つのエッジは「a」と「o」というラベルが付けられ、v _2からv ₃へのエッジは「p」というラベルが付けられ、v _3からv ₄へのエッジは「s」というラベルが付けられ、v ₃とv _4からv ₅へのエッジは文字列の終了マーカーでラベル付けされます。メモリと機能性の間にはトレードオフがあります。標準の DAFSA では単語が存在するかどうかはわかりますが、その単語に関する補助情報を示すことはできないのに対し、トライではそれが可能です。

DAFSA とトライの主な違いは、文字列を格納する際に接尾辞と中辞の冗長性が排除されることです。トライでは、共通の接頭辞がすべて文字列間で共有されるため、接頭辞の冗長性が排除されます。たとえば、doctorsとdoctorateの間では、 doctor接頭辞が共有されます。DAFSA では、互いに同じ接尾辞のセットを持つ単語の共通の接尾辞も共有されます。一般的な英語の単語の辞書セットの場合、これはメモリ使用量の大幅な削減につながります。

DAFSAの末端ノードには複数のパスで到達できるため、DAFSAは各パスに関連する補助情報（英語での単語の頻度など）を直接保存することはできません。ただし、各ノードについて、構造内のそのポイントを通過する一意のパスの数を保存しておけば、それを使用して単語のインデックス、またはインデックスが指定された単語を取得できます。^[4]補助情報は配列に保存できます。

• 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。
• エピファニオ、キアラ。ミニョーシ、フィリッポ。シャリット、ジェフリー。 Venturini、Ilaria (2004)、「Sturmian charts and a conjecture of Moser」、Calude、Cristian S.;カルード、エレナ。 Dineen、Michael J. (編)、言語理論の発展。 Proceedings、第 8 回国際会議 (DLT 2004)、オークランド、ニュージーランド、2004 年 12 月、Lecture Notes in Computer Science、vol. 3340、シュプリンガー版、175–187 ページ、ISBN 3-540-24014-4、Zbl  1117.68454
• Tresoldi, Tiago (2020)、「DAFSA: 決定論的非巡回有限状態オートマトン用の Python ライブラリ」、Journal of Open Source Software、5 (46): 1986、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にアーカイブ)