接尾辞オートマトンとは正確には何なのか、それがどのように機能し、接尾辞ツリーや接尾辞配列とどのように異なるのかを説明してもらえますか? すでにウェブで検索してみましたが、明確で包括的な説明に出くわすことができませんでした。
私が求めていたものに最も近い次のリンクを見つけましたが、それはロシア語であり、英語への翻訳は理解しにくかった.
2160 次
2 に答える
4
サフィックス オートマトンは、文字列のすべてのサフィックスを認識する有限状態マシンです。有限状態マシンについては、読むことができるリソースがたくさんあります。ウィキペディアは良い出発点です。
サフィックス ツリーとサフィックス配列は、文字列のすべてのサフィックスを含むデータ構造です。文字列に対して効率的に操作を実行するために、これらの構造を構築して動作するための複数のアルゴリズムがあります。
于 2014-11-16T23:12:38.053 に答える
3
サフィックス マシン:
サフィックス マシン (または単語の有向非巡回グラフ) は、多くの文字列の問題を解決できる強力なデータ構造です。
たとえば、マシンの接尾辞を使用して、ある文字列が別の文字列に出現するすべてを検索したり、指定された文字列の異なる部分文字列の数を数えたりすることができます。どちらのタスクも線形時間で解決できます。
直感的なレベルでは、サフィックス オートマトンは、特定の文字列のすべての部分文字列に関する簡潔な情報として理解できます。印象的な事実は、接尾辞オートマトンには、長さ n の文字列の場合、O(n) メモリしか必要としないような簡潔な形式ですべての情報が含まれていることです。さらに、時間 O(n) にわたって構築することもできます (アルファベット k のサイズを定数と見なす場合。そうでない場合は、O (n log k) の間)。
歴史的に、マシンの最初の線形サイズのサフィックスは、1983 年に Blumer などによって開かれ、1985 年から 1986 年にかけて、線形時間で構築された最初のアルゴリズム (Crochemore、Blumer など) が発表されました。詳細については、記事の最後にある参考文献を参照してください。
英語では、「サフィックス オートマトン」（複数形 - 「サフィックス オートマタ」）と呼ばれるサフィックス マシンと、「有向非巡回ワード グラフ」（または単に「DAWG」）という単語の有向非巡回グラフ。
接尾辞オートマトンの定義:
意味。与えられた文字列 s の接尾辞オートマトンは、文字列 s のすべての接尾辞を受け入れる最小決定論的有限オートマトンと呼ばれます。
この定義について説明します。
- サフィックスオートマトンは有向非巡回グラフであり、頂点は状態と呼ばれ、グラフの弧は
これらの状態間の遷移です。- 状態 t_0 の 1 つは初期状態と呼ばれ、グラフの起点でなければなりません (つまり、他のすべての状態で達成可能です)。
- オートマトンの各遷移は、何らかの記号でマークされたアークです。任意の状態から発生するすべての遷移には、異なるラベルが必要です。（一方、どのキャラクターもトランジションではないかもしれません。）
- 最終状態としてマークされた 1 つ以上の状態。初期状態 t_0 からいずれかの最終状態に移動し、このラベルをすべてのアークが通過したと書く と、文字列 s の接尾辞の 1 つで
なければならない文字列が得られます。- サフィックス オートマトンには、上記の条件を満たすすべてのマシンの中で最小数の頂点が含まれます。
(遷移の最小数は必要ありません。これ
は、マシン内の状態数の最小化の条件が「余分な」
方法ではない可能性があるためです。そうしないと、以前のプロパティが壊れてしまいます。)
接尾辞オートマトンの基本的なプロパティ:
サフィックス オートマトンの最も単純でありながら最も重要なプロパティは、文字列 s のすべての部分文字列に関する情報が含まれていることです。つまり、初期状態 t_0 からの任意のパスは、このパスに沿ってアークのラベルを書き出すと、必然的に文字列 s の部分文字列を形成します。逆に、文字列 s の任意の部分文字列は、初期状態 t_0 で始まる何らかのパスに対応します。
説明を簡単にするために、部分文字列は初期状態からのパス、部分文字列を形成するラベルに対応するとします。逆に言えば、任意のパスは、そのアークのラベルによって形成される 1 つの行に対応すると言えます。
各ステート マシンのサフィックスには、初期状態からの 1 つまたは複数のパスがあります。状態が、これらすべての方法に一致する一連の文字列に対応しているとしましょう。
例:
于 2015-01-26T14:57:35.820 に答える