Python의 순진한 문자열 일치 알고리즘: 예제, 추천 및 장단점

문자열에서 입력 패턴을 찾아야 하는 경우 코더와 프로그래머는 문자열 일치 알고리즘을 사용합니다. 일반적으로 짧은 문자열의 경우 파이썬 프로그래머는 프로그램이 쿼리 패턴에 대해 입력 문자열의 각 위치를 확인하는 순진한 접근 방식을 선호합니다. 일치하는 경우 위치 번호와 함께 출력을 제공합니다.

순진한 문자열 매칭 알고리즘을 사용하는 가장 큰 이유 중 하나는 빠르고 정확한 결과를 얻을 수 있기 때문입니다. 또한 전처리가 필요하지 않습니다. 어쨌든, 우리는 이 포스트의 뒷부분에서 이러한 장점에 대해 논의할 것입니다. 먼저 순진한 접근 방식을 사용하여 패턴 검색을 위한 알고리즘을 이해합시다.

순진한 패턴 검색 알고리즘

순진한 문자열 패턴 검색에서 프로그램은 문자열 T [1...m]에서 입력 패턴 P [1...i]의 위치를 ​​테스트합니다.

입력 텍스트 또는 문자열의 길이는 항상 패턴의 길이보다 크거나 같습니다.

다음은 다양한 프로그래밍 언어에 대한 순진한 패턴 검색 알고리즘입니다.

시작하다

pat = 패턴 크기

str = 문자열 크기

i = 0에서 (str – pat)에 대해 수행

j = 0에 대해 pat, 수행

텍스트[i+j] ≠ 패턴[j]이면

고리를 끊다

완료

j == pat이면

i의 위치를 ​​발견된 패턴으로 표시

완료

끝

이 알고리즘은 검색 결과를 출력으로 제공하는 데 도움이 되기 때문에 컴퓨터 과학에서 매우 중요한 알고리즘입니다.

읽기 : 당신이 알아야 할 AI 알고리즘의 유형

Python에서 순진한 문자열 일치의 예

다음은 파이썬 코드에서 순진한 패턴 검색 접근 방식을 사용하는 예입니다.

# 순진한 문자열 매칭을 위한 파이썬 프로그램

# 검색 알고리즘

def search(P, T):

X = 렌(P)

Y = 렌(T)

# P[]를 하나씩 이동하는 루프 */

범위(X – Y + 1) 의 i 에 대해 :

j = 0

# 현재 인덱스 i의 경우 확인

# 패턴 일치를 위해 */

범위(0, X) 의 j 에 대해 :

if (txt[i + j] ! = P[j]):

부서지다

if (j == X – 1):

print ("위치에서 찾은 패턴", i)

# 드라이버 코드

__name__ == '__main__'인 경우 :

T = "업그레이드두부뿌그라아부그라데두"

P = "업그레이드"

검색(P,T)

출력 :

위치 0에서 패턴 발견

위치 17에서 패턴 발견

설명: 첫 번째 위치는 0 번째 위치입니다. "UPGRAD" 패턴이 여기에서 처음 발견되었기 때문에 출력은 패턴이 위치 0에서 발견되었음을 보여줍니다.

유사하게, 다음 패턴은 위치 17에서 발견되었습니다.

순진한 패턴 검색의 모범 사례

두 개의 최악의 경우와 달리 순진한 패턴 검색 알고리즘에 대한 최상의 경우는 하나만 있습니다.

가장 좋은 경우는 패턴 텍스트의 첫 번째 문자가 입력 문자열의 아무 곳에도 없을 때 발생합니다.

예시:

T [] = "UPGRADEDUHIJKLUPGRA";

P [] = "투그라";

따라서 패턴이 일치하는 경우의 수는 O(n)입니다.

순진한 패턴 검색의 최악의 경우

순진한 문자열 검색 접근 방식에는 두 가지 최악의 경우가 있습니다.

1. 패턴의 모든 문자가 입력 문자열의 문자와 동일한 경우.

T [] = "이에에에에에에에에에에에에에에

P [] = "EEE";

1. 패턴의 마지막 문자만 입력 문자열과 다른 경우.

T [] = "이에에에에에에에에에에에에에에에에에에에에에에에에에에에에에

P [] = "EEEED";

이 경우 비교 횟수는 O(m*(n-m+1))입니다.

순진한 문자열 매칭 알고리즘의 특징

문자열 일치 알고리즘은 텍스트에서 주어진 패턴의 모든 발생을 찾기 위한 것입니다.

다음은 알고리즘의 주요 기능입니다.

1. 입력 텍스트에서 패턴을 찾는 가장 간단한 방법입니다. 주어진 문자열에서 모든 문자를 하나씩 확인합니다.
2. 패턴이 더 많거나 더 정확하게 일치하는 정확한 문자열 일치를 찾습니다.
3. 작은 글씨가 있을 때 더 많이 사용합니다. 또한 전처리 단계가 필요하지 않습니다.
4. 이 검색 방법은 문자열에서 패턴을 찾고 작동하는 데 추가 공간을 차지하지 않습니다.

더 읽어보기: Python의 데이터 구조 및 알고리즘

순진한 패턴 검색의 장점

1. 순진한 검색 접근 방식에서는 실행 시간이 일치 시간과 같기 때문에 사전 처리 단계가 필요하지 않습니다.
2. 추가 작업 공간이 필요하지 않습니다.
3. 문자열과 패턴의 비교는 임의의 순서로 수행할 수 있습니다.

순진한 문자열 매칭의 단점

순진한 문자열 일치 접근 방식에는 비효율적이라는 단 하나의 단점이 있습니다. 위치를 찾았을 때 다른 위치를 찾는 데 다시 사용하지 않기 때문입니다. 시작점으로 돌아가서 다시 패턴을 찾습니다. 따라서 이전 교대조의 정보를 다시 사용하지 않습니다.

결론

순진한 문자열 일치 알고리즘은 사전 처리 요구 사항, 작업을 위한 추가 공간 없음 등과 같은 다양한 이유로 주어진 텍스트에서 해당 패턴의 위치를 ​​찾는 데 가장 선호되는 접근 방식입니다. 그러나 더 큰 텍스트에는 사용할 수 없습니다. 대규모 작업을 더 빠르게 수행하기 위한 비효율성 때문입니다.

이 게시물이 파이썬의 순진한 패턴 검색 접근 방식에 대해 실질적으로 좋은 아이디어를 주었기를 바랍니다. 이 접근 방식의 사용에 대해 배우고 주제에 대한 더 넓은 이해를 얻으려면 upGrad의 전문가에게 문의하십시오. 우리는 기술을 확장하려는 개인을 위해 특별히 설계된 과정을 제공합니다. 오늘 저희에게 연락하십시오!

AI, 기계 학습에 대해 자세히 알아보려면 IIIT-B & upGrad의 기계 학습 및 AI PG 디플로마를 확인하십시오. 기계 학습 및 AI는 일하는 전문가를 위해 설계되었으며 450시간 이상의 엄격한 교육, 30개 이상의 사례 연구 및 과제를 제공합니다. IIIT-B 동문 자격, 5개 이상의 실용적인 실습 캡스톤 프로젝트 및 최고의 기업과의 취업 지원.