Algoritmo de correspondência de string ingênuo em Python: exemplos, destaques e prós e contras

Quando há necessidade de encontrar um padrão de entrada em uma sequência de caracteres, codificadores e programadores usam o algoritmo de correspondência de sequência. Normalmente, no caso de uma string curta, os programadores python preferem usar a abordagem ingênua na qual o programa verifica cada posição na string de entrada para o padrão de consulta. Caso corresponda, deu uma saída com o número da posição.

Uma das maiores razões pelas quais o algoritmo de correspondência de string ingênuo é usado é porque ele é rápido e produz resultados bastante precisos. Além disso, não requer pré-processamento. De qualquer forma, discutiremos essas vantagens em um estágio posterior deste post. Vamos primeiro entender o algoritmo para busca de padrões usando a abordagem ingênua.

Algoritmo de pesquisa de padrão ingênuo

Na busca do padrão de string ingênuo, o programa testa a posição do padrão de entrada P [1……i] em uma string de caracteres T [1…..m].

Observe que o comprimento do texto ou string de entrada sempre será maior ou igual ao do padrão.

Aqui está o algoritmo de busca de padrões ingênuos para diferentes linguagens de programação.

Começar

pat = tamanho do padrão

str = tamanho da string

para i = 0 a (str – pat), faça

para j = 0 para pat, faça

se texto[i+j] ≠ padrão[j], então

quebrar o laço

feito

se j == pat, então

exibir a posição de i como padrão encontrado

feito

Fim

Esse algoritmo é bastante importante na ciência da computação, pois ajuda a fornecer resultados de pesquisa como saída.

Leia: Tipos de algoritmos de IA que você deve conhecer

Exemplos de correspondência de string ingênua em Python

Aqui está um exemplo em que a abordagem de pesquisa de padrão ingênuo é usada em um código de python.

# Programa Python para Naive String Matching

# Algoritmo de busca

def pesquisa(P, T):

X = len(P)

Y = len(T)

# Um loop para deslocar P[] um por um */

para i no intervalo (X – Y + 1):

j = 0

# Para o índice atual i, verifique

# para correspondência de padrões */

para j no intervalo (0, X):

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

pausa

se (j == X – 1):

print (“Padrão encontrado na posição “, i)

# Código do motorista

if __name__ == '__main__':

T = “UPGRADUBUPGRAABUPGRADEDU”

P = “ATUALIZAR”

pesquisar (P, T)

Saída :

Padrão encontrado na posição 0

Padrão encontrado na posição 17

Explicação: A primeira posição é a posição 0 . Como o padrão “UPGRAD” foi detectado pela primeira vez aqui, a saída mostrou que o padrão é encontrado na posição 0.

Da mesma forma, o próximo padrão foi encontrado na posição 17.

Melhor caso de pesquisa de padrões ingênuos

Existe apenas um melhor caso para o algoritmo de busca de padrões ingênuos, ao contrário dos dois piores casos.

O melhor caso ocorre quando o primeiro caractere no texto padrão não está em nenhum lugar na string de entrada.

Exemplo:

T [] = “UPGRADEDUHIJKLUPGRA”;

P[] = “TUPGRA”;

E, portanto, o número de casos de padrões correspondentes é O(n).

Pior caso de pesquisa de padrões ingênuos

Existem dois piores casos na abordagem de busca de strings ingênuas.

1. Quando todos os caracteres no padrão são iguais aos da string de entrada.

T [] = “EEEEEEEEEEEEEEEE”;

P[] = “EEE”;

1. Quando apenas o último caractere no padrão difere da string de entrada.

T [] = “EEEEEEEEEEED”;

P[] = “EEEED”;

Nesses casos, o número de comparações em O(m*(n-m+1)).

Recursos do Algoritmo de Correspondência de String Naive

O algoritmo de correspondência de strings destina-se a encontrar todas as ocorrências de um determinado padrão em um texto.

Aqui estão os principais recursos do algoritmo.

1. É o método mais simples entre todos para procurar padrões em um texto de entrada. Ele verifica todos os caracteres um por um na sequência de caracteres fornecida.
2. Ele encontra as correspondências exatas de string - sejam ocorrências mais ou mais exatas do padrão.
3. É mais usado quando há texto pequeno. Além disso, não requer nenhuma fase de pré-processamento.
4. Este método de pesquisa não ocupa espaço extra para trabalhar e procurar os padrões na string.

Leia também: Estrutura de dados e algoritmo em Python

Vantagens da pesquisa de padrões ingênuos

1. Não há fases de pré-processamento necessárias na abordagem de busca ingênua, pois seu tempo de execução é igual ao tempo de correspondência.
2. Não há necessidade de espaço operacional extra.
3. As comparações dos padrões com as strings podem ser feitas em qualquer ordem.

Desvantagens do Naive String Matching

Há apenas uma desvantagem da abordagem de correspondência de string ingênua, que é ineficiente. Isso porque quando encontra uma posição, não a utiliza novamente para encontrar a outra posição. Ele volta ao ponto de partida e procura o padrão novamente. E assim, não utiliza novamente as informações do turno anterior.

Conclusão

O algoritmo de correspondência de string ingênuo é a abordagem mais preferida para encontrar as posições dos referidos padrões em um determinado texto por várias razões, como nenhum requisito de pré-processamento, nenhum espaço extra para operação, etc. No entanto, ele não pode ser usado para textos muito maiores porque de sua ineficiência para realizar grandes operações mais rapidamente.

Esperamos que este post tenha lhe dado uma ideia substancialmente boa sobre a abordagem de pesquisa de padrões ingênuos em python. Para conhecer os usos dessa abordagem e obter uma compreensão mais ampla do tópico, entre em contato com os especialistas do upGrad. Temos cursos especialmente projetados para indivíduos que desejam expandir suas habilidades. Entre em contato conosco hoje!

Se você estiver interessado em aprender mais sobre IA, aprendizado de máquina, confira o Diploma PG do IIIT-B e do upGrad em aprendizado de máquina e IA, projetado para profissionais que trabalham e oferece mais de 450 horas de treinamento rigoroso, mais de 30 estudos de caso e atribuições, Status de ex-aluno do IIIT-B, mais de 5 projetos práticos práticos e assistência de trabalho com as principais empresas.