如何实现"语音"式搜索

Question

目前我正在尝试增强我的搜索算法.

为了更好地理解,这里是它背后的当前逻辑:
我们在db中有附加n个关键字的对象.在数据库中,这是通过2个表(Object,Keyword)来解决的,其中Keyword-table的FK为Object.当我构建我的搜索树时,我创建了一个对象的所有关键字的行值(ad:remove umlauts,convert to lower-case,...).NormalizeSearchPattern()使用搜索模式完成相同的convertion-routine().我支持AND搜索和关键字,最小长度只有2个字符!

搜索算法目前是fast-reverse-search(此示例未优化)的变体:

bool IsMatch(string source, string searchPattern)
{
    // example:
    // source: "hello world"
    // searchPattern: "hello you freaky funky world"
    // patterns[]: { "hello", "you", "freaky", "funky", "world" }

    searchPattern = NormalizeSearchPattern(searchPattern);
    var patterns = MagicMethodToSplitPatternIntoPatterns(searchPattern);
    foreach (var pattern in patterns)
    {
        var success = false;
        var patternLength = pattern.Length;
        var firstChar = pattern[0];
        var secondChar = pattern[1];

        var lengthDifference = input.Length - patternLength;
        while (lengthDifference >= 0)
        {
            if (source[lengthDifference--] != firstChar)
            {
                continue;
            }
            if (source[lengthDifference + 2] != secondChar)
            {
                continue;
            }

            var l = lengthDifference + 3;
            var m = 2;
            while (m < patternLength)
            {
                if (input[l] != pattern[m])
                {
                    break;
                }
                l++;
                m++;
            }

            if (m == patternLength)
            {
                success = true;
            }
        }
        if (!success)
        {
            return false;
        }
    }
    return true;
}

标准化完成(此示例未优化)

    string RemoveTooShortKeywords(string keywords)
    {
        while (Regex.IsMatch(keywords, TooShortKeywordPattern, RegexOptions.Compiled | RegexOptions.Singleline))
        {
            keywords = Regex.Replace(keywords, TooShortKeywordPattern, " ", RegexOptions.Compiled | RegexOptions.Singleline);
        }

        return keywords;
    }

    string RemoveNonAlphaDigits(string value)
    {
        value = value.ToLower();
        value = value.Replace("ä", "ae");
        value = value.Replace("ö", "oe");
        value = value.Replace("ü", "ue");
        value = value.Replace("ß", "ss");

        return Regex.Replace(value, "[^a-z 0-9]", " ", RegexOptions.Compiled | RegexOptions.Singleline);
    }

    string NormalizeSearchPattern(string searchPattern)
    {
        var resultNonAlphaDigits = RemoveNonAlphaDigits(searchPattern);
        var resultTrimmed = RemoveTooShortKeywords(resultNonAlphaDigits);
        return resultTrimmed;
    }

因此,这是非常简单的,因此很明显,我只能用变异应对source和searchPattern我在已经实现NormalizeSearchPattern()(如上面提到的:变音符号,大小写区别,...).

但是,NormalizeSearchPattern()当涉及到以下情况时,我应该如何将算法(或)增强为非敏感性:

• 单数复数
• 错误的分类(例如"hauserr"< - >"hauser")
• ...

只是要了解更多有关设计的信息:
这个应用程序是在c#中完成的,它将搜索树和对象存储在一个静态变量中(仅在初始化时查询数据库一次),性能必须非常出色(目前在500以内查询500.000行值)超过300毫秒).

Answer 1

您可能还对Trigram 和 Biggram 搜索匹配算法感兴趣：

当目标对象的确切语法或拼写未知时，三元组搜索是一种强大的文本搜索方法。它查找与输入的搜索词中最大数量的三字符字符串匹配的对象，即接近匹配。可以指定阈值作为截止点，之后结果不再被视为匹配。