NFA表示的数据结构

Question

NFA表示的数据结构

data-structuresnfa

3

在我的词法分析器生成器中，我使用McNaughton和Yamada算法进行NFA构建，其中转换从I到J标记为J位置的字符。

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

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

- S.J.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tom Anderson · Accepted Answer

我的理解是，您想对图进行编码，其中节点是状态，边是转换，每条边都带有一个字符标签。是这样吗？

最简单的方法是为每个状态创建一个对象，并在该对象中使用某些小结构来编码转换。

最简单的方法是使用按字符代码索引的数组：这是最快的方法，但不自然地节省空间。您可以通过使用一种截断数组的偏移量来使其更加空间高效：仅存储包含转换的数组部分以及该部分的起始和结束索引。在其中查找字符时，请检查其代码是否在范围内；如果不是，则将其视为空边（或返回起始状态等边），如果是，则获取索引处的元素（字符代码-起始）。

更复杂的选项是使用小哈希表，这将更紧凑但略慢。我建议使用闭合哈希，因为冲突列表将使用太多内存；线性探测应该足够。您可以研究使用完美哈希（查询它），它需要很长时间来生成表格，但然后提供无冲突的查询。生成过程非常复杂。

聪明的方法是同时使用数组和哈希表，并根据边的数量选择其中之一：如果压缩数组超过三分之一，则使用它，否则使用哈希表。

现在，您可以执行的一些更激进的操作是使用数组，但要重叠它们-如果它们是稀疏的，则会有很多空洞，如果聪明，您可以将它们排列在一起，以便每个数组中的条目与其他数组中的空洞对齐。这将为您提供快速查找和优秀的内存效率。您需要一些方案来区分查找是否找到了某些内容以及是否找到了具有某些其他状态转换的空插槽，但我相信您可以想到一些方法。