Gho*_*der 7 c++ string algorithm url 64-bit
我需要编写一个C/C++函数,它可以快速检查字符串是否以~1000个预定义后缀之一结束.具体来说,字符串是主机名,我需要检查它是否属于几百个预定义的二级域之一.
这个函数将被调用很多,因此需要尽可能高效地编写.只要结果很快,任何事情就会发生.
后缀集是在编译时预先确定的,不会改变.
我想要实现一个Rabin-Karp的变体,或者编写一个工具来生成一个嵌套ifs和switch的函数,这些函数可以根据特定的后缀集进行定制.由于所讨论的应用程序是64位加速比较,我可以存储长度最多为8个字节的后缀作为常量排序数组并在其中进行二进制搜索.
还有其他合理的选择吗？
Jam*_*ack 11
如果后缀不包含任何扩展/规则(如正则表达式),则可以按相反的顺序构建后缀的Trie,然后根据该字符串匹配字符串.例如
suffixes:
foo
bar
bao
reverse order suffix trie:
o
-a-b (matches bao)
-o-f (matches foo)
r-a-b (matches bar)
然后可以使用它们来匹配您的字符串:
"mystringfoo" -> reverse -> "oofgnirtsym" -> trie match -> foo suffix
经过一些研究和深思熟虑，我决定采用 trie/有限状态机方法。
只要到目前为止解析的后缀部分可以对应于多个后缀，就使用 TRIE 从最后一个字符开始向后解析字符串。在某些时候，我们要么击中一个可能的后缀的第一个字符，这意味着我们有一个匹配，要么击中死胡同，这意味着没有更多可能的匹配，或者进入只有一个后缀候选的情况。在这种情况下，我们只比较后缀的其余部分。
由于 trie 查找的时间是恒定的，因此最坏情况的复杂度为 o（最大后缀长度）。事实证明该功能非常快。在 2.8Ghz Core i5 上，它每秒可以检查 33,000,000 个字符串以查找 2K 可能的后缀。2K 后缀总计 18 KB，扩展为 320kb trie/状态机表。我想我可以更有效地存储它，但这个解决方案目前似乎工作得足够好。
由于后缀列表太大，我不想全部手动编码，因此我最终编写了 C# 应用程序，为后缀检查函数生成 C 代码：
public static uint GetFourBytes(string s, int index)
{
byte[] bytes = new byte[4] { 0, 0, 0, 0};
int len = Math.Min(s.Length - index, 4);
Encoding.ASCII.GetBytes(s, index, len, bytes, 0);
return BitConverter.ToUInt32(bytes, 0);
}
public static string ReverseString(string s)
{
char[] chars = s.ToCharArray();
Array.Reverse(chars);
return new string(chars);
}
static StringBuilder trieArray = new StringBuilder();
static int trieArraySize = 0;
static void Main(string[] args)
{
// read all non-empty lines from input file
var suffixes = File
.ReadAllLines(@"suffixes.txt")
.Where(l => !string.IsNullOrEmpty(l));
var reversedSuffixes = suffixes
.Select(s => ReverseString(s));
int start = CreateTrieNode(reversedSuffixes, "");
string outFName = @"checkStringSuffix.debug.h";
if (args.Length != 0 && args[0] == "--release")
{
outFName = @"checkStringSuffix.h";
}
using (StreamWriter wrt = new StreamWriter(outFName))
{
wrt.WriteLine(
"#pragma once\n\n" +
"#define TRIE_NONE -1000000\n"+
"#define TRIE_DONE -2000000\n\n"
);
wrt.WriteLine("const int trieArray[] = {{{0}\n}};", trieArray);
wrt.WriteLine(
"inline bool checkSingleSuffix(const char* str, const char* curr, const int* trie) {\n"+
" int len = trie[0];\n"+
" if (curr - str < len) return false;\n"+
" const char* cmp = (const char*)(trie + 1);\n"+
" while (len-- > 0) {\n"+
" if (*--curr != *cmp++) return false;\n"+
" }\n"+
" return true;\n"+
"}\n\n"+
"bool checkStringSuffix(const char* str, int len) {\n" +
" if (len < " + suffixes.Select(s => s.Length).Min().ToString() + ") return false;\n" +
" const char* curr = (str + len - 1);\n"+
" int currTrie = " + start.ToString() + ";\n"+
" while (curr >= str) {\n" +
" assert(*curr >= 0x20 && *curr <= 0x7f);\n" +
" currTrie = trieArray[currTrie + *curr - 0x20];\n" +
" if (currTrie < 0) {\n" +
" if (currTrie == TRIE_NONE) return false;\n" +
" if (currTrie == TRIE_DONE) return true;\n" +
" return checkSingleSuffix(str, curr, trieArray - currTrie - 1);\n" +
" }\n"+
" --curr;\n"+
" }\n" +
" return false;\n"+
"}\n"
);
}
}
private static int CreateTrieNode(IEnumerable<string> suffixes, string prefix)
{
int retVal = trieArraySize;
if (suffixes.Count() == 1)
{
string theSuffix = suffixes.Single();
trieArray.AppendFormat("\n\t/* {1} - {2} */ {0}, ", theSuffix.Length, trieArraySize, prefix);
++trieArraySize;
for (int i = 0; i < theSuffix.Length; i += 4)
{
trieArray.AppendFormat("0x{0:X}, ", GetFourBytes(theSuffix, i));
++trieArraySize;
}
retVal = -(retVal + 1);
}
else
{
var groupByFirstChar =
from s in suffixes
let first = s[0]
let remainder = s.Substring(1)
group remainder by first;
string[] trieIndexes = new string[0x60];
for (int i = 0; i < trieIndexes.Length; ++i)
{
trieIndexes[i] = "TRIE_NONE";
}
foreach (var g in groupByFirstChar)
{
if (g.Any(s => s == string.Empty))
{
trieIndexes[g.Key - 0x20] = "TRIE_DONE";
continue;
}
trieIndexes[g.Key - 0x20] = CreateTrieNode(g, g.Key + prefix).ToString();
}
trieArray.AppendFormat("\n\t/* {1} - {2} */ {0},", string.Join(", ", trieIndexes), trieArraySize, prefix);
retVal = trieArraySize;
trieArraySize += 0x60;
}
return retVal;
}
所以它会生成这样的代码：
inline bool checkSingleSuffix(const char* str, const char* curr, const int* trie) {
int len = trie[0];
if (curr - str < len) return false;
const char* cmp = (const char*)(trie + 1);
while (len-- > 0) {
if (*--curr != *cmp++) return false;
}
return true;
}
bool checkStringSuffix(const char* str, int len) {
if (len < 5) return false;
const char* curr = (str + len - 1);
int currTrie = 81921;
while (curr >= str) {
assert(*curr >= 0x20 && *curr <= 0x7f);
currTrie = trieArray[currTrie + *curr - 0x20];
if (currTrie < 0) {
if (currTrie == TRIE_NONE) return false;
if (currTrie == TRIE_DONE) return true;
return checkSingleSuffix(str, curr, trieArray - currTrie - 1);
}
--curr;
}
return false;
}
由于对于 checkSingleSuffix 中我的特定数据集 len 永远不会超过 9，因此我尝试用 switch (len) 和硬编码比较例程替换比较循环，一次最多比较 8 个字节的数据，但它并没有影响整体无论哪种方式的性能。
感谢所有贡献自己想法的人！