minimize.h

一个类似STL的自动机的源代码库

/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Automata handling.
 * Copyright (C) 2000-2003 Vincent Le Maout ([e-mail]).
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */

#ifndef ASTL_MINIMIZE_H
#define ASTL_MINIMIZE_H

#include <iostream>
#ifndef __DFA_GLIMPSE_H_
#include <vector>
#endif
#include <iterator>
#include <algorithm>
#include <map>
#include <set>

#ifdef _MSC_VER
#define MAXOP _MAX
#else
#define MAXOP max
#endif

#include <astl.h>
#include <nfa_mmap.h>
#include <tools.h>
#include <determinize.h>
#include <debug.h>

using namespace std;

ASTL_BEGIN_NAMESPACE

// Algorithm    : acyclic_minimization
// Description  : minimize an acyclic dfa
// Input        : a dfa
// Output       : result is written in the argument
// Precondition : dfa must be acyclic
//              : long Tag::degree_in()
//              : void Tag::degree_in(long)
//              : long Tag::equivalent_to()
//              : void Tag::equivalent_to(long)
// Uses         : height, fusion, redirect_edges, group_equivalent_states, refine_partition
//

struct minimization_tag 
{
  unsigned long _degree_in, _equivalent_to;
  unsigned char _height;

  minimization_tag() : _degree_in(0), _equivalent_to(0), _height(0) { }
  unsigned char height() const { return (_height); }
  void          height(unsigned char x) { _height = x; }
  unsigned long degree_in() const { return (_degree_in); }
  void          degree_in(unsigned long x) { _degree_in = x; }
  unsigned long equivalent_to() const { return (_equivalent_to); }
  void          equivalent_to(unsigned long x) { _equivalent_to = x; }
  friend bool operator == (const minimization_tag &x, const minimization_tag &y) {
    return (x.degree_in() == y.degree_in() && x.equivalent_to() == y.equivalent_to());
  }
};

ostream& operator << (ostream &out, const struct minimization_tag &t)
{
  out << t.degree_in() << " " << t.equivalent_to();
  return (out);
}

// Computes the height of each state in A and
// stores it in a matrix (height x state)
// yields a partition of Q 
// if q is in Q, height(q) = Max {height(p) such that (q, a, p) is in T}
// and height(q) = 0 if q has no outgoing edges
// Uses method Tag::degree_in(long) to store the number of ingoing edges of each state
// Needs template functions swap and max 

template <class DFA, class Dstate>
unsigned char 
height(DFA& A, Dstate q, vector<vector < Dstate> *> &partition)
{
  const typename DFA::Edges edg = A.delta2(q);
  unsigned char max_height = 0;
  typename DFA::Edges::const_iterator q_trans, edg_end = edg.end();
  Dstate aim;

  for (q_trans = edg.begin(); q_trans != edg_end; ++q_trans)
    {
      aim = (*q_trans).second;
      A.tag(aim).degree_in(A.tag(aim).degree_in() + 1);
      if (A.tag(aim).degree_in()>1) //la hauteur est deja calcul閑
	max_height = MAXOP(max_height,(unsigned char)(A.tag(aim).height()+1));       
      else 
	max_height = MAXOP(max_height,(unsigned char)(height(A,aim,partition)+1));
    }
  if (partition.size() <= max_height)
    partition.push_back(new vector<Dstate>(1, q));
  else
    partition[max_height]->push_back(q);
  A.tag(q).height(max_height); 
  return (max_height);
}

// Set default transition of each state in [start, finish) toward
// start state (start is the reference state of the partition)

template <class DFA, class iterator>
void 
fusion(DFA &A, iterator start, iterator finish)
{
  typedef typename DFA::State Dstate;
  typename vector<Dstate>::iterator where;
  Dstate reference = *start;
  
  for (where = start + 1; where != finish; ++where)
    A.tag(*where).equivalent_to((unsigned long) reference);  
}

// Redirect the outgoing edges of a partition based on height
// to the partition reference state and decrease the number of
// ingoing edges of aim. (delete aim if it has no ingoing edges any more) 
template <class DFA, class State>
void
redirect_edges(DFA &A, vector<State> &v)
{
  typename vector<State>::iterator where;
  for (where = v.begin(); where != v.end(); ++where)
    {
      //      cout << " redirect " << (where - v.begin());
      const typename DFA::Edges edg = A.delta2(*where);
      typename DFA::Edges::const_iterator trans, edg_end = edg.end();
      typename DFA::State new_aim, aim;
      for (trans = edg.begin(); trans != edg_end; ++trans)
	{
	  aim = (*trans).second;
	  new_aim = (typename DFA::State) A.tag(aim).equivalent_to();
	  if (new_aim != A.null_state)
	    {
	      A.change_trans(*where, (*trans).first, new_aim);
	      A.tag(aim).degree_in(A.tag(aim).degree_in() - 1);
	      if (A.tag(aim).degree_in() == 0)  // no more ingoing edges to the aim
		A.del_state(aim);
	    }
	}
    }
}

