前回の記事では DFA 最小化アルゴリズムとして Brzozowski のアルゴリズムを解説しました。今回は、別の最小化アルゴリズムとして Hopcroft のアルゴリズムについて解説します。

"Introduction to Automata Theory, Languages, and Computation" (日本語訳『オートマトン言語理論計算論』) の著者の一人として知られる John Hopcroft が 1971 年に発表したアルゴリズムです。実装を工夫することで最悪計算量は DFA の状態数 $n$ に対して $O(n \log n)$ となることが知られています。しかし、正当さがやや直感的でないことから、オートマトン理論の教科書や講義などで触れられる機会は少ないように思います。

この記事では、Hopcroft のアルゴリズムの実装に加えて、その正しさの証明や計算量の解析を行います。

実装と解説

この記事で説明する内容は、次の参考文献の内容を元にしています。これは Hopcroft のアルゴリズムの原論文 (のはず) です。

Hopcroft, John. "An n log n algorithm for minimizing states in a finite automaton." Theory of machines and computations. Academic Press, 1971. 189-196. (PDF)

実装

さっそくですが、Ruby による実装を紹介します。

require 'set'
 
# Partition Refinement というデータ構造の実装。
#
# 参考: https://en.wikipedia.org/wiki/Partition_refinement
class PartitionRefinement
  # 元となる集合でデータ構造を初期化する。
  def initialize(values)
    block = Set.new(values)
    # ブロックの `object_id` からそのブロックへの Hash。
    @blocks = { block.object_id => block }
    # 各値とその値の属すブロックの `object_id` の Hash。
    @value_to_block = values.map { |value| [value, block.object_id] }.to_h
  end
 
  # 与えられた集合で元となる集合を分割する。
  # 計算量は与えられた集合の大きさを n として O(n)。
  # 戻り値はこの集合で分割された2つのブロックの組の配列。
  def refine(values)
    # 与えられた集合の各値に対応するブロックの `object_id` から、
    # そのブロックの分割先のブロックへの Hash を構築する。
    split = {}
    values.each do |value|
      block_id = @value_to_block[value]
      split[block_id] ||= Set.new
      split[block_id] << value
    end
 
    # 元のブロックから分割した値を削除する。
    result = []
    split.each do |block_id, new_block|
      block = @blocks[block_id]
      if block.size != new_block.size
        block.subtract(new_block)
        @blocks[new_block.object_id] = new_block
        new_block.each do |value|
          @value_to_block[value]  = new_block.object_id
        end
        result << [block, new_block]
      end
    end
    result
  end
 
  # 現在のブロックの配列。
  def blocks
    @blocks.values
  end
 
  # ブロックの `object_id` からその部分集合を取得する。
  def [](block_id)
    @blocks[block_id]
  end
end
 
# DFA (決定性有限状態オートマトン) を表すデータ構造。
DFA = Struct.new(
  :state_set,        # 状態の集合
  :alphabet,         # アルファベット
  :transition,       # 遷移関数
  :init_state,       # 初期状態
  :accept_state_set, # 受理状態の集合
)
 
