您将使用哪种算法在短文本中搜索短子串?简而言之,我的意思是子串为5-10个字符,字符串为255。我正在考虑根据输入数据长度选择算法。对于更长的输入,哪种算法更好?
试试Turbo-BM。但是,IMO用这种短串通常的线性扫描就足够了。
如果您正在寻找比Boyer Moore更好的算法,那么您要求的是一个混合答案。
据我所知,只有后缀树在文本搜索中击败了Boyer Moore。但是,它使用更多时间来创建索引并使用更多磁盘空间。
附加信息:速度方面,后缀树或后缀数组击败任何版本的Boyer Moore,因为后缀树基本上实现了树中所有可能的搜索,如数据结构。
但是,后缀树具有较高的RAM内存成本,并且索引文本较慢(创建树数据结构)。
Boyer Moore与后缀树的速度差异:Boyer Moore在搜索文本上是线性的。后缀树在搜索模式上是线性的。
如果您在200个字符的文本上搜索5个字母的单词,则boyer moore执行200次操作,后缀树执行5次。
无论如何更快,它很难实现。在数据结构的难度规模上,它可能是最难的一个。一旦建成,它可以针对空间和速度进行大幅优化。
这就是说,在未来几年寻找后缀树。通常,后缀树用于DNA索引和web搜索引擎优化。
Boyer Moore无处不在,例如会议程序(文本搜索功能),广泛用于网络搜索引擎。
@anon @Anton Gogolev 用一个词来回答你的问题:Railgun_Quadruplet
这个C函数在短2,3,4个模式和160个字符的字符串上进行了如此严格的测试,在这个表http://www.sanmayce.com/Railgun/index.html#Heavy-Search-Hustle上你可以自己决定。
还有一篇文章:http://www.codeproject.com/KB/cpp/Railgun_Quadruplet.aspx
你可以尝试Suffix Trees或Suffix Arrays。两者都取决于模式长度。
我认为Boyer-Moore-Horspool可以通过这种变化更快(我不知道它的名字,也许我的名字:-))。 BMH的算法不使用匹配的字符和不匹配的字符信息。它仅使用当前模式位置中的最后一个文本字符。例如:
在BMH中,下一个位置是(C与下一个C对齐):
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
如果我们使用匹配的字符,则下一个位置是(BC与下一个BC对齐):
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
如果我们使用匹配的字符和不匹配的字符,则下一个位置是(BC与下一个BC对齐,但由于与A不匹配的模式字符与下一个BC的前一个字符相同,它也将不匹配。由于没有其他BC,跳过是模式长度):
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
这是Java实现(仍然可以改进),使用风险因为我没有彻底测试过。在我的表现测试中,Boyer-Moore-Horspool仍然击败了这个实现。但正如预期的那样,如果模式被重用(两者都没有模式预处理),那么这个实现就会获胜。
public static int[] processPattern1(char[] pattern) {
int[] skip = new int[256];
for (int i = 0; i < skip.length; ++i) {
skip[i] = pattern.length;
}
for (int i = 0; i < pattern.length - 1; ++i) {
skip[pattern[i]] = pattern.length - i - 1;
}
return skip;
}
public static int[] processPattern2(char[] pattern) {
int[] skip = new int[pattern.length];
int i, j, k, x, y;
int lpos = pattern.length - 1;
int l2pos = pattern.length - 2;
OUTER:
for (k = l2pos; k > -1; k--) { // k points to unmatched pattern character
j = k + 1;
for (i = k; i > 0; i--) {
if (pattern[i] == pattern[j] && pattern[i-1] != pattern[k]) {
for (x = i + 1, y = j + 1; y < pattern.length && pattern[x] == pattern[y]; x++, y++) {
}
if (y == pattern.length) {
skip[k] = pattern.length - x;
continue OUTER;
}
}
}
for (x = lpos - j; x > -1; x--) {
if (pattern[x] == pattern[lpos]) {
for (i = x - 1, y = l2pos; i > -1 && pattern[i] == pattern[y]; i--, y--) {
}
if (i == -1) {
skip[k] = lpos - x;
continue OUTER;
}
}
}
skip[k] = pattern.length;
}
return skip;
}
public static int search(char[] text, char[] pattern, int[] skip1, int[] skip2) {
int k = pattern.length - 1;
int i, j;
int lpos = k;
int l2pos = pattern.length - 2;
while (k < text.length) {
if (text[k] == pattern[lpos]) {
for (j = l2pos, i = k - 1; j > -1 && text[i] == pattern[j]; j--, i--) {
}
if (j == -1) {
return i + 1;
}
k += skip2[j];
} else {
k += skip1[text[k]];
}
}
return -1;
}
public static void main(String[] args) {
String origText = "TTTTTTTTTTTTTTTZBCRABCCABCTTTTTTTTTTTTT";
char[] pattern = "ZBCRABCCABC".toCharArray();
char[] text = origText.toCharArray();
int[] skip1 = processPattern1(pattern);
int[] skip2 = processPattern2(pattern);
System.out.println(search(text, pattern, skip1, skip2) == origText.indexOf(pattern));
}
以下是我上面代码的改进。在我的测试中它与BMH的颈部和颈部相同但在某些跑步中会获得相当大的成功(每次跑步是对一个39,650个字符的英文文档的随机位置进行1,000,000次搜索)。
public class BoyerMoore {
int[] tab1 = new int[256];
int[][] tab2 = new int[1000][1001];
int[] tab3 = new int[1000];
public BoyerMoore8() {
for (int i = 0; i < tab1.length; i++) {
tab1[i] = -1;
}
}
public void processPattern(char[] pattern) {
// tab1 structure,
// 0 => tab2 index
// tab2 structure,
// 0 - pattern length - 2 => skip values
// pattern length - 1 => default skip value
// pattern length => pattern position where to start comparing
int i, p;
int lp = pattern.length - 1;
for (i = 0; i < pattern.length; ++i) {
tab3[i] = tab1[pattern[i]];
tab1[pattern[i]] = i;
}
for (i = pattern.length - 2; i > -1; i--) {
if (i < tab1[pattern[i]]) {
continue;
}
p = tab1[pattern[i]];
tab2[p][lp] = lp - i;
tab2[p][pattern.length] = i - 1;
computeJump(pattern, p, i + 1, tab2[p][lp]);
}
computeJump(pattern, tab1[pattern[lp]], pattern.length, 0);
}
public void computeJump(char[] pattern, int index, int len, int defJump) {
int i, k, x, y;
int lpos = len - 1;
int l2pos = len - 2;
int p = tab3[lpos];
OUTER1:
for (k = 0; k < lpos; k++) { // k points to unmatched pattern character
i = tab3[k + 1];
OUTER2:
while (i > 0) {
if (pattern[i - 1] != pattern[k]) {
x = k + 2;
y = i + 1;
while (x < len) {
if (pattern[y++] != pattern[x++]) {
i = tab3[i];
continue OUTER2;
}
}
tab2[index][k] = (len - y) + defJump;
continue OUTER1;
} else {
i = tab3[i];
}
}
x = l2pos - k;
while (p > x) {
p = tab3[p];
}
i = p;
OUTER3:
while (i > -1) {
x = l2pos;
y = i - 1;
while (y > -1) {
if (pattern[y--] != pattern[x--]) {
i = tab3[i];
continue OUTER3;
}
}
tab2[index][k] = (lpos - i) + defJump;
continue OUTER1;
}
tab2[index][k] = len + defJump;
}
}
public int search(char[] text, char[] pattern) {
int k = pattern.length - 1;
int i, j, p;
int lpos = k;
int l2pos = k - 1;
OUTER:
while (k < text.length) {
p = tab1[text[k]];
if (p == -1) {
k += pattern.length;
continue OUTER;
} else {
if (text[k] == pattern[lpos]) {
for (j = l2pos, i = k - 1; j > -1; j--, i--) {
if (text[i] != pattern[j]) {
k += tab2[p][j];
continue OUTER;
}
}
return i + 1;
} else {
for (j = tab2[p][pattern.length], i = k - 1; j > -1; j--, i--) {
if (text[i] != pattern[j]) {
k += tab2[p][j];
continue OUTER;
}
}
k += tab2[p][lpos];
continue OUTER;
}
}
}
return -1;
}
public int search(String origText, String origPattern) {
char[] text = origText.toCharArray();
char[] pattern = origPattern.toCharArray();
processPattern(pattern);
int res = search(text, pattern);
for (int i = 0; i < pattern.length; i++) {
tab1[pattern[i]] = -1;
}
return res;
}
}
这是另一种方法,可能会击败BMH。这类似于BMH,但继续在最后一个文本字符后对齐后续文本字符,直到当前文本字符无法对齐或直到没有更多的图案字符对齐。预处理在每个模式位置构建一个表格,显示任何字符的下一个位置。例如:
Pattern: ABCABC
012345
位置5处的下一个C本身是5,而位置4处的下一个C是2.图案中未找到的字符的下一个位置是-1。以下是Java代码:
public class BoyerMooreHorspool {
int[] tab1 = new int[256];
int[][] tab2 = new int[1000][1000];
int[] tab3 = new int[1000];
public BoyerMooreHorspool() {
for (int i = 0; i < tab1.length; i++) {
tab1[i] = 999;
}
for (int i = 0; i < 1000; i++) {
tab2[999][i] = -1;
}
}
public void processPattern(char[] pattern) {
int i, j, p;
for (i = 0; i < pattern.length; ++i) {
tab1[pattern[i]] = -1;
}
for (i = 0; i < pattern.length; ++i) {
tab3[i] = tab1[pattern[i]];
tab1[pattern[i]] = i;
}
for (i = 0; i < pattern.length; i++) {
p = tab1[pattern[i]];
for (j = tab3[i] + 1; j < i; j++) {
tab2[p][j] = tab3[i];
}
if (i == p) {
for (j = i; j < pattern.length; j++) {
tab2[p][j] = i;
}
} else {
tab2[p][i] = i;
}
}
}
public int search(char[] text, char[] pattern) {
int k = pattern.length - 1;
int i, j, oi, ok;
int lpos = k;
while (k < text.length) {
j = k;
ok = k;
i = tab2[tab1[text[j]]][lpos];
k += lpos - i;
j--;
i--;
while (i > -1) {
oi = i;
i = tab2[tab1[text[j]]][i];
k += oi - i;
j--;
i--;
}
if (ok == k) {
return j + 1;
}
}
return -1;
}
public int search(String origText, String origPattern) {
char[] text = origText.toCharArray();
char[] pattern = origPattern.toCharArray();
processPattern(pattern);
int res = search(text, pattern);
for (int i = 0; i < pattern.length; i++) {
tab1[pattern[i]] = 999;
}
return res;
}
}