通用 .NET DFA 状态机

• 下载 ver 1.2 源代码文件 - 25 Kb
• .NET 可调用 Dot.dll - 526kb (您唯一需要额外的文件)

引言

我将用两张图表来解释，而不是进行计算机科学 101 的讲解。简而言之，DFA 是确定性有限自动机的缩写。它的近亲是 NFA，即非确定性有限自动机。NFA 的一个例子是遍历一个大列表来查找一个单词。这个单词可能很快被找到，也可能只在最后一个条目中找到。这就是所谓的非确定性。因此，对于 DFA，我们可以确切地知道搜索一个单词（如 NFA 示例所示）需要多长时间。

数据样本

"原始"数据（无特定顺序），准备进行 NFA 处理（您知道的懒人方法）。

TABLE A

leppie can swim 
leppie can talk 
leppie looks good 
leppie looks left 
leppie goes home 
john looks fine 
john can walk 
john wants nothing 
leppie wants food 
leppie can code 
leppie can code C 
leppie can code C# 
leppie can code C# well 
leppie can code C++ poorly 
leppie lives in stellenbosch 
leppie lives with a flatmate 
leppie drinks plenty coke 
leppie drinks coffee 
leppie eats many hotdogs 
leppie eats food 
leppie knows alot 
leppie knows alot about code 
leppie knows a little about girls 
john can swim 
john can talk too

TABLE B

stop
stopper
stood
step
standard
stank
stance
authors
automatic
back
back's
backed
background
backing
backing's
backs
backwards
bad
badly
balance
balance's
ball
ball's
chain
chain's
chair
chair's
chairman
chairman's
chance
chance's
chances
change
changed
changes
changing
channel
channel's
channels
chaos
chaos's
chapter
chapter's
char
charge
charged
charges
fall
fallen
falling
falls
false
familiar
family
family's
famous
fan
fan's
fancy
far
farm

表 A 的 DFA 表示。一个带有外圈的圆圈表示终止状态。

表 B 的 DFA 表示。一个带有外圈的圆圈表示终止状态。

您可能会问 System.Object 在这里做什么，它什么也没做。更新：我已将根对象从生成的图中移除。正如您所见，它不是一个终止状态，所以它不会影响任何东西。但它确实有一个用途。它充当第一个创建的节点，无论键的类型是什么。我可以删除它，但我必须每次都检查 null，这会太慢。所以不用担心！

基本实现：AtomicState

public class AtomicState
{
	protected AtomicState();
	protected AtomicState(object key);
	protected bool Accepts(Array stack);
	public Array AcceptStates(Array stack);
	protected bool Add(Array stack);
	public AtomicState GetAtomicStateAt(Array stack);
	protected Array Match(Array stack);
	protected bool Remove(Array stack);
	internal protected virtual void RenderStateNodeAttributes attr);
	internal protected virtual void RenderTransistion(EdgeAttributes attr);
	public override string ToString();
	public int AcceptStateCount { get; }
	public int TotalStateCount { get; }
	protected object key;
}

DFA 状态机的基本实现。我提供了几种类型的安全实现，包括 Int32、String、Char、Boolean、Float、Object 和 Type。随时添加您自己的实现，并查看代码中的注释。数组的数组存在糟糕的类型转换问题。我还包含了一个我很久以前创建但一直没有地方放的 Combination 类。Combinations 非常适合构建 DFA。还包含了一个实用程序类，用于生成所有这些漂亮的图片（是的，这是直接写给你的，Marc Clifton ;P），您可以在此处看到（您需要 GraphViz）。更新：GraphViz 实用程序已大大改进，并且如上所示，您现在可以在状态级别指定渲染选项。实现类似于 ASP.NET 的自定义控件渲染。换句话说，如果您需要更改内容，只需重写 RenderXXX。TypeState 的实现是一个很好的例子。

该类主要包含人类无法理解的代码（几乎每个函数要么在一个 while(true) 循环中运行，要么是递归的）。这主要是一个为计算机科学项目开发的 C 项目的通用端口。从两个计数函数的代码中，您会看到“多维链表”可以通过递归轻松“遍历”（我遇到了一些堆栈问题，但无法重现）。

目的

