Эффективно проверьте строку на один из нескольких сотен возможных суффиксов

После некоторых исследований и размышлений Я решил пойти с подходом к trie / конечному автомату.

Строка анализируется, начиная с последнего символа, идущего в обратном направлении, с использованием TRIE до тех пор, пока часть суффикса, которая была проанализирована до сих пор, может соответствовать нескольким суффиксам. В какой-то момент мы либо попадаем в первый символ одного из возможных суффиксов, что означает, что у нас есть совпадение, заходим в тупик, что означает, что больше нет возможных совпадений, либо попадаем в ситуацию, когда есть только один кандидат на суффикс. В этом случае мы просто сравниваем остаток суффикса.

Поскольку поиск в дереве выполняется постоянно, сложность в худшем случае равна o (максимальная длина суффикса). Функция оказалась довольно быстрой. На процессоре Core i5 с тактовой частотой 2,8 ГГц он может проверять 33 000 000 строк в секунду на предмет возможных суффиксов 2K. Суффиксы 2K общим объемом 18 килобайт, расширенные до 320kb trie / table machine.Я предполагаю, что мог бы сохранить его более эффективно, но на данный момент это решение, похоже, работает достаточно хорошо.

Поскольку список суффиксов был таким большим, я не хотел кодировать все вручную, поэтому в итоге я написал приложение на 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;
    }

Поскольку для моего конкретного набора данных len в checkSingleSuffix никогда не было больше 9, я попытался заменить цикл сравнения переключателем (len) и жестко запрограммированными процедурами сравнения, которые сравнивали до 8 байтов данных за раз, но это не повлияло общая производительность в любом случае.

Спасибо всем, кто поделился своими идеями!