65.9K
CodeProject 正在变化。 阅读更多。
Home

有限状态自动机的面向对象方法

Lutosław
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.85/5 (18投票s)

2009年1月31日

CPOL

7分钟阅读

viewsIcon

62939

downloadIcon

1086

对 FSA 的简要介绍和即用型类库

引言

摘自 维基百科

有限状态机 (FSM) 或 有限状态自动机 (复数: 自动机) 或简称为 状态机，是一种行为模型，由有限数量的状态、这些状态之间的转换以及动作组成。有限状态机是一种具有原始内部存储的机器的抽象模型。

Using the Code

本文将重点介绍摩尔机。理解摩尔FSA最简单的方法是分析其图表。

示例 1

  • 圆圈中的符号是状态，它们组成集合 {q0, q1}。每个状态都必须有一个唯一的符号。
  • 每个状态旁边的标签 {y0, y1} 描述了机器进入该状态时生成的数据。
  • 箭头表示状态之间的转换。集合 {z0, z1} 也可以称为“输入字母表”。

总之，摩尔FSA由带有分配的输出符号的状态以及这些状态之间的转换组成。摩尔FSA是维基百科定义的一个特定案例。

让我们来了解它是如何工作的。如果我们在 q0 状态，那么发送 z0 信号不会改变任何东西——我们仍将停留在原地并重复生成 y0 (在图上检查一下!)。然而，发送 z1 会将我们移动到 q1 状态并生成 y1。现在情况类似：z0 = 留在此处；z1 = 返回到 q0 状态。

该机器可以编码如下：

MooreAutomaton moore = new MooreAutomaton(new MooreState[] {
	// state q0
	new MooreState {
		Table = new int[] {
			0, // z0: stay in q0
			1, // z1: move to q1
		},
		Output = 0
	},
	// state q1
	new MooreState {
		Table = new int[] {
			1, // z0: stay here
			0, // z1: return to q0
		},
		Output = 1
	}
});

示例 2

上述自动机检测字符串中的单词，假设它们只能由空格分隔。如果遇到任何其他字符，机器应进入一个陷阱状态。当且仅当没有从Q到另一个状态的转换时，状态Q才是陷阱状态。同样，我们假设初始状态是q0。

发送字符串 "abc de #fg" 将输出 1110110222。请注意，机器在**进入**某个状态时才给出输出。这台机器可以通过 AsciiTableGenerator 类轻松实现

const int sNothing = 0; // avoid "magic numbers" in your code!
const int sWord = 1;
const int sError = 2;

MooreAutomaton moore = new MooreAutomaton(new MooreState[] {
    // q0 = sNothing
    new MooreState {
        Table = new MooreAsciiTableGenerator {
            EmptyTransition = sError, // "any other"
            Expressions = { // put Regex here
                { @"\s", sNothing },
                { @"\w", sWord }
            }
        }.GenerateTable(),
        Output = 0    // between words
    },
    // q1 = sWord
    new MooreState {
        Table = new MooreAsciiTableGenerator {
            EmptyTransition = sError,
            Expressions = {
                { @"\s", sNothing },
                { @"\w", sWord }
            }
        }.GenerateTable(),
        Output = 1    // inside a word
    },
    // q2 = sError
    new MooreState {
        Table = new MooreAsciiTableGenerator {
            EmptyTransition = sError
        }.GenerateTable(),
        Output = 2    // error
    }
});

AsciiTableGenerator 生成一个包含 128 个整数（可打印字符的 ASCII 码）的表。正则表达式在创建表时只评估一次，因此字符的索引等于其 ASCII 值。此解决方案使我们查找下一个状态的复杂度为 O(1)。

如果您希望支持所有 UNICODE 字符，您可能需要使用 ParsingAutomaton

ParsingAutomaton parser = new ParsingAutomaton(new ParsingState[] {
    new ParsingState {
        EmptyTransition = sError,
        Expressions = {
            { @"\s", sNothing },
            { @"\w", sWord }
        },
        Output = 0
    },
    new ParsingState {
        EmptyTransition = sError,
        Expressions = {
            { @"\s", sNothing },
            { @"\w", sWord }
        },
        Output = 1
    },
    new ParsingState {
        EmptyTransition = sError,
        Output = 2
    }
});

声明与之前的类似，但它在运行时评估正则表达式。这两台机器都可以使用以下代码执行：

for (int i = 0; i < inputString.Length; i++)
	Console.Write(automaton.Send(inputString[i]));

顺便说一句，通常建议使用 fixed 语句而不是 inputString[i]。

示例 3：INI 文件解析器

如果您正在寻找一个好的 INI 文件解析器，请访问我的文章“INI 文件”。现在我将讨论一个由摩尔机构建的简单 INI 文件解析器。

首先，摩尔机还有另一种有用的可视化表示。我们来检查一下INI文件的结构，好吗？