那么您可能会问，为什么或如何使用它？该机器的设置方式是一次采取一个“路径”，因此添加一个句子或一个单词会自动在该机器中布局。不需要其他干预。最困难的事情之一是将 NFA 转换为 DFA，这一切都已为您完成。然后您只需要查询它。像 Match() 这样的函数在处理“通配符”（将它们设置为 null，请参阅实现）时可能会花费更长的时间。

您现在可能会问我为什么不直接使用 ArrayList 或 HashTable？很简单。ArrayList 适用于批处理数据，但搜索性能差。HashTable 非常适合查找，但对于模式匹配或“路径”查找则不太有用。事实上，在大多数情况下，您应该使用前面提到的任何一种。此技术的有用示例

• 拼写检查器
• 单词/代码补全
• 代码解析器
• 路径查找
• 以及更多人们梦寐以求的东西

性能

与任何 DFA 一样，性能至关重要。此实现的性能与 Hashtable 相当。事实上，如果消除了装箱，查找速度会更快（在我的实验中是 2 倍而不是 3 倍）。这是一个从 500,000 字词列表中加载到 char[] 中的简单控制台输出

提取所有条目
时间：5752.794559ms
CharState 测试从 502069 个条目中进行 10000 次随机查找
时间：133.561947ms
平均时间：0.013356ms
HashTable 测试从 502069 个条目中进行 10000 次随机查找
时间：37.712056ms
平均时间：0.003771ms

正如您所见，查找速度比 Hashtable 慢 3 倍，但请记住，Hashtable 速度极快，但特性不同。注意提取所有条目的缓慢。考虑到 DFA 被再次转换为原始数据，这不算太差。

感谢使用我用于计时目的的 HP 定时器类的作者（抱歉，现在记不起您的名字了）。

演练

举个例子，如果您想快速生成程序集的继承图，您只需这样做

TypeState typeroot = new TypeState();
Type[] types = Assembly.GetAssembly(typeof(AtomicState)).GetTypes();

foreach (Type type in types)
{
   ArrayList arr = new ArrayList();
   Type etype = type;
   do 
   {
      arr.Insert(0, etype);
      etype = etype.BaseType;
   }
   while (etype != null);

   typeroot.Add( (Type[]) arr.ToArray(typeof(Type)));
}
TextWriter writer = File.OpenText("file.dot");
GraphViz.Generate(typeroot, writer);

现在我们得到一个字符串，可以将其传递给 Dot (GraphViz 可执行文件)，结果如下

很漂亮，不是吗？但这甚至不是目的！幸运的是，GraphViz 非常适合，它使更多事情成为可能。如果有人想发送一些网络跟踪日志，我将提供一些渲染图。更新：来啦！我稍微裁剪了图表。

观察

可能会出现这样的问题：“leppie can eat”和“john can eat”为什么会互相连接。这实际上是可能的，但当您添加“leppie can eat meat”时会出现问题。这是否意味着 john 也可以吃肉？这取决于您想要的精度。在我的情况下，我选择了精度。添加此功能只会增加加载时间，并且要使其 100% 准确将需要 NFA 传递或对算法进行重大更改。欢迎提出建议。

结论

希望您喜欢使用此代码，并像往常一样随时发表评论。测试项目基本上只包含我运行过的一些测试，并且可能会在您的系统上引发异常。但可以看看它，了解它是如何使用的。

更新日志

1.1

• GraphViz 工具已完全重做，并在状态级别添加了渲染。可以调整转换（边）和状态（节点）的属性。对于熟悉该产品的人，我将命名尽可能接近 GraphViz 的语法。
• 上传了新版本，包含可用的测试（如您在此处看到的）和图片。

1.2

• 修复了性能 bug。
• 让图片更漂亮了 :)
• 构建了一个可由 .NET 调用 Dot 的 DLL。可以单独下载。编译、链接和解决 MC++ 问题很痛苦，但最终还是成功了。如果您遇到问题，我可以给您一个项目文件，但请注意，它也很混乱。

未来计划

现在，为了让大家反复回来，我列出了一些我未来的计划（可行的建议也会被添加）

• 能够添加状态和转换数据，以获得极致的渲染体验。
• 也许，为 GraphViz 构建一个 .NET 包装器（如果有人能给我一个源代码的解决方案文件，那将不胜感激，因为源代码很混乱）。更新：已构建 DLL，现在是包装器。有一个小的接口可从 .NET 调用。
• 我想也许稍后我可以实现 GDI 渲染。也许，以后。