Как реализовать поиск по нескольким ключевым словам в C?

Question

Я хочу реализовать поиск текста без учета регистра, который поддерживает параллельное тестирование нескольких ключевых слов.Я уже смог достичь этого способом, который мне не кажется эффективным с точки зрения производительности.

Функция "strcasestr" ( Ссылка на справочную страницу Linux ), кажется,хорошо справляться с поиском по одному ключевому слову, но если вы хотите одновременно протестировать несколько ключевых слов - в моем понимании - вы хотите итерировать символы текста (стог сена) только один раз, чтобы найти вхождение ключевых слов (иглы)).

Использование «strcasestr» несколько раз приведет - как я понимаю, - к нескольким итерациям по тексту (стогу сена), что может быть не самым быстрым решением.Пример:

#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 МБ текста).

Чтобы объяснить, что делает следующий код:

Сначала определяются текст (стог сена) и ключевые слова (иглы). Затем ключевые слова уже преобразуются в нижний регистр для хорошей производительности. iter - это массив чисел, которые отражают, сколько символов соответствует текущему текстовому прогрессу для каждого ключевого слова. Программа линейно перебирает каждый символ text , пока не найдет совпадение в одном из ключевых слов - в этом случае программа завершается, и в результате получается «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;
}