并行与分布式系统中的并行正则表达式匹配：基于位置自动机（Glushkov自动机）的并行构造与匹配算法
字数 4622 2025-12-18 13:05:02

并行与分布式系统中的并行正则表达式匹配：基于位置自动机（Glushkov自动机）的并行构造与匹配算法

1. 问题描述

正则表达式匹配是文本处理、编译器、网络安全等领域的基础操作。给定一个正则表达式 \(R\) 和一个文本串 \(T\)，我们需要判断 \(T\) 中是否存在子串能被 \(R\) 匹配，并通常要求找出所有匹配位置。在并行与分布式环境中，挑战在于如何高效地将正则表达式编译为可并行执行的数据结构（如自动机），以及如何并行地对文本进行匹配。本算法聚焦于一种称为 Glushkov自动机（位置自动机） 的结构，它因其性质适合并行构造和并行匹配。我们将探讨如何并行地构建Glushkov自动机，以及如何利用该自动机对文本进行并行匹配。

2. 背景与基础知识

首先，明确几个概念：

  • 正则表达式（RE）: 由基本符号（字母）和操作符（连接 ·、并集 |、克林闭包 *）递归定义的表达式。例如，(a|b)*ab 匹配所有以 ab 结尾的由 a 和 b 组成的串。
  • 非确定性有限自动机（NFA）: 一种状态机，从初始状态出发，对于输入符号可能进入多个下一状态。正则表达式可以等价转换为NFA。
  • Glushkov自动机（位置自动机）: 一种特殊的NFA，其特点如下：
    1. 所有状态（除初始状态）与正则表达式中的符号出现（位置）一一对应。例如，表达式 (a|b)*ab 有三个符号位置：a₁（第一个a）、b₂、a₃、b₄（假设我们为每个符号分配唯一索引）。
    2. 初始状态 q₀ 没有对应的符号。
    3. 转移函数定义清晰：从状态 q₀ 到位置 p 的转移，当且仅当 p 是表达式的“首符号”；从位置 p 到位置 s 的转移，当且仅当 s 是 p 的“后继符号”。
    4. 终止状态是那些对应“尾符号”的位置。
      这种结构避免了“ε-转移”（空转移），简化了并行处理。

3. 算法步骤详解

3.1 串行算法回顾
为了理解并行化，先回顾串行构建Glushkov自动机的关键步骤，它们都依赖于对正则表达式语法树的遍历：

  1. 标记（Indexing）: 为语法树中每个叶子节点（基本符号）分配唯一的整数位置。
  2. 计算函数:
    • First(R): 返回表达式R能推导出的所有串的第一个符号的位置集合。
    • Last(R): 返回表达式R能推导出的所有串的最后一个符号的位置集合。
    • Follow(R, i): 对于位置i，返回在R中紧跟在i之后可能出现的所有符号的位置集合。
    • Nullable(R): 判断R是否可能生成空串（ε）。
  3. 构建自动机:
    • 状态集合: {q₀} ∪ {所有位置}。
    • 初始状态: q₀。
    • 从q₀到每个位置p ∈ First(R) 添加转移，输入符号为位置p对应的字符。
    • 对于每个位置i，到每个位置j ∈ Follow(R, i) 添加转移，输入符号为位置j对应的字符。
    • 终止状态: 所有位置p ∈ Last(R)，以及如果Nullable(R)为真，则q₀也是终止状态。

3.2 并行化策略

并行化的核心思想是利用正则表达式语法树的递归结构，将计算 First、Last、Nullable、Follow 的任务分配给不同的处理器，并最终合并结果。

步骤一：并行语法树构建与标记

  • 输入: 正则表达式字符串。
  • 过程:
    1. 将表达式解析成语法树。这一步通常是串行的，但表达式很长时，可以并行解析子表达式，然后合并成树。
    2. 并行标记: 对语法树进行后序遍历。由于后序遍历中，一个节点的计算依赖于其子节点的结果（标记范围），我们可以为每个子树分配一个处理器或线程。每个处理器负责遍历其分配的子树，为叶子节点分配局部唯一的位置ID，并记录该子树的“位置范围”（起始ID和结束ID）。根节点的处理器负责协调，确保所有子树的ID全局唯一且连续。这可以通过前缀和（Prefix Sum）操作高效完成：每个子树报告自己的叶子节点数量，根节点计算全局偏移量，然后各子树根据偏移量调整自己的局部ID。

