Наивный алгоритм сопоставления строк в Python: примеры, избранное, плюсы и минусы

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

Одна из основных причин, по которой используется наивный алгоритм сопоставления строк, заключается в том, что он быстрый и дает довольно точные результаты. Кроме того, он не требует предварительной обработки. В любом случае, мы обсудим эти преимущества позже в этом посте. Давайте сначала разберемся с алгоритмом поиска паттернов, используя наивный подход.

Наивный алгоритм поиска паттернов

При простом поиске строкового шаблона программа проверяет позицию входного шаблона P[1……i] в строке символов T[1…..m].

Обратите внимание, что длина вводимого текста или строки всегда будет больше или равна длине шаблона.

Вот наивный алгоритм поиска шаблонов для разных языков программирования.

Начинать

pat = размер узора

ул = размер строки

для i = 0 to (str – pat), do

для j = 0 погладить, сделать

если text[i+j] ≠ pattern[j], то

разорвать петлю

Готово

если j == pat, то

отображать положение i как найденный шаблон

Готово

Конец

Этот алгоритм очень важен в компьютерных науках, поскольку он помогает выводить результаты поиска.

Читайте : Типы алгоритмов ИИ, которые вы должны знать

Примеры наивного сопоставления строк на Python

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

# Программа Python для наивного сопоставления строк

# Алгоритм поиска

поиск по определению (P, T):

Х = лен(П)

Y = лен(Т)

# Цикл для сдвига P[] по одному */

для i в диапазоне (X – Y + 1):

j = 0

# Для текущего индекса i проверьте

# для сопоставления с образцом */

для j в диапазоне (0, X):

если (txt[i + j]! = P[j]):

перерыв

если (j == X – 1):

print («Шаблон найден в позиции «, i)

# Код драйвера

если __name__ == '__main__':

T = «ОБНОВИТЬ ДУБУПГРААБУПГРЕДДУ»

П = «ОБНОВИТЬ»

поиск(П, Т)

Выход :

Шаблон найден в позиции 0

Паттерн найден в позиции 17

Объяснение: Первая позиция - это 0 -я позиция. Поскольку паттерн «UPGRAD» был впервые обнаружен здесь, выходные данные показали, что паттерн находится в позиции 0.

Точно так же следующий паттерн был найден в позиции 17.

Лучший случай наивного поиска по шаблону

Существует только один лучший случай для наивного алгоритма поиска по шаблону, в отличие от двух худших случаев.

В лучшем случае первый символ в тексте шаблона отсутствует во входной строке.

Пример:

T[] = «УЛУЧШЕННЫЙ КЛУПГРА»;

P[] = "ТУГРА";

И, следовательно, количество совпадающих шаблонов равно O (n).

Худший случай наивного поиска по шаблону

В наивном подходе к поиску строк есть два худших случая.

1. Когда все символы в шаблоне такие же, как и во входной строке.

T [] = "ЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕ";

Р [] = "ЕЕЕ";

1. Когда только последний символ в шаблоне отличается от входной строки.

T [] = «ЕЕЕЕЕЕЕЕЕЕЕЕЕЕ»;

Р [] = "ЕЕЕЕД";

В таких случаях количество сравнений в O(m*(n-m+1)).

Особенности наивного алгоритма сопоставления строк

Алгоритм сопоставления строк предназначен для поиска всех вхождений заданного шаблона в тексте.

Вот главные особенности алгоритма.

1. Это самый простой способ поиска закономерностей во вводимом тексте. Он проверяет все символы один за другим в заданной строке символов.
2. Он находит точные совпадения строк — будь то более или более точные вхождения шаблона.
3. Это больше используется, когда есть небольшой текст. Кроме того, он не требует каких-либо этапов предварительной обработки.
4. Этот метод поиска не занимает лишнего места для работы и поиска шаблонов в строке.

Читайте также: Структура данных и алгоритм в Python.

Преимущества наивного поиска по шаблону

1. В подходе наивного поиска не требуются этапы предварительной обработки, поскольку время его выполнения равно времени сопоставления.
2. Дополнительное рабочее пространство не требуется.
3. Сравнение шаблонов со строками можно выполнять в любом порядке.

Недостатки наивного сопоставления строк

У наивного подхода к сопоставлению строк есть только один недостаток — он неэффективен. Это потому, что когда он находит позицию, он не использует ее снова, чтобы найти другую позицию. Он возвращается к исходной точке и снова ищет паттерн. А значит, он больше не использует информацию из предыдущей смены.

Заключение

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

Мы надеемся, что эта статья дала вам хорошее представление о наивном подходе к поиску по шаблону в Python. Чтобы узнать об использовании этого подхода и получить более широкое представление о теме, свяжитесь с экспертами upGrad. У нас есть специально разработанные курсы для тех, кто хочет расширить свой набор навыков. Свяжитесь с нами сегодня!

Если вам интересно узнать больше об искусственном интеллекте и машинном обучении, ознакомьтесь с дипломом PG IIIT-B и upGrad в области машинного обучения и искусственного интеллекта, который предназначен для работающих профессионалов и предлагает более 450 часов тщательного обучения, более 30 тематических исследований и заданий, Статус выпускника IIIT-B, более 5 практических практических проектов и помощь в трудоустройстве в ведущих фирмах.