11

我目前正在研究扫描仪生成器。生成器已经可以正常工作了。但是当使用字符类时，算法变得非常慢。

扫描仪生成器为 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[] 的辅助函数定义为：

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

5 回答 5

3

有很多方法可以处理它。它们都归结为在数据结构中一次处理一组字符，而不是枚举整个字母表。这也是您在合理的内存量中制作 Unicode 扫描仪的方式。

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

于 2010-08-24T16:04:35.790 回答
3

我将澄清我认为您要求的内容：合并一组 Unicode 代码点，以便您生成状态最小的 DFA，其中转换表示这些代码点的 UTF8 编码序列。

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

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

为此，我们需要一个从 Unicode 码点到它们对应的 UTF8 编码的映射。无需预先存储所有这些 UTF8 字节序列；它们可以即时编码。UTF8 编码算法有据可查，这里不再赘述。

Aho-Corasick 的工作原理是首先构建一个trie。在您的情况下，这将是依次添加的每个 UTF8 序列的尝试。然后根据算法的其余部分，用转换将其转换为 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 字符类。在这里您可以看到以下代码：

其他方法（如该问题的其他答案中所述）包括处理代码点和表示代码点范围，而不是拼出每个字节序列。

[1] Myhill-Nerode: Nerode, Anil (1958), Linear Automaton Transformations , Proceedings of the AMS, 9, JSTOR 2033204
[2] Hopcroft & Ullman (1979), Section 3.4, Theorem 3.10, p.67
[3] Aho ，阿尔弗雷德五世；Corasick, Margaret J.（1975 年 6 月）。高效的字符串匹配：书目搜索的辅助。ACM 的通信。18 (6): 333–340。

于 2019-12-11T20:23:28.630 回答
2

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

于 2010-08-22T20:03:34.393 回答
0

我的扫描仪生成器遇到了同样的问题，所以我想出了用间隔​​树确定的 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
于 2013-05-16T08:04:04.463 回答
0

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

它非常紧凑，但它增加了每一步的代码复杂性。

于 2016-07-23T21:31:22.683 回答