Введение в поиск по тексту

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


Когда «обычному» человеку нужно найти какую-то подпоследовательность символов в «обычном» тексте, он практически всегда ищет приблизительно, то есть не обязательно точное совпадение, ведь в тексте может быть ошибка, да и в условиях реального текста форма слова может быть несколько отличной от шаблона поиска.
Таким образом можно выделить два вида поиска: Точный (Exact String Matching Algorithm) и Нечёткий (Fuzzy String Matching Algorithm).

Точный поиск

Точный поиск является более простым в реализации, ну а самая простая из реализаций – брутфорс (англ. brute force), называемый в соответствии с переводом алгоритмом грубой силы.

int Match(string input, string pattern)
{
    int inputLength = input.Length;
    int patternLength = pattern.Length;
    
    for (int i = 0; i <= inputLength - patternLength; i++)
    {
        bool success = true;
        for (int j = 0; j < patternLength; j++)
        {
            if (input[i + j] != pattern[j])
            {
                success = false;
                break;
            }
        }
        if (success) return i;
    }
    return -1;
}

Алгоритм пытается сопоставить образец поиска с частью входной строки такой же длины начиная с нулевого символа. Если эта попытка завершилась неудачей, сопоставление производится с первого символа и так далее.

Нечёткий поиск

Что у нас с нечётким поиском? В принципе, нечёткий поиск можно организовать, немного модифицировав уже написанный алгоритм.
Но, сначала немного теории.
Пусть нам даётся некоторое целое число k, и некоторая функция отдалённости (distance) рассматриваемой подстроки от образца. Нужно найти такую подстроку s, что distance(s) < k.

Расстояние Хемминга

Самый простой вариант, искать отдалённость двух строк одинаковой длины – определять количество несовпадающих символов в соответствующих позициях, или количество замен для получения идентичной строки, что по сути одно и то же. Этот вариант был предложен Хеммингом, потому и функция отдалённости называется расстоянием Хемминга.

Расстояние Левенштейна

Если нужно сравнить строки разной длины, то нужно использовать операции удаления и вставки.
Здесь также существует два варианта.

1. Функция отдалённости или расстояние d определяется как количество замен, удалений или вставок, необходимых для получения из рассматриваемой строки искомого шаблона.
   
   
2. d определяется, как сумма цен изменений в подстроке для получения искомого шаблона, где
   
   • цена удаления = 1
   • цена вставки = 1
   • цена замены = 2 (сперва удаляем символ за 1 и также по цене 1 вставляем нужный)
   
   
   

Нечёткий поиск вполне можно использовать для поиска возможных исправлений при проверке орфографии, главное, число k не задать слишком малым, а то возможны глюки как в Firefox:


Попробуем реализовать нечёткий поиск на брутфорс-алгоритме. Изменим внутренний цикл так, чтоб для каждой подстроки он находил расстояние Хемминга. Также нужен будет ещё один параметр – k. Причём для этого случая по-моему удобнее будет использовать действительное k в диапазоне от нуля до единицы. Это число будет показывать максимальный процент несовпадений. Тогда формула станет несколько иной:
distance(s) <= length(s) * k.
Итак, реализация:

int Match(string input, string pattern, double k)
{
    if (k < 0 || k > 1)
        throw new ArgumentException("Invalid value for coefficient", "k");

    int inputLength = input.Length;
    int patternLength = pattern.Length;

    for (int i = 0; i <= inputLength - patternLength; i++)
    {
        int distance = 0;
        for (int j = 0; j < patternLength; j++)
        {
            if (input[i + j] != pattern[j])
            {
                distance++;
            }
        }
        if (distance <= k * patternLength) return i;
    }
    return -1;
}

И немного отрефакторим код для приличия:

public int Match(string input, string pattern, double k)
{
    if (k < 0 || k > 1)
        throw new ArgumentException("Invalid value for coefficient", "k");

    int inputLength = input.Length;
    int patternLength = pattern.Length;

    for (int i = 0; i <= inputLength - patternLength; i++)
    {
        if (GetDistance(input.Substring(i, patternLength), pattern) <= k * patternLength)
            return i;
    }
    return -1;
}

private int GetDistance(string subString, string pattern)
{
    int changesCount = 0;
    int patternLength = pattern.Length;

    for (int i = 0; i < patternLength; i++)
    {
        if (subString[i] != pattern[i])
            changesCount++;
    }
    return changesCount;
}


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

Здесь можно скачать архив проекта с тестами.

p.s. Далее планирую продолжить свои начинания в виде серии «парсинг для чайников», кем я пока и являюсь :)