Как найти нужный символ в тексте

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

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

Когда «обычному» человеку нужно найти какую-то подпоследовательность символов в «обычном» тексте, он практически всегда ищет приблизительно, то есть не обязательно точное совпадение, ведь в тексте может быть ошибка, да и в условиях реального текста форма слова может быть несколько отличной от шаблона поиска.
Таким образом можно выделить два вида поиска: Точный (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. Далее планирую продолжить свои начинания в виде серии «парсинг для чайников», кем я пока и являюсь

Занимался вот намедни всяческими

сексуальными

извращениями с текстами очередных аффтаров от медицины в MS Word. И нужно мне было искать и заменять кучу всякой нецензурщины и тарабарщины, ибо аффтары, по большей своей части, русскому языку

вовсе не

обучены плохо (всё на аглицком кириллицей норовят писать и прочее) и тексты форматировать читабельно не умеют. Заменять и просто менять там нужно было очень много чего, а стандартных общеизвестных встроенных в редактор средств поиска стало не хватать, нужно было прибегать к использованию регулярных выражений. А как? На известные мне ранее маски волшебная программа Word стала грязно ругаться матом. Как всегда выручил Гугл. Немного покопавшись я обнаружил, что гениальные мелкомягкие написатели MS Office и тут пошли своим путём, обозвав такие выражения wildcards и немного изменив их синтаксис. В целом разобраться можно.

Оказалось всё довольно просто (у меня Office 2007, но, думаю, будет справедливо и для предыдущих версий, разве что будут незначительные отличия в названиях пунктов, но вы разберётесь, я верю ;)). И не нужно было, по большому счёту, никуда лезть искать. Наряду со сразу видимыми, если вызвать в Word’е окно «Поиск» (Ctrl+F) или «Поиск и замена» (Ctrl+H), поставить курсор в поле «Найти» и нажать кнопочку «Больше», а после «Специальный», спецсимволами, есть и ещё одна опция, о которой чуть ниже.Оказалось всё довольно просто (у меня Office 2007, но, думаю, будет справедливо и для предыдущих версий, разве что будут незначительные отличия в названиях пунктов, но вы разберётесь, я верю ;)). И не нужно было, по большому счёту, никуда лезть искать. Наряду со сразу видимыми, если вызвать в Word’е окно «Поиск» (Ctrl+F) или «Поиск и замена» (Ctrl+H), поставить курсор в поле «Найти» и нажать кнопочку «Больше», а после «Специальный», спецсимволами, есть и ещё одна опция, о которой чуть ниже.
Сперва о стандартных масках поиска:

^? — любой знак
^# — любая цифра
^$ — любая буква
^p — Знак абзаца (¶) (если выбран параметр «Подстановочные знаки» следует заменить на ^13)
^t — знак табуляции (→) (если выбран параметр «Подстановочные знаки» следует заменить на ^9)
^+ — длинное тире ( — )
^= — короткое тире ( – )
^^ — знак крышки (^)
^l — принудительный разрыв строки (символ ↵ или 0xBF), такой бывает если нажать Shift+Enter (если выбран параметр «Подстановочные знаки» следует заменить на ^11)
^n — разрыв колонки (если выбран параметр «Подстановочные знаки» следует заменить на ^14)
^12 — Разрыв раздела или страницы (при замене добавляет разрыв страницы)
^m — Принудительный разрыв страницы (применяется также для поиска и замены разрывов разделов, если выбран параметр «Подстановочные знаки»)
^s — неразрывный пробел (º) (Ctrl+Shift+Space)
^~ — неразрывный дефис (≈)
^- — мягкий перенос (¬)
Теперь перейдём к полю «Заменить на», тут появляются две специфические опции:
^& — искомый текст
^c — содержимое буфера обмена
Как это можно использовать? Например так — пусть нужно найти текст «Achtung!» и «Achtung.»? покрасить его в зелёный и заменить на «Achtung, minen!» (именно красного цвета). Причём в тексте у вас есть и просто слово «achtung» с маленькой буквы, которое менять не нужно. Решение:
Написать красным «minen!» и вырезать в буфер обмена
Найти (отметив галочку «Учитывать регистр»): Achtung
Заменить на (переставить курсор на это поле и нажать кнопку «Формат», затем выбрать «Шрифт» и там зелёный):
Теперь Найти: Achtung^?
Заменить на: Achtung, ^c

С этим всё действительно просто и понятно. А если нужно в огромном списке литературы вида
Reynolds J. V., Murchan P., Leonard N. et al. High-dose interlenkin-2 promotes bacterial translocation from the gut // Brit. J. Cancer.-1995. -Vol. 72, N 3. — P. 634-636.
привести всё к нормальному виду
ReynoldsºJ.V., MurchanºP., LeonardºN. etºal. High-dose interlenkin-2 promotes bacterial translocation from the gut // Brit. J. Cancer.º— 1995.º— V.72(3).º— P.º634–636.
Как быть? Ручками править в каждой строчке всё это будет очень долго и утомительно. Но это тоже можно сделать поиском и заменой.
Если отметить в окне поиска и замены галочку «Подстановочные знаки», то содержимое кнопки «Специальный» для поля «Найти» примет несколько иной вид:

? — любой знак
[ — ] — знак в диапазоне
< — в начале слова
> — в конце слова
() — диапазон
[!] — не
{; } — число вхождений
@ — предыдущий 1 или более
* — любое число знаков
А для поля «Заменить на» появится дополнительный пункт
n — искомое выражение
Как этим пользоваться? Просто. Начну почти по порядку.
? и * — по сути одно и то же, но выражение ??са будет для поиска значить «[пробел]оса», «коса», «лиса» и ещё кучу всего, содержащего два символа впереди «са». А выражение *са выделит вам весь текст от положения курсора в тексте до первого попавшегося «са», в том числе и «[курсор]По полю бежало животное с номером 25, это была лиса».
Близок по смыслу к предыдущим и символ @. Тут фантазии на пример у меня не хватило, заимствую у мелкомягких: lo@t поможет найти «lot» или «loot», ful@ поможет найти «ful» или «full» и т.д. 
Почти из той же оперы символы < и >: <ок поможет найти все «около», а ок> — всевозможный «шок».
Выражение [A-Z] поможет найти любую букву английского алфавита в верхнем регистре, а [A-я] — любую букву и русского и английского. Неразрывно с этим используется и выражение {; }. Выглядит это так: допустим, нужно найти все слова, начинающиеся с заглавной буквы и длиной от 4 до 5 букв и заканчивающиеся вопросительным знаком. Решением будет искать их по следующей маске:
[A-Я]{1;1}[a-я]{3;4}?
то есть найти одну заглавную букву и ещё 3 или 4 следующих за ней строчных плюс вопросительный знак. Тут есть одна маленькая тонкость — так как символ «?» используется как подстановочный, то, чтобы поиск его воспринял за знак вопроса, а не любой символ перед ним нужно поставить «». Если нужно найти сам символ «» в тексте, то это будет выглядеть как \, ну и т.д.
При помощи [!] можно найти например всё кроме заглавных букв: [!A-Я].
Теперь о самом наверное интересном операторе поиска — (). При его помощи можно находить несколько разных выражений и группировать их при помощи оператора n. Простой пример: пусть вам нужно по всему тексту заменить «Фамилия И О» на «И.О.ºФамилия». Решение:
Найти: ([A-Я]{1;1}[a-я]{2;11}) ([A-Я]{1;1}) ([A-Я]{1;1})
Заменить на: 2.3.^s1
То есть каждое выражение в скобках в поле «Найти» соответствует по порядку оператору n в поле «Заменить на».
Теперь с заданной выше задачей я думаю вы справитесь и сами

P.S. Я желаю долгого здравия и личного счастья всем разработчикам «Визуального редактора» постов в ЖЖ. Пришлось копировать весь сгенерированный код в обычный блокнот и править всё ручками… Страницы, сгенерированные MS Word выглядят лучше чем ЭТО. Какое уж тут соблюдение стандартов HTML…

Возможности

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

1. Найти и заменить — находит и заменяет элемент.
2. Найти и удалить — находит и удаляет нужный элемент.
3. Найти и подсветить — находит искомое значение и подсвечивает контрастным цветом.

Незаменимый помощник для редактора, копирайтера, маркетолога и специалиста по контекстной рекламе. Скрипт производит массовые операции во всем тексте с символами (пробелы, иконки, знаки), а также буквами, словами, выражениями, словосочетаниями и фразами.

Подстановочные символы (скоро)

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

? (вопросительный знак) — используется в качестве фильтра для одного любого символа. Например, условие «дро?а» будет соответствовать словам «дрова» , «дрофа» или «дрона» .
* (звездочка) — используется чтобы найти выражение с любым количеством символов. Для примера, условие «красн*» соответствует словам «красная» , красного» , «краснуха» , «красненького» и т.д.

Инструмент заменяет привычный Word и Excel и позволяет искать, заменять или удалять элементы онлайн, когда привычные пакетные офисные программы отсутствуют под рукой.

Инструкция

Найти и заменить

1. Выберите функцию Найти и заменить (доступа по умолчанию);
2. Вставьте исходный текст для изменения;
3. В строке Найти укажите искомое слово или фразу;
4. В поле Заменить введите новое значение;
5. Нажмите на кнопку Выполнить. Алгоритм найдет все вхождения и заменит.

Найти и удалить

1. Выберите функцию Найти и удалить;
2. Вставьте исходный текст в текстовое окно;
3. В строке Найти укажите слово или фразу для удаления;
4. Нажмите на Выполнить. Алгоритм удалит все найденные значения.

Найти и выделить

1. Чтобы подсветить буквы или слово, выберите нужную функцию;
2. Укажите ключ-значение в поле Найти;
3. Далее кнопка Выполнить для определения всех значений.

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

С лёгкостью можно отправить полученный результат в буфер обмена — просто нажмите на кнопку Скопировать в самом низу.

Узнать подробнее →