[SectionName]
Key=Value

我这里可以看到七种可能的状态

0[1SectionName2]3
0Key4=5Value6

现在我们必须分析上述表达式，并决定解析器何时应从一个状态移动到另一个状态。创建FSA的重要阶段是测试它。测试项目中包含了一个完整的解决方案。

生成超快速摩尔码

每个Moore FSA都可以转换为类似于此的程序

fixed (int* _q = Q) { // Q - table of states
	int* q = _q;
	int y_i = 0; // Y - output buffer
	int[] Y_old;
	fixed (int* _r = R) { // R - state-output table
		fixed (int* _z = Z) { // Z - input alphabet
			for (int* z = _z; *q >= 0 && z - _z < Z_len; z++, y_i++) {
				int nextq = *(q + *z);
				Y[y_i] = *(_r + nextq);
				q = _q + stateLen * nextq;
				if (y_i >= buferLen - 1) {
					Y_old = Y; // reallocate if needed
					Y = new int[buferLen *= 2];
					Array.Copy(Y_old, Y, Y_old.Length);
				}
			}
		}
	}
	Y_old = Y;
	Y = new int[y_i];
	Array.Copy(Y_old, Y, Y.Length); // update the size of the buffer
}
return Y;

FastRun(int[] input) 方法执行快速运行，并以 int[] 表的形式返回输出。在内部，它生成这些 Q 和 R 表并运行上述算法。它速度相当快，使摩尔自动机编程成为性能关键问题的一个可观的解决方案。更多文档可以在 MooreTables 结构周围找到。

FSA 的有用包装器

每个 XxxAutomaton 类都派生自抽象类 FiniteStateAutomaton。它提供了一组基本功能，并可用作机器核心（例如 MooreAutomaton 或 MealyAutomaton）与包装类之间的桥梁。

映射与匹配自动机

正如您可能已经注意到的，MooreAutomaton 的输入和输出都是整数。在某些情况下，这已经足够了，但通常我们需要发送 TInput 类型的输入并接收 TOutput 类型的输出。

此功能由 MappedAutomaton 和 MatchAutomaton 类提供。例如，我们可以映射示例 2 中 FSA 的输出。

OutputMappedAutomaton<string> mapped = new OutputMappedAutomaton<string>(moore) {
	OutputMap = {
		{0, " SPACE "},
		{1, " WORD "},
		{2, " ERROR "},
	}
};
mapped.Reset(); 	// remember to reset the machine if it is a wrapper 
		// to a machine which might be used before!
for (int i = 0; i < length; i++)
	Console.Write(mapped.SendAndMap(s[i]));

输出

  WORD  WORD  WORD  SPACE  WORD  WORD  SPACE  ERROR  ERROR  ERROR

一个匹配（有没有更好的名字？）自动机使用 Converter<TInput, TOutput> 委托将外部输入映射到内部输入，并将内部输出映射到外部输出。

MatchAutomaton<byte, string> mapped = new MatchAutomaton<byte, string>(moore) {
	OutputMatch = output => string.Format(" q{0} ", output),
	InputMatch = input => (int)input
};

事件驱动自动机

事件自动机极其有用，因为它会记住其最近的历史记录并触发通知任何变化的事件。

EventedAutomaton evented = new EventedAutomaton(moore);
evented.OutputChanged += delegate (object sender, FsaEventArgs e) {
	// of course an enumeration should be used here to avoid "magic numbers"
	if (e.PreviousOutput == 1) {
		StringBuilder build = new StringBuilder();
		foreach (int c in e.Automaton.OutputInput) {
			build.Append((char) c);
		}
		Console.WriteLine("Word: {0}", build);
	}
};
evented.StateChanged += delegate(object sender, FsaEventArgs e) {
	Console.WriteLine("Transition: q{0} -> q{1}", e.State, e.CurrentState);
};

输出

Transition: q0 -> q1
Word: abc
Transition: q1 -> q0
Transition: q0 -> q1
Word: de
Transition: q1 -> q0
Transition: q0 -> q2

异步执行

FiniteStateAutomaton abstract 类提供了一些很好的特性。例如，它支持 FSA 的异步执行。

来自 IniFile.cs 文件的示例

