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

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

1. 概要

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

あなたは主題こことここについてもっと読むことができます。

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

そうですね、この概念は多くのビジネスシナリオを単純化し、複雑なロジックについて推論するためのツールを提供できることがわかりました。

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

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オブジェクトの簡単なバリデーターを作成してみましょう。オブジェクトを受け入れるオートマトンは次のとおりです。

値は、文字列、整数、ブール値、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();
}

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

ステートマシンには現在のStateが1つあり、停止できるかどうか（状態が最終かどうか）を通知します。
State には、たどることができる遷移のリストがあります（外向きの矢印）
Transition は、キャラクターが受け入れられたかどうかを通知し、次のStateを提供します

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の実装は不変であることに注意してください。これは主に、1つのインスタンスを複数回使用できるようにするためです。

次に、実装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：

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
}

上記のコードはここです。この実装により、任意のステートマシンを構築できるようになります。最初に説明したアルゴリズムは、次のように単純です。

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());

テストクラスRtFiniteStateMachineTestをチェックして、 buildJsonStateMachine（）メソッドを確認します。文字列を適切に囲む引用符をキャッチするために、上の画像よりもいくつかの状態が追加されていることに注意してください。

4. 結論

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

ただし、複雑な入力になると複雑になる可能性があるため、広く知られていません（トランジションは1文字にしか使用できないため）。それでも、単純なルールのセットをチェックする場合は優れています。

最後に、有限状態マシンを使用してより複雑な作業を行いたい場合は、StatefulJとsquirrelを調べる価値のある2つのライブラリです。

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

getdocs

13036