Как мне реализовать «фонетический» поиск

Question

В настоящее время я пытаюсь улучшить свой алгоритм поиска.

Для лучшего понимания, вот текущая логика:
у нас есть объекты с прикрепленными n ключевых слов в дБ. в базе данных это решается с помощью 2 таблиц (Object, Keyword), где таблица Keyword имеет FK до Object. Когда я создаю свои поисковые деревья, я создаю строковое значение (объявление: удалить умные слова, преобразовать в нижний регистр, ...) из всех ключевых слов объекта. та же самая процедура преобразования (NormalizeSearchPattern()) выполняется с шаблонами поиска. Я поддерживаю 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()), чтобы он был нечувствительным, когда он сводится к:

• единственном / множественном
• misstyping (например, "hauserr" <-> "hauser")
• ...

Просто чтобы узнать больше о дизайне:
Это приложение выполнено на языке c #, оно хранит деревья поиска и объекты в статической переменной (чтобы запросить базу данных только один раз при инициализации), производительность должна быть выдающейся (в настоящее время 500 000 строк-значений запрашиваются в течение менее 300 мс).

Answer 1

Вам следует изучить алгоритм Soundex .Это алгоритм для преобразования слов в фонетическое пространство, так что слова с похожим звучанием (и слова с ошибками) отображаются на одинаковые (или похожие) значения.В википедии есть список других фонетических алгоритмов :

• Soundex, который был разработан для кодирования фамилий для использования в переписи.Коды Soundex - это четырехсимвольные строки, состоящие из одной буквы, за которой следуют три цифры.
  • Daitch – Mokotoff Soundex, который является усовершенствованием Soundex, разработанным для лучшего соответствия фамилий славянского и германского происхождения.Коды Daitch – Mokotoff Soundex - это строки, состоящие из шести цифровых цифр.
  • Kölner Phonetik, аналогичный Soundex, но более подходящий для немецких слов.
  • Метафон и двойной метафон, который подходит для использованияс большинством английских слов, а не только имена.Метафонные алгоритмы являются основой для многих популярных программ проверки правописания.
  • Miracode
  • Система идентификации и разведки штата Нью-Йорк (NYSIIS), которая сопоставляет похожие фонемы с одной и той же буквой.В результате получается строка, которую читатель может произносить без расшифровки.
  • Подход Match Rating, разработанный Western Airlines в 1977 году - этот алгоритм имеет метод кодирования и сравнения диапазонов.

Answer 2

Вам также может быть интересен алгоритм поиска поиска Trigram и Bigram :

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

Answer 3

Попробуйте взглянуть на то, что называется расстояние Левенштейна , оно вычисляет, сколько изменений требуется, чтобы заменить одно слово на другое.

Несколько изменений указывают на очень похожие слова.

Для сопоставления множественного числа вы также можете использовать таблицы псевдонимов, если форма множественного числа сильно отличается от единственного числа, но вы все равно хотите, чтобы они соответствовали. Я предполагаю, что Google использует некоторую форму списков псевдонимов для предложений альтернативных вопросов.