实际上，如何在函数中计算自动机然后返回它？-解网

问：

我正在尝试关注，第 3 版。具体来说，第七章，32“字符串匹配”。总的来说，我发现这本书非常难以理解，因为大量的数学口语和过于理论化而不是实践性。这就是为什么我只在我目前感兴趣的算法上有选择地访问它。Cormen - Algorithms

我一直很好地遵循字符串章节。这并不容易，但我设法获得了蛮力和快速哈希算法中的大部分内容......然而，第二部分，让我有点抓紧空气。我在自动机理论方面的背景几乎为零，但我仍然设法掌握了算法的概念。然而，有一件事对我来说是深不可测的：

好的，所以这里的一切似乎都很明显。Automaton 根据先前的状态和文本中的字符更改状态，方法是将其传递到过渡函数中。但是等等......这个转换函数到底是什么？好吧，这里是：qsmall delta

好吧，现在，在这里，甚至不太明显发生了什么。但我最大的问题不是理解这个特定的伪代码是如何工作的。我无法理解这个过程的实用性。怎么可能在运行时在另一个函数中生成函数，然后像某种变量一样返回它，以便调用函数可以执行它？

谁能给我指导我需要了解哪些基本的东西才能获得它的实用方面？也许您可以给出一些简短而简单的描述，说明如何实际实现？

目前，我唯一的猜测是虚拟机......从理论上讲，您可以在函数中生成一系列 VM 指令，然后执行它们，是的......但是 VM 的开销很高，这违背了快速字符串匹配的整个目的......

另一种可能的方法，尽管有点疯狂，是在运行时直接在函数内部生成本机机器代码指令。然后，将它们写入分配有权限的内存区域，然后返回指向此函数的指针。然后，调用代码可以像调用任何其他硬编码函数一样调用该函数。不过，我不知道这是否可行或可行。PAGE_EXECUTE

算法字符串匹配自动机

enum State {
    Q1,
    Q2
};
enum State delta(enum State q, char c) {
    switch (q) {
        case Q1:
            switch (c) {
                case 'a': return Q1;
                case 'b': return Q2;
            }
        case Q2:
            switch (c) {
                case 'a': return Q2;
                case 'b': return Q2;
            }
    }
}

此交换机树对 delta（Q1， a） = Q1， delta（Q1， b） = Q2， delta（Q2， a） = Q2， delta（Q2， b） = Q2 进行编码。它省略了 not in {a， b} 或 q not in {Q1， Q2} 的情况。defaultc

出于性能原因，解析器生成器在实践中通常会生成这样的代码 - 实际函数。请注意，这发生在编译时，而不是运行时。

怎么可能在运行时在另一个函数中生成函数，然后像某种变量一样返回它，以便调用函数可以执行它？

如果函数的代码在“编译时”已经存在，则称为闭包：函数的代码不会更改，只有上下文会更改。上下文中的这些变量（实际上是父作用域的局部变量）称为上值。创建一个闭包实际上只是分配一个包含这些上值的隐式和一个函数指针;粗略地说，调用闭包会调用函数指针，传递函数指针，以便闭包可以访问其上值。structstruct

当然，这个闭包只是一个指向结构或类似结构的指针，可以自由地传递。能够将函数视为值 - 从而实现完全动态调度 - 使函数成为一流的。

一流的闭包是 lambda 演算和函数式编程的基础。许多脚本语言也采用了一流的闭包。下面是 Lua 中一个标准的“咖喱加法”示例：

function adder(a)
    return function(b)
        return a + b
    end
end
add1 = adder(1)
add2 = adder(2)
print(add1(41)) -- 42
print(add2(40)) -- 42

上一个：对我的 Javascript 搜索引擎项目的反馈。打印未全部接受结果，未显示错误 [已关闭]

下一个：了解 KMP 模式匹配算法中的特定细节

实际上，如何在函数中计算自动机然后返回它？

How is it practically possible to compute an automaton inside a function and then return it?

评论