连续扫描流缓冲区中字符串的最佳方法

我有这种情况,我的function不断接收各种长度的数据。 数据可以是任何东西。 我想找到我在这个数据中寻找特定字符串的最佳方法。 该解决方案将需要以某种方式缓冲以前的数据,但我无法解决问题。

以下是问题的示例:

DATA IN – > [\ x00 \ x00 \ x01 \ x23B] [] [LABLABLABLABLA \ x01TO] [KEN] [BLA \ x01] …

如果每个[…]代表一个数据块而[]代表一个没有项目的数据块,那么扫描字符串TOKEN的最佳方法是什么?

更新:我意识到这个问题有点复杂。 []不是分隔符。 我只是用它们来描述上面例子中的块的结构。 此外,TOKEN不是静态字符串。 它是可变长度的。 我认为逐行读取的最佳方法是问题是如何将可变长度的流缓冲区读入行。

对不起,我投票删除了我以前的答案,因为我对这个问题的理解不正确。 我没有仔细阅读enouogh并认为[]是令牌分隔符。

对于您的问题,我建议基于一个简单的计数器构建一个小型状态机:对于每个字符,您执行以下伪代码:

if (received_character == token[pos]) { ++pos; if (pos >= token_length) { token_received = 1; } } else { pos = 0; // Startover } 

这需要最少的处理器周期和最小的内存,因为除了刚收到的块之外你不需要缓冲任何东西。

搜索TOKEN最简单的方法是:

  • 尝试从流中的位置0开始匹配“TOKEN”
  • 尝试从流中的位置1开始匹配“TOKEN”
  • 等等

所以你需要缓冲的是来自流的一些字节,等于“TOKEN”的长度(5个字节,或者实际上是4个字节)。 在每个位置尝试匹配“TOKEN”,这可能需要等待,直到您的缓冲区中至少读取了5个字节。 如果匹配失败,请回退到您开始匹配的位置,再加上一个。 因为你永远不会倒回超过你正在搜索的字符串的长度(减去一个),这就是你真正需要的所有缓冲区。

那么技术问题是,当您从流中连续读取时,如何维护5字节的缓冲数据。 一种方法是所谓的“循环缓冲”。 另一种方法,特别是如果令牌很小,是使用更大的缓冲区,每当你接近结束时,将你需要的字节复制到开头并重新开始。

如果你的函数是一个回调,为每个新的数据块调用一次,那么你将需要保持从一个调用到下一个调用的某种状态,以允许跨越两个块的匹配。 如果你很幸运,那么你的回调API包含一个“用户数据指针”,你可以设置它指向你喜欢的包含缓冲区的任何结构。 如果没有,您将需要全局或线程局部变量。

如果流具有高数据速率,那么您可能需要考虑使用KMP算法或其他方式加快速度。

如果针包含在内存中,可以假设您可以分配一个大小相同的对象来读入(例如char input_array[needle_size]; )。

要开始搜索过程,请用文件中的字节填充该对象(例如size_t sz = fread(input_array, 1, input_size, input_file); )并尝试匹配(例如if (sz == needle_size && memcmp(input_array, needle, needle_size) == 0) { /* matched */ }

如果匹配失败或者您希望在成功匹配后继续搜索,请将位置向前推进一个字节(例如memmove(input_array, input_array + 1, input_size - 1); input_array[input_size - 1] = fgetc(input_file);以及再试一次。

有人担心这个想法会在评论中复制太多字节。 虽然我不认为这种关注具有重要的价值(因为没有重要价值的证据),但可以通过使用圆形arrays来避免副本; 我们在pos % needle_size处插入新字符,并比较该边界之前和之后的区域,就好像它们分别是尾部和头部一样。 例如:

 void find_match(FILE *input_file, char const *needle, size_t needle_size) { char input_array[needle_size]; size_t sz = fread(input_array, 1, needle_size, input_file); if (sz != needle_size) { // No matches possible return; } setvbuf(input_file, NULL, _IOFBF, BUFSIZ); unsigned long long pos = 0; for (;;) { size_t cursor = pos % needle_size; int tail_compare = memcmp(input_array, needle + needle_size - cursor, cursor), head_compare = memcmp(input_array + cursor, needle, needle_size - cursor); if (head_compare == 0 && tail_compare == 0) { printf("Match found at offset %llu\n", pos); } int c = fgetc(input_file); if (c == EOF) { break; } input_array[cursor] = c; pos++; } }