1

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

这是问题的一个例子：

数据输入 -> [\x00\x00\x01\x23B][][LABLABLABLABLA\x01TO][KEN][BLA\x01]...

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

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

4

3 回答 3

2

搜索 TOKEN 的最简单方法是：

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

因此，您需要缓冲的只是流中等于“TOKEN”长度的字节数（5 个字节，或者实际上是 4 个字节）。在每个位置尝试匹配“TOKEN”，这可能需要等到您至少有 5 个字节读入缓冲区。如果匹配失败，倒回到你开始匹配的地方，加一。由于您不会倒带超过您正在搜索的字符串的长度（减一），这就是您真正需要的所有缓冲区。

那么技术问题是，当您从流中连续读取时，如何维护 5 字节的缓冲数据。一种方式是所谓的“循环缓冲区”。另一种方法，尤其是在令牌很小的情况下，是使用更大的缓冲区，并且每当您离结尾太近时，将所需的字节复制到开头并重新开始。

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

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

于 2013-01-28T15:54:58.180 回答
0

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

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

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

这需要最少的处理器周期和最少的内存，因此您不需要缓冲除了刚刚收到的块之外的任何内容。

于 2013-01-28T16:10:43.207 回答
-1

如果指针包含在内存中，则可以假设您可以分配一个相同大小的对象来读取（例如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);，再试一次。

在评论中提出了一个担忧，即这个想法复制了太多字节。虽然我不认为这种担忧有很大的好处（因为没有证据表明有重要价值），但可以通过使用循环数组来避免复制；我们在该边界之前和之后插入新字符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++;
    }
}
于 2015-09-15T07:30:47.190 回答