步骤二：并行计算 Nullable, First, Last

  • 目标: 为语法树中每个节点计算这三个函数的值。
  • 过程:
    • 这是一个典型的树形动态规划问题。每个节点的 Nullable、First、Last 仅依赖于其直接子节点的值。
    • 我们可以对语法树进行后序遍历。与标记过程类似，将树划分为若干子树，分配给不同处理器。每个处理器并行地计算其负责子树内所有节点的 Nullable（布尔值）、First 和 Last（位集合，bitset）。集合的合并操作（并集）可以并行且高效地完成。
    • 最终，根节点的 Nullable(R)、First(R)、Last(R) 被计算出来。

步骤三：并行计算 Follow

  • 挑战: Follow(i) 的计算比 First/Last 更复杂，因为它涉及语法树中非直接父子关系的节点。但Glushkov的原始方法提供了一种基于树遍历的公式。
  • 关键观察: 对于语法树中的操作节点（连接 ·、并集 |、闭包 *），Follow 关系可以在局部确定：
    • (A|B): Follow 集不变。
    • (A·B): Follow 集增加：对于所有 i ∈ Last(A)，Follow(i) 需要并入 First(B)。
    • (A*): Follow 集增加：对于所有 i ∈ Last(A)，Follow(i) 需要并入 First(A)。
  • 并行过程:
    1. 初始化: 为每个位置i创建一个空的 Follow(i) 集合。
    2. 并行树遍历（自顶向下或自底向上合并）:
      • 我们可以再次使用后序遍历。当处理器处理一个节点时（如连接节点 A·B），它已经知道了子节点A和B的 First 和 Last 集。
      • 根据上述规则，它生成一组 (i, S) 对，表示需要将集合S合并到 Follow(i) 中。例如，对于连接节点，生成 (i, First(B)) 对，其中 i 遍历 Last(A)。
      • 这些更新对可以收集起来。由于不同子树产生的更新可能涉及相同的位置 i，我们需要一个合并阶段。
    3. 并行合并更新: 所有处理器产生的 (i, S) 对可以看作一个列表。我们可以根据位置 i 作为键，并行地进行归约（Reduce） 操作。例如，使用并行哈希表或基于排序的归约：首先根据 i 并行排序所有对，然后并行遍历排序后的列表，将具有相同 i 的集合S合并，最终得到每个位置 i 的完整 Follow(i) 集。

步骤四：并行构建自动机转移表

  • 输入: First(R), Last(R), 所有 Follow(i)，以及位置到字符的映射。
  • 过程:
    1. 初始转移: 从 q₀ 出发的转移。这很简单：为 First(R) 中的每个位置 p 创建一个转移 (q₀, sym(p), p)。First(R) 是一个集合，可以并行地为每个 p 创建转移。
    2. 状态间转移: 对于每个位置 i 和 Follow(i) 中的每个位置 j，创建一个转移 (i, sym(j), j)。这是一个典型的嵌套并行模式：外层循环遍历所有位置 i（并行），内层循环遍历 Follow(i) 中的每个 j（并行）。转移的创建是独立的，可以完全并行化。
    3. 终止状态标记: 将 Last(R) 中的所有位置标记为终止状态，如果 Nullable(R) 为真，也将 q₀ 标记为终止。这也是并行的集合操作。

步骤五：并行文本匹配
Glushkov自动机是NFA，但无ε转移。并行匹配的关键是模拟NFA的并行执行。

  • 算法（并行NFA模拟）:
    1. 初始化: 当前活跃状态集合 S = {q₀}（如果 Nullable(R) 为真，则 q₀ 是活跃的）。
    2. 并行处理文本位置: 将输入文本 T 划分为连续的块，分配给不同的处理器。
    3. 块内处理（核心）:
      • 每个处理器负责一段文本 T[start...end]。
      • 从共享的当前活跃状态集合 S 开始（对于第一个块，S 是初始集合；对于后续块，S 是前一个块处理结束时的活跃状态集合）。
      • 处理器顺序（或进一步并行地）处理自己块内的每个字符 c_k：
        a. 并行状态转移: 对于当前活跃集合 S 中的每个状态 q（可以并行处理），查找所有以 c_k 为输入符号从 q 出发的转移，得到一组下一状态 Next_q。
        b. 并行集合合并: 将所有 Next_q 集合进行并集操作，得到处理字符 c_k 后的新活跃状态集合 S_new。这个并集操作可以并行化（例如，使用并行归约）。
        c. 用 S_new 更新 S，继续处理下一个字符。
      • 块处理结束时，该处理器得到自己块末尾的活跃状态集合 S_end。
    4. 块间同步与传递:
      • 由于NFA的活跃状态集在字符间传递，处理器必须按顺序处理块。因此，这是一个数据并行（每个块内并行模拟）与流水线结合的模式。
      • 处理器 P_i 将其 S_end 传递给处理器 P_{i+1}，作为处理下一个文本块的初始活跃状态集。
    5. 匹配检测: 在处理任何字符后（或块结束时），如果当前活跃状态集合 S 中包含任何终止状态，则发现了一个匹配。匹配位置等信息可以被记录。

