Javaの有限オートマトンによる入力の検証

投稿日: 2019-10-19 2019-11-05
タグ: Algorithms, Java

1.概要

あなたがCSを勉強したことがあるならば、あなたは間違いなくコンパイラまたは類似した何かについてのコースを受講しました。これらのクラスでは、有限オートマトン（有限状態機械としても知られています）の概念が教えられています。これは言語の文法規則を形式化する方法です。

あなたは主題https://www.cs.rochester.edu/u/nelson/courses/csc

173/fa/fa.html[here]およびhttps://en.wikipedia.org/wiki/Deterministic

finite__automaton[件の詳細について読むことができますここに]。

それでは、この忘れられた概念が、新しいコンパイラーの構築を心配する必要がない私たち、上級プログラマーにとってどのように役立つのでしょうか。

実のところ、この概念によって多くのビジネスシナリオが単純化され、複雑なロジックについて推論するためのツールが得られることがわかりました。

簡単な例として、外部のサードパーティ製ライブラリを使わずに入力を検証することもできます。

2.アルゴリズム

一言で言えば、そのようなマシンは状態と、ある状態から別の状態に移行する方法を宣言します。ストリームを通過させると、次のアルゴリズム（疑似コード）を使ってその形式を検証できます。

for (char c in input) {
    if (automaton.accepts(c)) {
        automaton.switchState(c);
        input.pop(c);
    } else {
        break;
    }
}
if (automaton.canStop() && input.isEmpty()) {
    print("Valid");
} else {
    print("Invalid");
}

現在の状態から文字がある矢印があれば、オートマトンは与えられた文字を「受け入れる」と言います。状態の切り替えとは、ポインタがたどられ、現在の状態が矢印の指す状態に置き換えられることを意味します。

最後に、ループが終了したら、オートマトンが「停止」できる（現在の状態が二重丸で囲まれている）かどうか、およびその入力が使い果たされたかどうかを確認します。

3.例

実際のアルゴリズムを確認するために、JSONオブジェクト用の簡単なバリデータを書きましょう。これはオブジェクトを受け取るオートマトンです:

リンク:/uploads/json__dfa-2.png%20784w[]

valueは、string、integer、boolean、null、または別のJSONオブジェクトのいずれかになります。簡潔にするために、この例では文字列のみを検討します。

3.1. コード

有限状態機械を実装することは非常に簡単です。次のものがあります。

public interface FiniteStateMachine {
    FiniteStateMachine switchState(CharSequence c);
    boolean canStop();
}

interface State {
    State with(Transition tr);
    State transit(CharSequence c);
    boolean isFinal();
}

interface Transition {
    boolean isPossible(CharSequence c);
    State state();
}

それらの間の関係は次のとおりです。

ステートマシンには1つの現在の

State

があり、停止できるかどうかを通知します

かどうか（状態が最終的かどうか）
**

State

には、追従できるトランジションのリストがあります。

矢印）
**

Transition

は、その文字が受け入れられたかどうかを示し、

次の

州

publi class RtFiniteStateMachine implements FiniteStateMachine {

    private State current;

    public RtFiniteStateMachine(State initial) {
        this.current = initial;
    }

    public FiniteStateMachine switchState(CharSequence c) {
        return new RtFiniteStateMachine(this.current.transit(c));
    }

    public boolean canStop() {
        return this.current.isFinal();
    }
}

FiniteStateMachine

実装は不変** であることに注意してください。これは主にその単一のインスタンスが複数回使用される可能性があるためです。

以下に、実装

RtState

があります。

with（Transition）

メソッドは、流暢さを期して、トランジションが追加された後のインスタンスを返します。

State

は、それが最終的なもの（二重丸で囲まれている）かどうかも示します。

public class RtState implements State {

    private List<Transition> transitions;
    private boolean isFinal;

    public RtState() {
        this(false);
    }

    public RtState(boolean isFinal) {
        this.transitions = new ArrayList<>();
        this.isFinal = isFinal;
    }

    public State transit(CharSequence c) {
        return transitions
          .stream()
          .filter(t -> t.isPossible(c))
          .map(Transition::state)
          .findAny()
          .orElseThrow(() -> new IllegalArgumentException("Input not accepted: " + c));
    }

    public boolean isFinal() {
        return this.isFinal;
    }

    @Override
    public State with(Transition tr) {
        this.transitions.add(tr);
        return this;
    }
}

そして最後に、

RtTransition

は遷移規則をチェックし、次の

State

を与えることができます。

public class RtTransition implements Transition {

    private String rule;
    private State next;
    public State state() {
        return this.next;
    }

    public boolean isPossible(CharSequence c) {
        return this.rule.equalsIgnoreCase(String.valueOf(c));
    }

   //standard constructors
}

上記のコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-1/src/main/java/com/baeldung/algorithms/automata[here]です。

この実装では、どのステートマシンも構築できるはずです。

冒頭で説明したアルゴリズムは、次のように簡単です。

String json = "{\"key\":\"value\"}";
FiniteStateMachine machine = this.buildJsonStateMachine();
for (int i = 0; i < json.length(); i++) {
    machine = machine.switchState(String.valueOf(json.charAt(i)));
}

assertTrue(machine.canStop());

テストクラスhttps://github.com/eugenp/tutorials/blob/ef7400484c2409ae25a82874e16a1b8d53ba2b32/algorithms/src/test/java/algorithms/RtFiniteStateMachineLongRunningUnitTest.java[RtFiniteStateMateStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMachStateMach（）（））;）}））））））））））上記の画像よりもいくつかの状態が追加されていることに注意してください。これは、文字列を囲む引用符も正しく捉えるためです。

4.まとめ

有限オートマトンは、構造化データの検証に使用できる優れたツールです。

ただし、複雑な入力になると複雑になる可能性があるため、一般的にはあまり知られていません（トランジションは1文字しか使用できないため）。それにもかかわらず、それはそれがルールの簡単なセットをチェックすることになると素晴らしいです。

最後に、有限ステートマシンを使用してさらに複雑な作業を行いたい場合は、https://github.com/statefulj/statefulj[StatefulJ]およびhttps://github.com/hekailiang/squirrel[squirrel]の2つが参考になりますに。

GitHub

でコードサンプルを確認できます。

getdocs

9427