将字符集转换为NFA / DFA的高效算法

Question

我目前正在开发一个扫描器生成器。

这个生成器已经可以正常工作了，但是当使用字符集时算法会变得非常慢。

该扫描器生成器用于生成UTF8编码文件的扫描器。应支持完整的字符范围（0x000000至0x10ffff）。

如果我使用大型字符集，例如任意操作符“.”或Unicode属性{L}，则nfa（以及dfa）将包含大量状态（> 10000）。因此，从nfa转换为dfa并创建最小dfa需要很长时间（即使输出的最小dfa只包含一些状态）。

以下是我当前实现的创建nfa字符集部分的代码：

void CreateNfaPart(int startStateIndex, int endStateIndex, Set<int> characters)
{
transitions[startStateIndex] = CreateEmptyTransitionsArray();
foreach (int character in characters) {
    // get the utf8 encoded bytes for the character
    byte[] encoded = EncodingHelper.EncodeCharacter(character);
    int tStartStateIndex = startStateIndex;
    for (int i = 0; i < encoded.Length - 1; i++) {
        int tEndStateIndex = transitions[tStartStateIndex][encoded[i]];
        if (tEndStateIndex == -1) {
           tEndStateIndex = CreateState();
               transitions[tEndStateIndex] = CreateEmptyTransitionsArray();
        }                   
        transitions[tStartStateIndex][encoded[i]] = tEndStateIndex;
        tStartStateIndex = tEndStateIndex;
    }
    transitions[tStartStateIndex][encoded[encoded.Length - 1]] = endStateIndex;
}

有人知道如何更高效地实现函数以仅创建必要的状态吗？

编辑：

更具体地说，我需要一个类似于：

List<Set<byte>[]> Convert(Set<int> characters)
{
     ???????
}

定义了一个帮助函数，将字符（int）转换为UTF8编码的字节数组：

byte[] EncodeCharacter(int character)
{ ... }

- raisyn

---

你正在为 byte 输入构建一个xFA？操作（Utf16）字符会不会更容易（更可靠）一些呢？ - H H

我不这样认为，如果使用16位字符，查找表的大小会增加。而且，与UTF-8相比，如果使用UTF-16，典型的输入文件将会更大。 - raisyn

对不起，我误解了！接受任何编码将是未来版本的一个不错的选择。但为了保持简单，我认为只实现一种编码会更容易，而UTF-8看起来是我最合适的选择。 - raisyn

但是我得到了包含所有0x10ffff字符条目的查找表。那么如何实现转换表呢？？？ - raisyn

你需要一种“智能”处理字符集的方式。一个简单的想法是拥有一个1 0..0x10ffff查找表（虽然很大但可行），以便为每个字符找到相应的集合号码。 - H H

你需要使用符号编码来编码你的自动机转换，例如，如Ian所提到的那样，使用边界。也许brics自动机库可以给你一些提示！ - Dan

Answer 1

有很多种处理它的方法。所有这些都归结为在数据结构中一次处理字符集合，而不是枚举整个字母表。这也是如何制作适量内存的Unicode扫描仪的方法。

您可以选择如何表示和处理字符集合。我目前使用的解决方案是保持有序边界条件列表和相应目标状态。您可以比每次都必须扫描整个字母表时更快地处理这些列表上的操作。事实上，它足够快，以至于它可以在Python中以可接受的速度运行。

- Ian

Answer 2

我将澄清您所询问的内容：将一组Unicode代码点联合起来，以便您生成一个状态最小的DFA，其中转换表示这些代码点的UTF8编码序列。

当您说“更有效率”时，这可能适用于运行时间，内存使用情况或最终结果的紧凑性。在有限自动机中，“最小”的通常意义是使用最少的状态描述任何给定语言，这就是您通过“仅创建必要的状态”所得到的。

每个有限自动机都有一个等效的状态最小DFA（参见Myhill-Nerode定理[1]或Hopcroft＆Ullman[2]）。对于您的目的，我们可以直接使用Aho-Corasick算法[3]构建此最小DFA。

为此，我们需要将Unicode代码点映射到它们对应的UTF8编码。没有必要提前存储所有这些UTF8字节序列；它们可以即时编码。UTF8编码算法已经有很好的文档，我不会在这里重复。

Aho-Corasick的工作原理是首先构建一个Trie树。在您的情况下，这将是逐个添加的每个UTF8序列的Trie树。然后，该Trie树使用转换进行注释，以便根据算法的其余部分将其转换为DAG。这里有一个漂亮的算法概述，但我建议阅读论文本身。

此方法的伪代码：

trie = empty
foreach codepoint in input_set:
   bytes[] = utf8_encode(codepoint)
   trie_add_key(bytes)
dfa = add_failure_edges(trie) # per the rest of AC

这种方法（形成UTF8编码序列的trie，然后进行Aho-Corasick，最后渲染出DFA）是我正则表达式和有限状态机库实现中采用的方法，我在其中完全按照此方法构建Unicode字符类。在这里，您可以看到以下代码：

• 对Unicode代码点进行UTF8编码：examples/utf8dfa/main.c

• 构建trie：libre/ac.c

• 为每个字符类呈现最小DFA：libre/class/

其他方法（如本问题的其他答案中提到的）包括使用码点并表达码点范围，而不是拼写出每个字节序列。

[1] Myhill-Nerode: Nerode，Anil（1958年），Linear Automaton Transformations，AMS会议论文集，9，JSTOR 2033204
[2] Hopcroft&Ullman（1979年），第3.4节，定理3.10，第67页
[3] Aho，Alfred V .; Corasick，Margaret J.（1975年6月）。 Efficient string matching: An aid to bibliographic search。 ACM通讯。 18（6）：333-340。

- Kate F

---

如果这是一个初学者问题，我很抱歉。上面的伪代码中我们真的需要添加失败边吗？我的意思是，我们不需要在输入字符字节中搜索从某个地方开始的子字符串：一旦字节无法遵循 trie，则我们知道输入字节不属于该字符类。我错过了什么吗？ - awllower

Answer 3

看看像Google RE2和TRE这样的正则表达式库在做什么。

- jilles

---

我认为Google RE2可以做我需要的事情，但它非常复杂... 我在http://code.google.com/p/re2/source/browse/re2/compile.cc（从第559行开始）找到了一些有趣的代码。 - raisyn

Answer 4

我在扫描器生成器中遇到了同样的问题，所以我想到了用区间树确定它们的ID来替换区间的想法。例如，在DFA中表示a..z范围可以表示为：97、98、99、...、122，而我将范围表示为[97, 122]，然后构建区间树结构，最终它们被表示为引用区间树的ID。给定以下RE：a..z+，我们最终得到这样的DFA：

0 -> a -> 1
0 -> b -> 1
0 -> c -> 1
0 -> ... -> 1
0 -> z -> 1

1 -> a -> 1
1 -> b -> 1
1 -> c -> 1
1 -> ... -> 1
1 -> z -> 1
1 -> E -> ACCEPT

现在压缩区间：

0 -> a..z -> 1

1 -> a..z -> 1
1 -> E -> ACCEPT

从DFA中提取所有间隔，并构建间隔树：

{
    "left": null,
    "middle": {
        id: 0,
        interval: [a, z],
    },
    "right": null
}

将实际时间间隔替换为它们的ID：

0 -> 0 -> 1
1 -> 0 -> 1
1 -> E -> ACCEPT

- Ruslan

Answer 5

在这个库（http://mtimmerm.github.io/dfalex/）中，我通过在每个转换上放置一系列连续字符而不是单个字符来实现。这在NFA构造、NFA->DFA转换、DFA最小化和优化的所有步骤中都有体现。

它非常紧凑，但会增加每个步骤的代码复杂度。

- Matt Timmermans

Answer 6

我的https://metacpan.org/pod/Unicode::SetAutomaton模块实现了这一点。请注意，正则表达式或自动机通常会多次重复大型集合，例如\w+\W+\w+[\w\d]*有三个（如果将\W视为补集，则为四个）\w的实例，如果\w的DFA很大，则可能不希望制作多个副本。因此，我的模块将Unicode标量值集合划分为每个标量值属于一个分区，然后计算DFA，其中每个接受状态对应于这样的分区。您可以使用DFA将输入字节转换为分区，然后定义在这些分区上的高级转换，在高级自动机中节省大量空间。

- Björn Höhrmann