4. 算法复杂度与优势

  • 构建复杂度:
    • 串行: O(|R|^2) 主要来自计算 Follow 集（最坏情况）。
    • 并行: 理想情况下，在 p 个处理器上，树形计算和归并操作可以将构建时间降低到 O((|R|^2)/p + log p)，但通信和同步开销需考虑。
  • 匹配复杂度:
    • 串行模拟: O(|T| * |S|)，其中 |S| 是活跃状态集大小，最坏情况为 O(|R|)。
    • 并行模拟: 每个文本块的处理时间理论上可减少为 O((|T|/p) * (|S|/p_inside))，其中 p_inside 是块内用于并行状态转移的线程数。但块间有顺序依赖。
  • 优势:
    1. 无ε转移: 简化了并行模拟的逻辑，状态转移只依赖于输入字符。
    2. 规整的结构: 状态与位置对应，First、Last、Follow 集合的计算具有很好的并行递归性。
    3. 匹配可并行性: 虽然活跃状态集需要顺序传递，但每个字符处的状态转移计算（从多个活跃状态出发）可以并行化，这对于宽自动机（|R|大）尤其有效。

5. 总结

基于Glushkov自动机的并行正则表达式匹配算法，通过将正则表达式语法树的计算任务（标记、函数计算）并行化，构建出一个适合并行匹配的自动机。在匹配阶段，它利用数据划分和块内并行状态转移模拟，加速了对长文本的匹配过程。该算法展示了如何将形式语言理论与并行计算模式结合，解决一类重要的模式匹配问题。其性能在实践中依赖于正则表达式的复杂度和并行架构的特性。