# 与えられた DFA に対して Hopcroft の最小化アルゴリズムを適用する。
# 最悪計算量は DFA の状態数 n に対して O(n log n)。
def hopcroft(dfa)
  # (1)
  # リバースした遷移関数を求める。
  transition = dfa.transition
  reversed_transition = transition
    .each_key
    .group_by { |(q, a)| [transition[[q, a]], a] }
    .map { |(k, v)| [k, v.map(&:first).to_set] }
    .to_h
 
  # (2)
  # 状態の集合を、まず受理状態とそれ以外の状態に分割する。
  partition = PartitionRefinement.new(dfa.state_set)
  partition.refine(dfa.accept_state_set)
 
  # (3)
  # 待ちリスト wait に各文字とブロックの `object_id` の組を追加する。
  wait = []
  in_wait = Set.new
  dfa.alphabet.each do |a|
    partition.blocks.each do |block|
      wait << [a, block.object_id]
      in_wait << [a, block.object_id]
    end
  end
 
  # (4)
  # 待ちリスト wait が無くなるまで繰り返す。
  until wait.empty?
    # (4.1)
    # 待ちリスト wait から文字 a とブロック block を取り出す。
    a, block_id = wait.pop
    in_wait.delete([a, block_id])
    block = partition[block_id]
 
    # (4.2)
    # 文字 a でブロックに含まれる状態へと遷移する状態の集合 previous を求める。
    previous = Set.new
    block.each { |q| previous.merge(reversed_transition[[q, a]] || []) }
 
    # (4.3)
    # 集合 previous で分割して、分割された各ブロックについて繰り返す。
    partition.refine(previous).each do |(old, new)|
      # (4.3.1)
      # 各文字と待ちリストに含まれていない大きさの小さい方のブロックを、
      # 待ちリスト wait に追加する。
      old_id, new_id = old.object_id, new.object_id
      min_block_id = old.size < new.size ? old_id : new_id
      dfa.alphabet.each do |b|
        next_id = !in_wait.include?([b, old_id]) ? min_block_id : new_id
        wait << [b, next_id]
        in_wait << [b, next_id]
      end
    end
  end
 
  # (5)
  # 各ブロックに含まれる状態からそのブロックへの Hash で、
  # 元の DFA の状態を置き換える。
  divide = partition.blocks
    .flat_map { |block| block.map { |q| [q, block] } }.to_h
  DFA.new(
    dfa.state_set.map { |q| divide[q] }.to_set,
    dfa.alphabet,
    dfa.transition.map { |((q1, a), q2)| [[divide[q1], a], divide[q2]] }.to_h,
    divide[dfa.init_state],
    dfa.accept_state_set.map { |q| divide[q] }.to_set,
  )
end

実装についてはコメントの通りです。 hopcroft の実装中の (1) のようなコメントは後から参照する用です。

それと、Partition Refinement について少し補足します。これは元となる集合 $X$ の細分 $P_1, P_2, \cdots, P_n$ (互いに素で和がちょうど $\bigcup P_j = X$ となる) を管理するデータ構造で、集合 $A$ で分割する操作 (各 $P_j$ について $P_j \ne A \land P_j \cap A \ne \varnothing$ のとき、 $P_j$ を $P_j \cap A$ と $P_j \setminus A$ で置き換える) が $O(|A|)$ で行なえるものです。

正当性

次にアルゴリズムの正当性を確認します。

まず、このアルゴリズムは必ず停止することを確認します。一見すると同じブロックの object_id が待ちリスト wait に複数回追加される可能性があるため無限にループしそうにも思えますが、そのようなことはありえません。なぜなら、wait に追加される前に必ずブロックは分割されているため、以前に処理したときよりも小さくなっています。そして、1 要素だけになったブロックがさらに分割されることはないため、(4) のループは必ず終了し、アルゴリズムも停止します。

アルゴリズム中で Partition Refinement で管理している 2 つの異なる細分 $P_1, P_2$ に含まれる状態 $q_1 \in P_1, q_2 \in P_2$ は区別可能な状態 (その状態からはじめて受理される文字列の集合が異なる) となることを帰納法で確認します。最初の (2) で初期化した時点では、受理状態とそれ以外の状態に分けられていますが、それらは明らかに区別可能です。次に(4.3) で分割された場合を考えます。 (4.1) で取り出された文字を $a$ 、細分を $P$ 、 (4.3) で分割された細分を $P_1, P_2$ とすると、どちらか一方に含まれる状態では $a$ で $P$ のいずれかの状態に遷移できますが、もう一方では不可能のため、区別可能だと分かります。

