在http://www-igm.univ-mlv.fr/~lecroq/string/上对大量字符串搜索算法进行了广泛的讨论,并附有说明性的 C 代码和参考资料。
一组评论中有关于算法成本的讨论。要记住的一点是,如果您可以通过多次调用搜索函数来分摊设置成本,那么高性能算法可以为您带来巨大的好处。如果您要一直搜索不同的字符串,则更难胜出。
我有一个版本的 KMP (Knuth-Morris-Pratt) 算法打包用于多次重用相同的搜索字符串。标题是:
/*
@(#)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()
等完成的环境中工作,并且您必须能够按需切换内存分配器。你可以忽略这两个 typedef 和对应的函数;当然,默认设置是使用malloc()
和free()
。
基本的 KMP 算法代码来自上面的站点 - 但经过修改以允许我设置一次搜索字符串,然后搜索多个目标字符串等。请联系我(请参阅我的个人资料)以获取源代码。我也有类似的 Boyer-Moore 代码结构(相同的原始来源),以及不区分大小写的 Boyer-Moore 代码。
strstr()
在 Kernighan 和 Pike 的优秀著作《编程实践》中有一个很好的战争故事和表演。
我做了一些实验——使用 King James Bible (4.8 MB) 的副本作为纯文本,并对其进行内存映射。对于许多搜索,(MacOS X 10.6.2 / BSD)strstr()
比 KMP 或 BM 都快。当字符串变得足够长(大约 12+ 个字符)时,BM 算法最终超过了strstr()
. KMP 算法似乎总是慢得多。
德?
- 很难超越一个好的图书馆。
- 在似是而非的英语语言字符串上,KMP 比 BM 慢得多。
而且我围绕算法设置的基础设施可能过于繁重 - 但原始代码中的替代方案是回调机制,它为确定匹配的上下文带来了一些问题。