并行与分布式系统中的并行正则表达式匹配：基于位置自动机（Glushkov自动机）的并行构造与匹配算法 1. 问题描述 正则表达式匹配是文本处理、编译器、网络安全等领域的基础操作。给定一个正则表达式 \( R \) 和一个文本串 \( T \)，我们需要判断 \( T \) 中是否存在子串能被 \( R \) 匹配，并通常要求找出所有匹配位置。在并行与分布式环境中，挑战在于如何高效地将正则表达式编译为可并行执行的数据结构（如自动机），以及如何并行地对文本进行匹配。本算法聚焦于一种称为 Glushkov自动机（位置自动机） 的结构，它因其性质适合并行构造和并行匹配。我们将探讨如何并行地构建Glushkov自动机，以及如何利用该自动机对文本进行并行匹配。 2. 背景与基础知识 首先，明确几个概念： 正则表达式（RE） : 由基本符号（字母）和操作符（连接 · 、并集 | 、克林闭包 * ）递归定义的表达式。例如， (a|b)*ab 匹配所有以 ab 结尾的由 a 和 b 组成的串。 非确定性有限自动机（NFA） : 一种状态机，从初始状态出发，对于输入符号可能进入多个下一状态。正则表达式可以等价转换为NFA。 Glushkov自动机（位置自动机） : 一种特殊的NFA，其特点如下： 所有状态（除初始状态）与正则表达式中的 符号出现（位置） 一一对应。例如，表达式 (a|b)*ab 有三个符号位置： a₁ （第一个a）、 b₂ 、 a₃ 、 b₄ （假设我们为每个符号分配唯一索引）。 初始状态 q₀ 没有对应的符号。 转移函数定义清晰：从状态 q₀ 到位置 p 的转移，当且仅当 p 是表达式的“首符号”；从位置 p 到位置 s 的转移，当且仅当 s 是 p 的“后继符号”。 终止状态是那些对应“尾符号”的位置。 这种结构避免了“ε-转移”（空转移），简化了并行处理。 3. 算法步骤详解 3.1 串行算法回顾 为了理解并行化，先回顾串行构建Glushkov自动机的关键步骤，它们都依赖于对正则表达式语法树的遍历： 标记（Indexing） : 为语法树中每个叶子节点（基本符号）分配唯一的整数位置。 计算函数 : First(R) : 返回表达式R能推导出的所有串的第一个符号的位置集合。 Last(R) : 返回表达式R能推导出的所有串的最后一个符号的位置集合。 Follow(R, i) : 对于位置i，返回在R中紧跟在i之后可能出现的所有符号的位置集合。 Nullable(R) : 判断R是否可能生成空串（ε）。 构建自动机 : 状态集合: {q₀} ∪ {所有位置}。 初始状态: q₀。 从q₀到每个位置p ∈ First(R) 添加转移，输入符号为位置p对应的字符。 对于每个位置i，到每个位置j ∈ Follow(R, i) 添加转移，输入符号为位置j对应的字符。 终止状态: 所有位置p ∈ Last(R)，以及如果Nullable(R)为真，则q₀也是终止状态。 3.2 并行化策略 并行化的核心思想是利用正则表达式语法树的 递归结构 ，将计算 First 、 Last 、 Nullable 、 Follow 的任务分配给不同的处理器，并最终合并结果。 步骤一：并行语法树构建与标记 输入 : 正则表达式字符串。 过程 : 将表达式解析成语法树。这一步通常是串行的，但表达式很长时，可以并行解析子表达式，然后合并成树。 并行标记 : 对语法树进行 后序遍历 。由于后序遍历中，一个节点的计算依赖于其子节点的结果（标记范围），我们可以为每个子树分配一个处理器或线程。每个处理器负责遍历其分配的子树，为叶子节点分配 局部唯一 的位置ID，并记录该子树的“位置范围”（起始ID和结束ID）。根节点的处理器负责协调，确保所有子树的ID全局唯一且连续。这可以通过前缀和（Prefix Sum）操作高效完成：每个子树报告自己的叶子节点数量，根节点计算全局偏移量，然后各子树根据偏移量调整自己的局部ID。 步骤二：并行计算 Nullable, First, Last 目标 : 为语法树中每个节点计算这三个函数的值。 过程 : 这是一个典型的 树形动态规划 问题。每个节点的 Nullable 、 First 、 Last 仅依赖于其直接子节点的值。 我们可以对语法树进行 后序遍历 。与标记过程类似，将树划分为若干子树，分配给不同处理器。每个处理器并行地计算其负责子树内所有节点的 Nullable （布尔值）、 First 和 Last （位集合，bitset）。集合的合并操作（并集）可以并行且高效地完成。 最终，根节点的 Nullable(R) 、 First(R) 、 Last(R) 被计算出来。 步骤三：并行计算 Follow 挑战 : Follow(i) 的计算比 First/Last 更复杂，因为它涉及语法树中非直接父子关系的节点。但Glushkov的原始方法提供了一种基于树遍历的公式。 关键观察 : 对于语法树中的操作节点（连接 · 、并集 | 、闭包 * ）， Follow 关系可以在局部确定： (A|B) : Follow 集不变。 (A·B) : Follow 集增加：对于所有 i ∈ Last(A) ， Follow(i) 需要并入 First(B) 。 (A*) : Follow 集增加：对于所有 i ∈ Last(A) ， Follow(i) 需要并入 First(A) 。 并行过程 : 初始化: 为每个位置i创建一个空的 Follow(i) 集合。 并行树遍历（自顶向下或自底向上合并） : 我们可以再次使用后序遍历。当处理器处理一个节点时（如连接节点 A·B ），它已经知道了子节点A和B的 First 和 Last 集。 根据上述规则，它生成一组 (i, S) 对，表示需要将集合S合并到 Follow(i) 中。例如，对于连接节点，生成 (i, First(B)) 对，其中 i 遍历 Last(A) 。 这些更新对可以收集起来。由于不同子树产生的更新可能涉及相同的位置 i ，我们需要一个合并阶段。 并行合并更新 : 所有处理器产生的 (i, S) 对可以看作一个列表。我们可以根据位置 i 作为键， 并行地进行归约（Reduce） 操作。例如，使用并行哈希表或基于排序的归约：首先根据 i 并行排序所有对，然后并行遍历排序后的列表，将具有相同 i 的集合S合并，最终得到每个位置 i 的完整 Follow(i) 集。 步骤四：并行构建自动机转移表 输入 : First(R) , Last(R) , 所有 Follow(i) ，以及位置到字符的映射。 过程 : 初始转移 : 从 q₀ 出发的转移。这很简单：为 First(R) 中的每个位置 p 创建一个转移 (q₀, sym(p), p) 。 First(R) 是一个集合，可以并行地为每个 p 创建转移。 状态间转移 : 对于每个位置 i 和 Follow(i) 中的每个位置 j ，创建一个转移 (i, sym(j), j) 。这是一个典型的 嵌套并行 模式：外层循环遍历所有位置 i （并行），内层循环遍历 Follow(i) 中的每个 j （并行）。转移的创建是独立的，可以完全并行化。 终止状态标记 : 将 Last(R) 中的所有位置标记为终止状态，如果 Nullable(R) 为真，也将 q₀ 标记为终止。这也是并行的集合操作。 步骤五：并行文本匹配 Glushkov自动机是NFA，但无ε转移。并行匹配的关键是 模拟NFA的并行执行 。 算法（并行NFA模拟） : 初始化 : 当前活跃状态集合 S = {q₀} （如果 Nullable(R) 为真，则 q₀ 是活跃的）。 并行处理文本位置 : 将输入文本 T 划分为连续的块，分配给不同的处理器。 块内处理（核心） : 每个处理器负责一段文本 T[start...end] 。 从 共享的当前活跃状态集合 S 开始（对于第一个块， S 是初始集合；对于后续块， S 是前一个块处理结束时的活跃状态集合）。 处理器顺序（或进一步并行地）处理自己块内的每个字符 c_k ： a. 并行状态转移 : 对于当前活跃集合 S 中的 每个状态 q （可以并行处理），查找所有以 c_k 为输入符号从 q 出发的转移，得到一组下一状态 Next_q 。 b. 并行集合合并 : 将所有 Next_q 集合进行 并集 操作，得到处理字符 c_k 后的新活跃状态集合 S_new 。这个并集操作可以并行化（例如，使用并行归约）。 c. 用 S_new 更新 S ，继续处理下一个字符。 块处理结束时，该处理器得到自己块末尾的活跃状态集合 S_end 。 块间同步与传递 : 由于NFA的活跃状态集在字符间传递，处理器必须按顺序处理块。因此，这是一个 数据并行（每个块内并行模拟）与流水线结合 的模式。 处理器 P_i 将其 S_end 传递给处理器 P_{i+1} ，作为处理下一个文本块的初始活跃状态集。 匹配检测 : 在处理任何字符后（或块结束时），如果当前活跃状态集合 S 中包含任何终止状态，则发现了一个匹配。匹配位置等信息可以被记录。 4. 算法复杂度与优势 构建复杂度 : 串行: O(|R|^2) 主要来自计算 Follow 集（最坏情况）。 并行: 理想情况下，在 p 个处理器上，树形计算和归并操作可以将构建时间降低到 O((|R|^2)/p + log p) ，但通信和同步开销需考虑。 匹配复杂度 : 串行模拟: O(|T| * |S|) ，其中 |S| 是活跃状态集大小，最坏情况为 O(|R|) 。 并行模拟: 每个文本块的处理时间理论上可减少为 O((|T|/p) * (|S|/p_inside)) ，其中 p_inside 是块内用于并行状态转移的线程数。但块间有顺序依赖。 优势 : 无ε转移 : 简化了并行模拟的逻辑，状态转移只依赖于输入字符。 规整的结构 : 状态与位置对应， First 、 Last 、 Follow 集合的计算具有很好的并行递归性。 匹配可并行性 : 虽然活跃状态集需要顺序传递，但每个字符处的状态转移计算（从多个活跃状态出发）可以并行化，这对于宽自动机（|R|大）尤其有效。 5. 总结 基于Glushkov自动机的并行正则表达式匹配算法，通过将正则表达式语法树的计算任务（标记、函数计算）并行化，构建出一个适合并行匹配的自动机。在匹配阶段，它利用数据划分和块内并行状态转移模拟，加速了对长文本的匹配过程。该算法展示了如何将形式语言理论与并行计算模式结合，解决一类重要的模式匹配问题。其性能在实践中依赖于正则表达式的复杂度和并行架构的特性。