最後に、区別可能な状態が同じ細分に含まれている状態でアルゴリズムが停止したとすると矛盾が生じることにより、このアルゴリズムが状態の集合を正しく区別不可能な部分集合に分割し、最小化が行えることを確認します。このとき、細分 $P$ に含まれる 2 つの状態 $q_1, q_2 \in P$ が区別可能なとき、 $q_1, q_2$ の関係には次の 3 つの場合が考えられます。

ある文字 $a$ での $q_1$ の遷移先 $q'_1$ の属する細分と、 $q_2$ の遷移先 $q'_2$ の属する細分が異なる場合。
ある文字 $a$ での一方の遷移先 $q'$ は存在するが、もう一方の遷移先は存在しない場合。
2 文字以上の文字列 $w$ で一方からはじめた場合受理されるが、もう一方はそうではない場合。

3 の場合はその文字列で遷移させていって、遷移先が別の細分になった、もしくは一方の遷移先が無くなったところで止めれば 1 か 2 の状況になります。なので 1 か 2 の場合だけを考えればよいです。

$q'_1$ を含む細分と $q'_2$ を含む細分が分割されているということは、少なくともこのどちらかが待ちリストに入り、分割が行なわれるはずです。だとすると、 $q_1, q_2$ を含む細分が分割されていない、ということはありえないため、矛盾が生じます。
待ちリストが受理状態の集合とそれ以外の状態の集合から始まっているため、すべての状態についてそれを含む細分で一度は分割を行なっています。よって $q'$ を含む細分も分割されていなければならず、矛盾が生じます。

以上で Hopcroft のアルゴリズムの正当性を確認できました。

ちなみに DFA の遷移関数が任意の状態、文字について遷移先が存在するような場合は 2 の場合分けが必要ないので、 (3) で待ちリストに追加するのも大きさの小さい方だけで十分です。

計算量

最悪計算量が状態数 $n$ に対して $O(n \log n)$ となることを確認します。

まず (1), (2), (3) と (5) は $O(n)$ で処理できることに注意してください。これは単なるアルファベットに対するループであったり、遷移関数の各対応に対するループのためです。

よって (4) のループの計算量が支配的となります。

ループの中身 (つまり (4.1) から (4.3)) の計算量は、取り出した文字 $a$ で取り出した細分 $P$ のいずれかの状態へと遷移する状態の数と $|P|$ に比例します。つまり $a_j$ を文字 $a$ で細分 $P_j$ のいずれかの状態へと遷移する状態の個数として、 $O(a_j + |P_j|)$ です。なぜなら、(4.3) の PartitionRefinement#refine の計算量と戻り値の配列の大きさは与えられた集合の大きさに比例するのと、 (4.2) の計算量は |P| の大きさに依存するからです。この比例係数を $k$ とします。

細分が $P_1, P_2, \cdots, P_n$ まであり、ある文字 $a$ について $(a, P_1), \cdots, (a, P_r)$ までが待ちリストに追加されていて、残りの $P_{r+1}, \cdots, P_n$ との組は追加されていないような状況から、ループが終了するまでの計算量が次の式 $T$ で抑えられると仮定します。

T = k\left[\sum_{j=1}^r (a_j + |P_j|) \log |P_j| + \sum_{j=r+1}^n (a_j + |P_j|) \log |P_j|/2\right]

この式は突然出てきた感じがしますが、直感的には左の総和 (待ちリストに含まれてる方) は一回のループに $k (a_j + |P_j|)$ かかる処理を、それが分割されてまた待ちリストに入るため $\log |P_j|$ 回起こる可能性がある、ということを表していて、右の総和 (待ちリストに含まれていない方) は最初の 1 回のループが無い分 2 分の 1 にされている、というイメージになります。

このとき、 $\sum a_j = n$ かつ $\sum |P_j| = n$ で、各 $\log |P_j|, \log |P_j|/2$ は $\log n$ 以下なので、 $T \le 2k n \log n$ であることは容易に分かるでしょう。よって、この式で抑えられることが正しいことを確かめたいです。