void OpenAsync(Stream stream)
{
	Pipe outputPipe = new Pipe();
	IAsyncResult asyncResult = mooreAutomaton.RunAsync(new RunParameters {
		Input = stream,
		Output = outputPipe
	});

然而，我们不能责怪 RunAsync 方法本身（它是一个非常简单的东西），IniFile.cs 中的代码非常慢。必须找到一个更好的线程同步问题的解决方案。请随时在下面的留言板中留下评论和建议。

关注点

关于 Mealy FSA

摩尔（Moore）和米利（Mealy）FSA 的区别在于输出符号的位置。在摩尔机中，它们作为状态定义的一部分存储。另一方面，米利机中的输出被分配给转换。这种方法可以大大减少状态数量并提高性能，但每次转换消耗的内存是以前的两倍。示例 2 可以定义为下面的米利机：

Graph 3.

MealyAutomaton mealy = new MealyAutomaton(new MealyState[] {
	new MealyState {
		Table = new MealyAsciiTableGenerator {
			EmptyTransition = new MealySymbol { Output = 2, State = 1 },
			Expressions = {
			    { @"\s", new MealySymbol { Output = 0, State = 0 } },
			    { @"\w", new MealySymbol { Output = 1, State = 0 } }
			}
		}.GenerateTable()
	},
	new MealyState {
		Table = new MealyAsciiTableGenerator {
			EmptyTransition = new MealySymbol { Output = 2, State = 1 }
		}.GenerateTable()
	}
}
	);

我们还可以使用 ToMealy 转换方法，它以 O(n3) 的复杂度完成所有优化。

MealyAutomaton mealy = moore.ToMealy();

关于 MealyAsciiTableGenerator 类：这里不需要特殊的实现。MealyAsciiTableGenerator 类的定义如下：

// to make life easier and don't need to put everywhere those nasty < > brackets
public class MealyAsciiTableGenerator : AsciiTableGenerator<MealySymbol>

{
}

输出显然是相同的：1110110222。

性能比较

一个简单的测试带来了可预测的结果（Pentium Quad 2.4, Vista Business）

Generate: 00:00:03.0150000 // 1000 keys and 1000 values
Save to a file: 00:00:00.6060000

Parsing

Classic: 00:00:01.9270000		(100%)  // the IniFileLight from my another article
Mealy automaton: 00:00:00.8690000	(45,1%) // fewer transitions
Moore automaton: 00:00:02.3850000	(123,77%)// fairly comparable with classic parsing
Parsing automaton: 00:00:06.6780000	(346,55%)// regex at run-time
Asynchronous Moore automaton: 00:00:09.2800000 (481,58%)    // need to be improved
Fast Moore: 00:00:00.8860000	(45,98%)// ASCII-only, but hey not only for parsing

奖励内容

我给你们一些额外的类。

  1. Pipe 是一个面向多线程的内存流。它应该从两个或更多线程读取和写入。Write 和 Read 方法都**阻塞当前线程**，直到能够获取所需数量的数据，或者直到有足够的空间可供写入。它使用一个固定大小的缓冲区，可以在构造函数中定义。关闭流会禁止写入，但数据仍然可以从缓冲区中读取。这可以防止当数据源完成其工作而读取器有自己的缓冲区（例如 StreamReader）时出现永久锁定状态。还支持超时。
  2. RestictedList<T> 是一个派生自 List<T> 的类。它提供了设置项目必须满足的条件才能添加到列表中的可能性。如果用户尝试添加不符合条件的项，则会抛出异常。条件由 Predicate<T> 委托定义。
  3. RestictedDictionary<TKey, TValue> - 类似于 RestrictedList<T> 类。

扩展 FSA 功能

您需要实现 3 个方法来扩展标准 FSA 机器。

public class MyAutomaton : FiniteStateAutomaton
{
	private readonly FiniteStateAutomaton fsa;

	public MyAutomaton(FiniteStateAutomaton fsa)
	{
		this.fsa = fsa;
	}

	// add fields and properties which make up your automaton.

	public override void Reset()
	{
		// Reset the current state of your machine (not a whole structure!)
		fsa.Reset();
	}
	public override int Send(int input)
	{
		// Write your code here
		int output = fsa.Send(input);
		// and probably here as well
		return output;
	}
	public override FiniteStateAutomaton ShallowCopy()
	{
		MyAutomaton copy = new MyAutomaton(fsa.ShallowCopy());
		// do a shallow copy of all new fields.
		return copy;
	}
}

摘要

在本文中，我试图证明FSA系统并非像人们认为的那样过时。我相信在某些情况下，FSA甚至可以作为一种设计模式来使用。通过精心设计的自动机，可以创建一个快速而健壮的系统。由于每个自动机都可以以图形形式呈现，因此关于FSA晦涩难懂的说法是错误的。即使图形丢失了，只需稍加努力，我们就可以开发一个生成此类图形的软件，或者只是拿一张纸进行一次漂亮的创作。由于其通用性，像未调查的案例这样的错误可以迅速发现，甚至无需人工干预。

我希望我能成功地很好地更新了 FSA 技术，使其重新回到开发者身边。祝您绘图愉快！

待办事项

  1. 提高异步操作的性能
  2. 为 MatchAutomaton 找到一个更好的名称
  3. 一如既往，追查 bug（目前为止一切顺利）

历史

  • 2009年1月31日：第一版发布
  • 2009年2月3日：文章更新
© . All rights reserved.