C++ 中在无限二元流中查找模式 I

在无限二元流中查找模式是计算机科学和数据处理中的基本概念。它涉及在可能无限延续的、潜在无界二元数据流中搜索特定二元数字序列。

在许多实际应用中，数据会持续到来，例如网络流量监控、传感器数据分析或金融市场数据处理。在这些场景中，有效检测传入数据流中的模式或异常至关重要。

此问题的挑战在于处理数据流的无限性，同时仍能确定给定模式是否在其中出现。由于一次性存储或处理整个无限流不可行，因此必须设计能够增量式工作的算法，在数据到达时或以可管理的数据块进行处理。

可以采用各种技术来应对这一挑战。一种常见的方法是使用滑动窗口算法，该算法一次检查数据流的固定大小窗口，将窗口沿着流移动以检查与模式的匹配情况。其他方法涉及概率数据结构、哈希或有限自动机。

用于在无限流中进行模式匹配的高效算法对于实时数据分析、监控和众多领域的决策至关重要。它们需要仔细考虑计算复杂性、内存使用以及处理连续数据输入而不中断的能力。

方法-1：滑动窗口

滑动窗口算法是一种在二元流中有效搜索模式的技术。在许多实际场景中，例如数据分析、网络数据包检查或信号处理，我们经常会遇到需要在连续二元数据流中识别特定模式出现的情况。

考虑一个场景，我们有一个无限的二元流，表示为 0 和 1 的序列，我们想在该流中查找特定模式的出现次数。例如，我们可能对检测流中的“101”等序列感兴趣。挑战在于在搜索模式出现的同时高效处理这个潜在的无限流。

程序

输出

Pattern found at indices: 0 4 8 10 12 14 16 20 24 26 28 30 32 36 38 40 42 44 46

说明

• 头文件包含

代码包含必要的头文件，如 <iostream>、<string> 和 <vector>。这些头文件分别用于输入/输出操作、字符串操作和向量容器使用。

• 命名空间声明

using namespace std; 语句允许访问标准命名空间中的实体，通过避免显式命名空间限定来简化代码可读性。

• 函数定义：findPatternInBinaryStream

此函数接受两个参数：binaryStream（表示要搜索的二元流）和 pattern（表示要在流中查找的模式）。它返回一个整数向量 (vector<int>)，其中包含模式在流中出现的位置索引。

该函数使用循环遍历二元流，从索引 0 开始，到 streamSize - patternSize 结束，以确保检查整个流。在循环中，它会检查当前索引开始的模式是否可能匹配。

如果找到匹配项，则将出现位置的索引添加到 occurrences 向量中。最后，该函数返回包含模式在二元流中所有出现位置索引的occurrences 向量。

• 主函数

main 函数作为程序的入口点。它初始化要搜索的二元流（binary stream）和模式（pattern）。它调用 findPatternInBinaryStream 函数，并将二元流和模式作为参数传递，将结果存储在 result 向量中。根据结果，它将打印模式的出现索引或一条消息，指示模式未在流中找到。

• 执行

执行时，程序将搜索二元流中模式的出现情况。如果找到一个或多个出现项，它将打印找到模式的索引。如果流中未找到模式，它将打印一条消息，指示未找到模式。

此代码提供了滑动窗口算法在二元流中进行模式匹配的直接实现。它高效地处理流并识别指定模式的出现，展示了字符串匹配和数据分析应用中使用的基本技术。

复杂度分析

时间复杂度

滑动窗口算法的时间复杂度由在二元流中检查模式所需的比较次数决定。

外循环

外层循环遍历整个二元流，从索引 0 到 streamSize - patternSize。此循环运行 n-m+1 次，其中 n 是二元流的大小，m 是模式的大小。因此，外层循环的时间复杂度为O(n-m+1)，当 m 远小于 n 时，等同于O(n)。

内层循环

内层循环将二元流中当前窗口中的模式的每个字符与相应字符进行比较。循环遍历模式，模式的大小为 m。

因此，内层循环的时间复杂度为O(m)。结合外层和内层循环的时间复杂度，滑动窗口算法的总时间复杂度为O(n⋅m)。

这是因为，在最坏的情况下，模式的每个字符都需要与二元流中每个窗口中的每个字符进行比较。

空间复杂度

滑动窗口算法的空间复杂度主要由存储二元流中模式出现次数所需的附加空间决定。

出现次数向量

occurrences 向量存储模式在二元流中出现的位置索引。在最坏的情况下，流的所有索引可能都是模式的出现。因此，occurrences 向量的空间复杂度为O(n)，其中 n 是二元流的大小。

附加空间

除了 occurrences 向量外，该算法还使用恒定的附加空间用于变量和临时存储。因此，附加空间复杂度为 O(1)。

方法-2：有限自动机方法

在无限二元流中查找模式的有限自动机方法涉及构建一个表示要搜索模式的有限自动机。在此方法中，二元流被增量式处理，根据传入的二元数字转换自动机。当自动机到达接受状态时，表示整个模式已匹配，并记录模式的出现。

有限自动机是计算模型，由状态和基于输入符号的状态之间的转换组成。通过构建表示模式的自动机，模式匹配过程变得确定且高效。此方法特别适用于模式固定且预先已知的场景。

有限自动机的构建涉及将模式映射到一组状态和转换。每个状态代表到目前为止已达到的模式的部分匹配，状态之间的转换对应于基于流中的下一个二元数字扩展模式的可能性。一个或多个状态被指定为接受状态，表示整个模式已匹配。

程序