// Compares two states and returns int <0 or ==0 or >0
template <class DFA, class State>
int
compare_states(DFA &A, State q, State p)
{
  bool fq = A.final(q);
  bool fp = A.final(p);
  if (fq != fp)
    return ((int) fq - (int) fp);

  typename DFA::Edges::size_type q_trans_count = A.delta2(q).size();
  typename DFA::Edges::size_type p_trans_count = A.delta2(p).size();
  if (q_trans_count - p_trans_count != 0) 
    return (q_trans_count - p_trans_count);
  if (q_trans_count == 0) return (0);

  // Both states have the same finality and the same number of transitions
  // We apply a kind of lexicographical comparison
  typename DFA::Edges::const_iterator left_edg_end = A.delta2(q).end();
  typename DFA::Edges::const_iterator left = A.delta2(q).begin();
  typename DFA::Edges::const_iterator right = A.delta2(p).begin();

  for (; left != left_edg_end; ++left, ++right)
    {
      typedef typename DFA::Alphabet Dalph;
      typedef typename DFA::State Dstate;
      const pair<const Dalph, Dstate>& q_trans = *left;
      const pair<const Dalph, Dstate>& p_trans = *right;
    
      if (q_trans.first == p_trans.first) // Same letter
	{
	  if (q_trans.second < p_trans.second)
	    return (-1);
	  else
	    if (p_trans.second < q_trans.second)
	      return (1);
	}
      else
	if (q_trans.first < p_trans.first)
	  return (-1);
	else
	  return (1);
    }
  return (0);
}
  

// Groups equivalent states and returns the range they are in
template <class DFA, class Size_type, class State>
void
group_equivalent_states(DFA &A, vector<State> &v, Size_type start, 
			Size_type finish, pair<Size_type, Size_type> &rang)
{
  // Result is placed in 'range' argument
  Size_type g, d, pg;
  pg = g = start + 1;
  d = finish;
  State e = v[start];  // Reference state
  int res;

  while (g <= d)
    {
      res = compare_states(A, v[g], e);
      if (res == 0)
	{
	  swap(v[pg],v[g]);
	  pg++;
	  g++;
	}
      else
	if (res < 0) 
	  {
	    g++;
	  }
	else
	  {
	    res = compare_states(A, v[d], e);
	    if (res == 0)
	      if(g == pg)
		{
		  swap(v[pg],v[d]);
		  pg++;
		  g++;
		}
	      else
		{  
		  swap(v[pg],v[g]);
		  swap(v[pg],v[d]);
		  pg++;
		}
	    else
	      if(res > 0) d--;
	      else
		{   
		  swap(v[g],v[d]);
		  g++;
		}
	  }
    }
  
  rang.second = d;
  rang.first  = pg;
}   

// Refine the partition based on state height
// All equivalent states are placed together in the vector then merged
template <class DFA, class Size_type, class State>
void 
refine_partition(DFA &A, vector<State> &v,
		 Size_type start, Size_type finish)
{
  if (start < finish)
    {
      pair<typename vector<State>::size_type, typename vector<State>::size_type> range;
  
      group_equivalent_states(A, v, start, finish, range);
      if (start < range.first - 1) fusion(A, v.begin() + start, v.begin() + range.first);
      if (range.first < range.second) refine_partition(A, v, range.first, range.second);
      if (range.second + 1 < finish) refine_partition(A, v, range.second + 1, finish);
    }
}


// Main minimization function
template <class DFA>
void 
acyclic_minimization(DFA &dfa)
{
  if (dfa.state_count() > 0)
    {
      typedef typename DFA::State Dstate;
      typedef vector<vector < Dstate> *> matrix;
      matrix partition(1, new vector< Dstate>); 
      height(dfa,dfa.initial(),partition);

      if (partition[0]->empty() == false)
	{
	  typename matrix::iterator where;
	  for (where = partition.begin(); where != partition.end(); ++where)
	    {
	      redirect_edges(dfa, **where);
	      refine_partition(dfa, **where, (typename matrix::size_type) 0, (**where).size() - 1);
	      delete (*where);
	    }
	}
    }
}	  

template <typename DFA, typename NFA>
void
reverse(const DFA &a1, NFA &a2)
{
  map<typename DFA::state_type, 
    safe<typename NFA::state_type, NFA::null_state> > m;

  // for each state:
  for(typename DFA::const_iterator src = a1.begin();
      src != a1.end(); ++src) {
    // create a new state if needed:
    safe<typename NFA::state_type, NFA::null_state> &new_aim = m[*src];
    if (new_aim == NFA::null_state) {
      new_aim = a2.new_state();
      a2.final(new_aim) = (a1.initial() == *src);
      a2.tag(new_aim) = *src;
      if (a1.final(*src))
	a2.initial().insert(new_aim);
    }

    // for each transition:
    typename DFA::edges_type t = a1.delta2(*src);
    for(typename DFA::edges_type::const_iterator i = t.begin();
	i != t.end(); ++i) {
      // create a new state if needed:
      safe<typename NFA::state_type, NFA::null_state> &new_src = m[(*i).second];
      if (new_src == NFA::null_state) {
	new_src = a2.new_state();
	a2.final(new_src) = a1.initial() == new_src;
	a2.tag(new_src) = (*i).second;
	if (a1.final((*i).second))
	  a2.initial().insert(new_src);
      }
      a2.set_trans(new_src, (*i).first, new_aim);
    }
  }
}

// Requirements: DFA1::char_type convertible to DFA2::char_type
template <typename DFA1, typename DFA2>
void
brzozowski(const DFA1 &a1, DFA2 &a2)
{
  typedef NFA_mmap<typename DFA1::char_traits, typename DFA1::state_type> 
    nfa_type;

  if (a1.state_count() > 0) {
    nfa_type tmp2;
    {
      DFA1 tmp3;
      {
	nfa_type tmp1;
	reverse(a1, tmp1);
	tmp3.initial(clone(tmp3, dfirst_markc(forwarddc(tmp1))));
      } 
      reverse(tmp3, tmp2);
    }
    a2.initial(clone(a2, dfirst_markc(forwarddc(tmp2))));
  }
}
    
ASTL_END_NAMESPACE

#endif // ASTL_MINIMIZE_H