3

次の簡単なデータ構造を考えてみましょう。

data Step =
  Match Char |
  Options [Pattern]

type Pattern = [Step]

これは小さな関数と一緒に使用されます

match :: Pattern -> String -> Bool
match [] _ = True
match _  "" = False
match (s:ss) (c:cs) =
  case s of
    Match   c0 -> (c == c0) && (match ss cs)
    Options ps -> any (\ p -> match (p ++ ss) (c:cs)) ps

ここで何が起こっているかは明らかです。aは、それに含まれるステップに基づいてPattern、与えられた a に一致するか一致しないかのいずれかです。StringそれぞれStepが単一の文字 ( Match) に一致するか、可能なサブパターンのリストで構成されます。(注意: サブパターンは必ずしも同じ長さではありません! )

次のようなパターンがあるとします。

[
  Match '*',
  Options
    [
      [Match 'F', Match 'o', Match 'o'],
      [Match 'F', Match 'o', Match 'b']
    ],
  Match '*'
]

このパターンは、可能な 2 つの文字列*Foo*と*Fob*. 明らかに、これを「最適化」できます

[Match '*', Match 'F', Match 'o', Options [[Match 'o'], [Match 'b']], Match '*']

私の質問: これを行う関数をどのように記述すればよいですか?

より一般的には、特定のOptionsコンストラクターは、長さが大きく異なる任意の数のサブパスを持つことができ、共通のプレフィックスとサフィックスを持つものもあれば、持たないものもあります。サブパスを空にしたり、次のようなことを行うことさえ可能ですOptions [](もちろん何もしません)。考えられるすべての入力を正しく減らす関数を書くのに苦労しています...

4

1 に答える 1

4

大まかな検査では、これは非決定論的な有限状態オートマトンを定義したように見えます。NFA は、Michael O. Rabin によって最初に定義されました。また、他の多くのことを私たちにもたらした Dana Scott によって定義されました。

これは、受け入れ状態に基づいてステップ間の遷移を伴うステップから構築されているため、オートマトンです。各ステップでは、多くの可能な遷移があります。したがって、オートマトンは非決定論的です。これを最適化します。それを最適化する1つの方法（あなたが求めている方法ではありませんが、関連しています）は、バックトラッキングを排除することです。これを行うには、状態自体と状態に到達する方法のすべての組み合わせを使用します。これは、パワーセットの構築として知られています: http://en.wikipedia.org/wiki/Powerset_construction

ウィキペディアの記事は実際には非常に優れています。Haskell のような言語では、最初に完全なパワーセットの DFA を定義し、次に、すべての本物のパスをゆっくりとたどって、到達できないクラフトのほとんどを「取り除く」ことができます。これで適切な DFA が得られますが、必ずしも最小の DFA とは限りません。

その記事の最後で説明したように、Brzozowski のアルゴリズムを使用して、すべての矢印を反転させ、終了状態から初期状態への移行を記述する新しい NFA を取得できます。ここで、DFA を最小化する場合は、そこから再び DFA に戻り、矢印を反転してすべてをやり直す必要があります。これは必ずしも最速のアプローチではありませんが、簡単で、多くの場合に十分に機能します。より優れたアルゴリズムも多数あります: http://en.wikipedia.org/wiki/DFA_minimization

NFA を最小化するには、さまざまなアプローチがありますが、問題は一般に np-hard であるため、いくつかの毒を選択する必要があります :-)

もちろん、これは完全な NFA があることを前提としています。相互に再帰的な定義がある場合は、それ自体の「内部」にパターンを配置できます。とはいえ、この形式で NFA の操作を開始するためにも、巧妙なトリックを使用して明示的な共有構造を回復する必要があります。そうしないと、永遠にループしてしまいます。

「共有なし」ルールを挿入すると、つまり、NFA の有向グラフは非循環であるだけでなく、「オプション」セットを終了する場合を除いて分岐が「マージバック」することはありません。一般的な文字を「因数分解」するだけです。これには参照を提供するだけでなく、考えることも含まれるため、この記事が何らかの形で興味深いかもしれないことに注意して、今のところはそのままにしておきます。

ps

「因数分解」ソリューションの突き刺しは、次のタイプの関数です。

factor :: [Pattern] -> (Maybe Step, [Pattern])
factor = -- pulls out a common element of the pattern head, should one exist. shallow.

factorTail = -- same, but pulling out of the pattern tail

simplify :: [Pattern] -> [Pattern]
simplify = -- remove redundant constructs, such as options composed only of other options, which can be flattened out, options with no elements that are the "only" option, etc. should run "deep" all levels down.

これで、最低レベルから始めて、(simplify . factor)新しい要素がなくなるまでサイクルを繰り返すことができます。次に、でそうし(simplify . factorTail)ます。次に、レベルを 1 つ上げて、同じことを行います。これを「だまして」非最小ソリューションにできなくても、私はショックを受けませんが、ほとんどの場合、非常にうまく機能すると思います。

更新: このソリューションが対処しないのは、たとえばオプション ["--DD--", "++DD++"] (文字列を一致のリストとして読み取る) がある場合であるため、両方のヘッドに珍しい構造があります。と尾が真ん中ではありません。このような場合のより一般的な解決策は、リスト内のすべての一致から最も一般的でない部分文字列を取り出し、それを「フレーム」として使用して、異なるセクションにオプションを挿入することです。

于 2013-05-28T04:41:29.833 に答える