输出

Pattern found at position 3
Pattern found at position 3

说明

有限自动机类

• 构建

FiniteAutomaton 类表示用于模式匹配的有限自动机。它以模式作为输入，并根据模式构建自动机。

• 转移表

自动机的转换存储在转移表中，实现为二维向量。表中的每一行代表一个状态，每一列代表一个可能的二元数字（0 或 1）。转换值指示根据当前状态和输入数字要转换到的下一个状态。

• 接受状态

自动机会将一个或多个状态指定为接受状态，表示模式已完全匹配。isAccepting 向量跟踪哪些状态是接受状态。

• 处理下一个数字

processNextDigit 方法将流中的下一个二元数字作为输入，并相应地更新自动机的状态。它根据当前状态和输入数字，遵循转移表中定义的转换，转换到下一个状态。

如果自动机到达接受状态，则表示整个模式已匹配，并记录了出现项。

主函数

• 模式匹配

在 main 函数中，指定了要搜索的二元流和模式。调用 findPatternInBinaryStream 函数，使用有限自动机在流中搜索模式的出现。

实现细节

• 效率

有限自动机方法提供了高效的模式匹配，其时间复杂度与二元流和模式的大小成线性关系。处理流中的每个二元数字涉及恒定时间操作，这使得该方法非常适合大型流。

• 确定性操作

自动机以确定性方式运行，这意味着从一个状态到另一个状态的转换由当前状态和输入数字唯一确定。这种确定性行为确保了可预测且高效的模式匹配，而无需回溯。

在处理二元流的过程中，自动机会根据传入的二元数字在状态之间进行转换。如果找到有效的转换，自动机会移动到相应的下一个状态。当到达接受状态时，会在流中的当前位置记录模式。

复杂度分析

时间复杂度

构建有限自动机

构建有限自动机涉及根据模式初始化转移表和确定接受状态。此过程需要遍历模式，时间复杂度为O(m)，其中 m 是模式的大小。

处理二元流

处理流中的每个二元数字涉及恒定的操作次数，主要包括访问转移表和更新当前状态。由于流中有 n 个数字，其中 n 是流的大小，因此处理整个流的时间复杂度为 O(n)。结合有限自动机的构建和二元流的处理，有限自动机方法的总时间复杂度为O(m+n)。

这种线性时间复杂度使得该方法对于大型二元流和模式非常高效。

空间复杂度

转移表

转移表存储状态之间的转换，所需空间与状态数和字母表大小（二元数字）成比例。在最坏的情况下，有m+1 个状态（其中 m 是模式的大小），每个状态都有针对两个二元数字的转换。因此，转移表空间复杂度为O(2m) 或 O(m)。

接受状态

isAccepting 向量存储有关哪些状态是接受状态的信息。由于有 m+1 个状态，此向量的空间复杂度为 O(m)。

附加空间

其他变量，例如自动机的当前状态，需要恒定空间。因此，附加空间复杂度为O(1)。结合转移表、接受状态和附加变量所需的空间，有限自动机方法的总空间复杂度为O(m)。

方法-3：使用 Z 算法

Z 算法是一种线性时间模式匹配算法，它预处理模式以创建“Z 数组”，然后有效地在二元流中搜索匹配项。它特别适用于较大的模式，并且提供高效的模式搜索，时间复杂度为O(n+m)，其中 n 是流的大小，m 是模式的大小。

程序

输出

Pattern found at index 0
Pattern found at index 14

说明

• Z 数组构建

constructZArray 函数负责为给定模式构建 Z 数组。Z 数组或 Z 函数存储从模式中每个位置开始与模式前缀匹配的最长子串的长度。该算法遍历模式中的每个位置 i，并确定该位置的匹配长度。

如果 i 超出当前 Z 区域（即 i>R），则从 i 开始进行字符比较，直到发生不匹配或到达模式末尾。匹配长度存储在Z[i]中，并相应更新 Z 区域边界 L 和 R。

如果 i 在当前 Z 区域内，则计算来自先前Z 区域的相应值。如果计算值不超过当前 Z 区域的右边界，则将其直接赋给 Z[i]。否则，从 R 开始进行字符比较，直到发生不匹配或到达模式末尾，并相应更新Z[i]。

• 在二元流中搜索匹配项

searchPatternInBinaryStream 函数采用构建的 Z 数组，扫描二元流以查找模式的出现。它遍历流中的每个位置 i，并通过比较字符来检查从 i 开始的子串是否与模式匹配。如果找到匹配项，则打印出现的索引。

复杂度分析

时间复杂度

Z 数组构建

构建 Z 数组需要遍历模式中的每个位置并比较字符。此过程需要 O(m) 时间，其中 m 是模式的大小。

在二元流中搜索匹配项

扫描二元流以进行匹配涉及遍历每个位置并将字符与模式进行比较。此过程需要 O(n⋅m) 时间，其中 n 是流的大小，m 是模式的大小。

Z 算法的最终时间复杂度为 O(m+n⋅m)，但由于对于较大的模式，m 通常小于 n，因此通常简化为O(n+m)。

空间复杂度

Z 数组

Z 数组需要与模式 m 的大小成比例的空间。因此，其空间复杂度为O(m)。

附加空间

算法中使用的附加空间与模式和流的大小相比可忽略不计。它主要包括用于迭代和比较的变量，这些变量需要恒定空间。因此，空间复杂度为O(1)。

结合 Z 数组和附加变量所需的空间，Z 算法的总空间复杂度为O(m+1)，简化为O(m)。