Наверное любой программист хоть раз в жизни стоял перед задачей поиска в строке какой-нибудь подстроки. Когда-то столкнуться с этим пришлось и мне. С тех пор это дело мне весьма полюбилось. Не сказать, что я в этом многого достиг, но останавливаться не собираюсь.
Потому и решил написать, но, чтоб начать более или менее плавно, вступление сделать в виде нескольких вводных статеек по основам текстового поиска.
Когда «обычному» человеку нужно найти какую-то подпоследовательность символов в «обычном» тексте, он практически всегда ищет приблизительно, то есть не обязательно точное совпадение, ведь в тексте может быть ошибка, да и в условиях реального текста форма слова может быть несколько отличной от шаблона поиска.
Таким образом можно выделить два вида поиска: Точный (Exact String Matching Algorithm) и Нечёткий (Fuzzy String Matching Algorithm).
Точный поиск является более простым в реализации, ну а самая простая из реализаций – брутфорс (англ. brute force), называемый в соответствии с переводом алгоритмом грубой силы.
Алгоритм пытается сопоставить образец поиска с частью входной строки такой же длины начиная с нулевого символа. Если эта попытка завершилась неудачей, сопоставление производится с первого символа и так далее.
Что у нас с нечётким поиском? В принципе, нечёткий поиск можно организовать, немного модифицировав уже написанный алгоритм.
Но, сначала немного теории.
Пусть нам даётся некоторое целое число k, и некоторая функция отдалённости (distance) рассматриваемой подстроки от образца. Нужно найти такую подстроку s, что distance(s) < k.
Самый простой вариант, искать отдалённость двух строк одинаковой длины – определять количество несовпадающих символов в соответствующих позициях, или количество замен для получения идентичной строки, что по сути одно и то же. Этот вариант был предложен Хеммингом, потому и функция отдалённости называется расстоянием Хемминга.
Если нужно сравнить строки разной длины, то нужно использовать операции удаления и вставки.
Здесь также существует два варианта.
Нечёткий поиск вполне можно использовать для поиска возможных исправлений при проверке орфографии, главное, число k не задать слишком малым, а то возможны глюки как в Firefox:
Попробуем реализовать нечёткий поиск на брутфорс-алгоритме. Изменим внутренний цикл так, чтоб для каждой подстроки он находил расстояние Хемминга. Также нужен будет ещё один параметр – k. Причём для этого случая по-моему удобнее будет использовать действительное k в диапазоне от нуля до единицы. Это число будет показывать максимальный процент несовпадений. Тогда формула станет несколько иной:
distance(s) <= length(s) * k.
Итак, реализация:
И немного отрефакторим код для приличия:
Подводя итоги скажу, что представленные алгоритмы весьма неэффективны, однако, топик и не претендует ни на что иное, как быть введением в текстовый поиск.
Здесь можно скачать архив проекта с тестами.
p.s. Далее планирую продолжить свои начинания в виде серии «парсинг для чайников», кем я пока и являюсь :)
Потому и решил написать, но, чтоб начать более или менее плавно, вступление сделать в виде нескольких вводных статеек по основам текстового поиска.
Когда «обычному» человеку нужно найти какую-то подпоследовательность символов в «обычном» тексте, он практически всегда ищет приблизительно, то есть не обязательно точное совпадение, ведь в тексте может быть ошибка, да и в условиях реального текста форма слова может быть несколько отличной от шаблона поиска.
Таким образом можно выделить два вида поиска: Точный (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.
Расстояние Хемминга
Самый простой вариант, искать отдалённость двух строк одинаковой длины – определять количество несовпадающих символов в соответствующих позициях, или количество замен для получения идентичной строки, что по сути одно и то же. Этот вариант был предложен Хеммингом, потому и функция отдалённости называется расстоянием Хемминга.
Расстояние Левенштейна
Если нужно сравнить строки разной длины, то нужно использовать операции удаления и вставки.
Здесь также существует два варианта.
- Функция отдалённости или расстояние d определяется как количество замен, удалений или вставок, необходимых для получения из рассматриваемой строки искомого шаблона.
- 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. Далее планирую продолжить свои начинания в виде серии «парсинг для чайников», кем я пока и являюсь :)