Обширное обсуждение большого количества алгоритмов поиска строк приведено по адресу http://www -igm.univ-mlv.fr / ~ lecroq / string / , с иллюстративным кодом C и ссылками.
В одном наборе комментариев обсуждается стоимость алгоритмов.Один из моментов, на которые следует обратить внимание, заключается в том, что если вы можете амортизировать стоимость установки по многим вызовам функции поиска, то высокопроизводительные алгоритмы могут дать вам огромное преимущество.Если вы все время будете искать разные строки, выиграть будет сложнее.
У меня есть версия алгоритма KMP (Кнут-Моррис-Пратт), упакованная для многократного повторного использованията же строка поиска.Заголовок:
/*
@(#)File: $RCSfile: kmp.h,v $
@(#)Version: $Revision: 1.4 $
@(#)Last changed: $Date: 2008/02/02 05:49:34 $
@(#)Purpose: Knuth-Morris-Pratt Search Algorithm
@(#)Author: J Leffler
@(#)Copyright: (C) JLSS 2005,2008
@(#)Product: :PRODUCT:
*/
#ifndef KMP_H
#define KMP_H
#include <stddef.h> /* size_t */
typedef struct kmp_control kmp_control;
/*
** To set up a search (to repeatedly look for the same search string in
** multiple scan strings), use kmp_setsearch(). To start a search on a
** new scan string, use kmp_settarget(). To find the next match of a
** given search string in a given target string, use kmp_search(). Note
** that kmp_setsearch() and kmp_settarget() do not copy the data in the
** source and target strings; the pointers must remain valid You can
** copy kmp_control structures for reuse if desired.
*/
typedef void *(*kmp_malloc)(size_t nbytes);
typedef void (*kmp_free)(void *data);
extern kmp_control *kmp_setsearch(const char *search, size_t schlen);
extern void kmp_settarget(kmp_control *ctrl, const char *target, size_t tgtlen);
extern const char *kmp_search(kmp_control *ctrl);
extern void kmp_release(kmp_control *ctrl);
extern void kmp_setalloc(kmp_malloc mem_alloc, kmp_free mem_free);
#endif /* KMP_H */
Возможность задавать функции выделения памяти немного необычна - но мой код часто работает в среде, где выделение памяти не выполняется через стандартный malloc() и т. Д., ИВы должны иметь возможность переключать распределитель памяти по требованию.Вы можете игнорировать две typedefs и соответствующую функцию;настройки по умолчанию, конечно, для использования malloc() и free().
Основной код алгоритма KMP пришел с сайта выше - но был изменен, чтобы я мог задать строку поиска один раз, а затем искатьнесколько целевых строк и т. д. Свяжитесь со мной (см. мой профиль) для получения исходного кода.У меня есть похожая структура и для кода Бойера-Мура (тот же исходный код), а также без учета регистра кода Бойера-Мура.
Есть хорошая военная история о strstr() и производительности в Кернигане и Пайке.Отличная книга " Практика программирования ".
Я провел несколько экспериментов - использовал копию Библии короля Иакова (4,8 МБ) в качестве простого текста и отображение памяти, которое,Для многих поисков (MacOS X 10.6.2 / BSD) strstr() был быстрее, чем KMP или BM.Когда строки росли достаточно долго (примерно 12+ символов), тогда алгоритм BM, наконец, опередил strstr().Алгоритм KMP всегда казался намного медленнее.
Мораль?
- Трудно превзойти хорошую библиотеку.
- KMP намного медленнее, чем BM, для правдоподобных строк на английском языке.
И инфраструктура, которую я создал для алгоритмов, может быть слишком тяжелой, но альтернативой в исходном коде является механизм обратного вызова, который представляетнекоторые проблемы для определения контекста совпадений.