data-structures - NFA 表示的数据结构

Question

在我的词法分析器生成器中，我使用 McNaughton 和 Yamada 算法构建 NFA，它的属性之一是从 I 转换为 J，在 J 位置用 char 标记。

因此，NFA 的每个节点都可以简单地表示为下一个可能状态的列表。

哪种数据结构最适合存储此类数据？它必须为所有可能的状态提供快速查找并使用更少的空间，但插入时间并不那么重要。

Answer 1

我的理解是你想编码一个图，其中节点是状态，边是转换，每条边都标有一个字符。那是对的吗？

枯燥但实用的答案是每个状态都有一个对象，并在该对象的一些小结构中编码转换。

最简单的一个是一个数组，由字符代码索引：这是尽可能快的，但自然不节省空间。您可以通过使用一种偏移量截断数组来提高空间效率：仅存储数组中包含转换的部分，以及该部分的开始和结束索引。在其中查找字符时，检查其代码是否在边界内；如果不是，则将其视为空边（或返回到开始状态的边或其他），如果是，则获取索引处的元素（字符代码 - 开始）。那有意义吗？

一个更复杂的选择是一个小哈希表，它会更紧凑但稍微慢一些。我建议关闭散列，因为冲突列表会占用太多内存；线性探测应该足够了。您可以考虑使用完美散列（查找），这需要花费大量时间来生成表，但随后会提供无冲突查找。但是，生成过程相当复杂。

一个聪明的方法是同时使用数组和哈希表，并根据边的数量选择一个或另一个：如果压缩数组超过三分之一，则使用它，但如果不是，则使用哈希表.

现在，你可以做的更激进的事情是使用数组，但要重叠它们 - 如果它们是稀疏的，它们会有很多洞，如果你很聪明，你可以安排它们，以便每个数组中的条目与其他数组中的孔对齐。这将为您提供快速查找，同时也提供出色的内存效率。您将需要一些方案来区分查找何时找到某物与何时找到一个带有其他状态转换的空槽，但我相信您能想到一些东西。