c - 如何用C实现多关键字搜索？

Question

我想实现一个不区分大小写的文本搜索，支持多个关键字的并行测试。我已经能够以一种在我看来在性能方面似乎效率不高的方式实现这一目标。

函数“strcasestr”( Link to Linux man page )在搜索一个关键字时似乎做得很好，但是当您想同时测试多个关键字时 - 根据我的理解 - 您想要迭代文本的字符( Haystack)仅一次找到出现的关键字(Needles)。

多次使用“strcasestr”会导致 - 我的理解 - 对文本(Haystack)进行多次迭代，这可能不是最快的解决方案。一个例子:

#define _GNU_SOURCE
#include <stdio.h>
#include <string.h>

int main (void) {

  // Text to search in
  char *str = "This is a test!";

  char *result = strcasestr(str, "not_found1");

  if (result == NULL) {
    result = strcasestr(str, "NOT_FOUND2");
  }

  if (result == NULL) {
    result = strcasestr(str, "TEST!");
  }

  printf("Result pointer: %s\n", result );

  return 0;
}

是否有一种方法可以比我更快地获取文本中某个(不区分大小写)关键字第一次出现的位置？

如果解决方案是可扩展的，以便我可以继续循环文本以查找关键字出现的所有位置，我将不胜感激，因为我正在进行全文搜索具有结果评级系统。也非常欢迎将我引向正确方向的框架和小提示。

Answer 1

经过长时间的学习和测试，我找到了一个适合我的解决方案。我测试了它的单关键字版本，其性能与函数“strcasestr”相当(使用约 500 MB 的文本进行测试)。

解释以下代码的作用:

首先定义文本(Haystack)和关键字(Needles)。然后关键字已经转换为小写以获得良好的性能。 iter 是一个数字数组，反射(reflect)当前文本进度与每个关键字匹配的字符数。该程序线性迭代文本的每个字符，直到找到其中一个关键字的匹配项 - 在这种情况下，程序结束并且结果为“True”。如果未找到匹配项 (=0)，则结果为“False”。

我欢迎在评论中提出建议，以获得更好的代码质量或更高的性能。

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main (void) {

  int i, j;
  int match = 0;

  // Haystack
  char *text = "This is a test!";

  // Needles
  int keywords_len = 3;
  char keywords[][12] = {
    "not_found1",
    "NOT_FOUND2",
    "TEST!"
  };

  // Make needles lowercase
  for (i = 0; i < keywords_len; i++)
    for (j = 0; keywords[i][j]; j++)
      keywords[i][j] = tolower(keywords[i][j]);

  // Define counters for keywords matches
  int iter[] = { 0, 0, 0 };

  // Loop over all characters and test match
  char ptext;
  while (ptext = *text++)
    // Compare matches
    // NOTE: (x | 32) means case-insensitive
    if (!match)
      for (i = 0; i < keywords_len; i++)
        if ((ptext | 32) == keywords[i][iter[i]]) {
          if (keywords[i][++(iter[i])] == '\0') {
            match = 1;
            break;
          }
        } else
          iter[i] = 0;
    else
      break;

  printf("Result: %s\n", match ? "True" : "False");

  return 0;
}