$a$ 以外の文字との組が取り出されて、その結果分割が起こった場合を考えます。この場合の新たな計算量 $\hat{T}$ は必ず $T$ 以下になります。待ちリストに含まれる細分 $P_j$ が分割されたのであれば、分割した結果の細分を $P_{j1}, P_{j2}$ として $T$ の $(a_j + |P_j|) \log |P_j|$ の部分が $(a_{j1} + |P_{j1}|) \log |P_{j1}| + (a_{j2} + |P_{j2}|) \log |P_{j2}|$ となりますが、 $\log |P_{j1}|, \log |P_{j2}|$ は $\log |P_j|$ 以下なので、 $\hat{T}$ は $T$ 以下と分かります。待ちリストに含まれない細分 $P_k$ が分割された場合も、分割した結果の細分を $P_{j1}, P_{j2}$ として、さらに $|P_{j1}| \le |P_{j2}|$ として考えます。この場合 $T$ の $(a_j + |P_j|) \log |P_j|/2$ が $(a_{j1} + |P_{j1}|) \log |P_{j1}| + (a_{j2} + |P_{j2}|) \log |P_{j2}|/2$ となるのですが、 $|P_j|= |P_{j1}| + |P_{j2}|$ かつ $|P_{j1}| \le |P_{j2}|$ より $|P_{j1}| \le |P_j|/2$ および $|P_{j2}|/2 \le |P_j|/2$ なので、 $\hat{T}$ が $T$ 以下になることが確かめられます。よって他の文字との組で分割が起こる場合でも、 $T$ で抑えられることが分かりました。

最後に、 $r$ についての帰納法で $T$ で抑えられることを確かめましょう。 $r = 0$ の場合は待ちリストに存在しない場合なので、当然成り立ちます。 $r > 0$ の場合、 $r-1$ までで成り立っているとして、 $r$ が待ちリストに入っていて、そこでちょうど取り出されるところで成り立つか考えます。この場合の計算量は、帰納法の仮定より次のようになります。

k \left[ (a_r + |P_r|) + (a_r + |P_r|) \log |P_r|/2 + \sum_{j=1}^r (a_j + |P_j|) \log |P_j| + \sum_{j=r+1}^m (a_j + |P_j|) \log |P_j|/2 \right]

しかし $(a_r + |P_r|) + (a_r + |P_r|) \log |P_r|/2 = (a_r + |P_r|) (\log 2 + \log |P_r|/2) = (a_r + |P_r|) \log |P_r|$ より、これは $T$ そのものです。よって、すべての $r$ について $T$ で抑えられることが確認できました。

以上で、アルゴリズムの計算量が $O(n \log n)$ であることを確認しました。

まとめ

Hopcroft のアルゴリズムの正しさと計算量が $O(n \log n)$ であることを確認しました。実は論文の内容ほとんどそのままなのですが、それなりに分かりやすく説明したつもりです。しいて違うところを挙げるなら、正当性の部分で完全でない DFA について考えているところと、計算量のところが論文では (4) の 1 回のループを $a_j$ に比例する時間で行えるとしているのですが、 (少なくとも今回の実装では) あやしいと感じたので $a_j + |P_j|$ としているところです。論文にはソースコードも付属しているのですが、印刷の関係でほとんど読めないし、読めても古の ALGOL のコードを読むのはしんどいだろうな、と思うので、実際にどうなのかはよく分かってません。

論文には実装して行なった実験結果もあるのですが、実行環境が IBM System/360 モデル 67 とかで面白いです。でもその時代のプログラムでも、そこそこの大きさに対してちゃんと動いたんだなと感心する部分もあります。

というわけで、この記事に最後まで目を通していただきありがとうございました。

makenowjust-labs/blog

Hopcroft のアルゴリズムについて

実装と解説

実装

正当性

計算量

まとめ