用于在string中search子string的快速algorithm

我想要一个高效的algorithm(或库),我可以在Java中使用来searchstring中的子string。

我想要做的是:

给定一个inputstring – INSTR

“BCDEFGH”

和一组候选string – CAND

“AB”,“CDE”,“FG”,“H”,“IJ”

find与INSTR内的子string匹配的任何CANDstring

在这个例子中,我会匹配“CDE”,“FG”和“H”(但不是“AB”和“IJ”)

可能有数千个候选string(在CAND中),但更重要的是,我将这样search数百万次,所以我需要它是快速的。

我想使用char数组。 另外,我并没有将其构build成解决scheme,比如分发search – 只是本地最有效的function/algorithm。

此外,CAND和INSTR中的所有string都将相对较小(<50个字符) – 即目标stringINSTR相对候选string不长。


更新我应该提到,CANDstring的集合在INSTR的所有值中都是不变的。

更新我只需要知道有一场比赛 – 我不需要知道比赛是什么。

最终更新由于实施简单,我select尝试AhoCorsick和Rabin-Karp。 因为我有可变长度模式,所以我使用了一个修改过的Rabin-Karp来散列每个模式的前n个字符,其中n是最小模式的长度,那么N就是我的滚动子stringsearch窗口的长度。 对于Aho Corsick,我使用了这个

在我的testing中,我search了两个文档新闻文章中的1000个模式,平均1000次迭代等…规范化的时间完成:

AhoCorsick :1

拉宾卡普 :1.8

天真的search (检查每个模式和使用string.contains):50


*一些资源描述在以下答案中提到的algos:

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html

http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2×2.pdf

http://www-igm.univ-mlv.fr/~lecroq/string/index.html *

阅读Aho-Corasickalgorithm和Rabin-Karpalgorithm 。

如果input不是很大,你不想多次重复search,也没有多less模式,多次使用单个模式algorithm可能是个好主意。 维基百科关于searchalgorithm的文章给出了运行和预处理时间的许多algorithm。

实现:

介绍:

将候选string集合转换为确定性有限状态自动机,然后在线性时间内运行inputstring。 将单个string转换为DFS已在标准书籍中得到了很好的说明。 您可以通过首先构造一个非确定性自动机然后确定它来转换一组string。 在最坏的情况下,自动机的大小会造成指数性的爆炸,但之后的search速度很快; 特别是如果目标string很长,候选人的短期工作将会很好。

这是正则expression式的用途。 如上所述,有限状态自动机就是你所需要的,但这正是如何实现一个标准的正则expression式匹配器。

在Java中,你可以写如下的东西:

StringBuilder sb = new StringBuilder(); bool first = true; for (String subStr : substrings) { if (first) first = false; else sb.append('|'); sb.append(escape(subStr)); } Pattern p = Pattern.compile(sb.toString()); 

该方法escape应该逃脱在正则expression式中有特殊含义的任何字符。

拉宾 – 卡普多重模式search似乎是最快的。

你可能想看看Aho-Corasickalgorithm和相关的algorithm。 我不知道任何实现这一点的库,但是这是解决这个问题的经典方法。

还要检查Boyer-Moorealgorithm的单串模式匹配。

我们可以利用string的小尺寸(<50个字符)为这种情况build立一个超快速algorithm,代价是内存。

我们可以将所有可能的INSTR子string哈希一次,这将花费O(n ^ 2)时间。 然后,无论CANDstring的数量如何,查找将是O(1)。 值得大量的CANDstring。

如果INSTR很大,那么我们可以build立一个后缀数组而不对其进行sorting,这样顶部项目是最长的(= N),最下面的项目是INSTR的最后一个字符。 现在对于每个CANDstring,只要从顶部search长度(CAND)<=长度(后缀)即可。 每个比较将是O(n)。

另一个解决scheme是为INSTR使用后缀数组 。
由于INSTR很小,可以使用冒泡sorting来sorting。

之后,您可以在O(logN)时间内search特定的CANDstring,
其中N =长度(suffix_array)=长度(INSTR)。

这里是一些Java中的快速stringsearchalgorithm的实现。

 import java.util.Scanner; public class StringMatch { static int temp,i=0,j=0; static boolean flag=true,matcher=false; static String str=null,mstr=null;static char astr[],amstr[]; static void getter(){ Scanner sc = new Scanner(System.in); str = sc.nextLine(); //String str="today is Monday"; astr=str.toCharArray(); mstr = sc.nextLine(); //String mstr="is"; amstr=mstr.toCharArray(); } static void stringMatch(){ while(i<astr.length){ if(astr[i]==amstr[j]){ while((j!=amstr.length)&&flag){temp=i; if(astr[i]!=amstr[j]) {flag=false;matcher=false;} else{matcher=true;} i++;j++; //System.out.println(i+"\t"+j); }if(matcher==true)break;i=temp;}i++;j=0;flag=true; } if(matcher==true) {System.out.println("true");} else {System.out.println("false");} } public static void main(String[] args) { StringMatch.getter(); StringMatch.stringMatch(); } }