Algoritmo di corrispondenza delle stringhe ingenuo in Python: esempi, in primo piano e pro e contro

Quando è necessario trovare un modello di input in una stringa di caratteri, i programmatori e i programmatori utilizzano l'algoritmo di corrispondenza delle stringhe. Di solito, nel caso di una stringa corta, i programmatori python preferiscono utilizzare l'approccio ingenuo in cui il programma controlla ogni posizione nella stringa di input per il modello di query. In caso di corrispondenza, fornisce un output con il numero di posizione.

Uno dei motivi principali per cui viene utilizzato un algoritmo di corrispondenza delle stringhe ingenuo è perché è veloce e produce risultati abbastanza accurati. Inoltre, non richiede pre-elaborazione. In ogni caso, discuteremo di questi vantaggi in una fase successiva in questo post. Per prima cosa comprendiamo l'algoritmo per la ricerca di modelli utilizzando l'approccio ingenuo.

Algoritmo di ricerca del modello ingenuo

Nella ricerca ingenua del pattern di stringhe, il programma verifica la posizione del pattern di input P [1……i] in una stringa di caratteri T [1…..m].

Si noti che la lunghezza del testo o della stringa di input sarà sempre maggiore o uguale a quella del modello.

Ecco l'ingenuo algoritmo di ricerca del modello per diversi linguaggi di programmazione.

Inizio

pat = modello Taglia

str = dimensione della stringa

per i = da 0 a (str – pat), do

per j = 0 accarezzare, fare

se testo[i+j] ≠ modello[j], allora

rompere il ciclo

fatto

se j == pat, allora

visualizzare la posizione di i come modello trovato

fatto

Fine

Questo algoritmo è piuttosto importante nell'informatica, poiché aiuta a fornire risultati di ricerca come output.

Leggi: Tipi di algoritmi AI che dovresti conoscere

Esempi di corrispondenza di stringhe naive su Python

Ecco un esempio in cui l'approccio ingenuo di ricerca del modello viene utilizzato in un codice di Python.

# Programma Python per Naive String Matching

# Algoritmo di ricerca

def ricerca(P, T):

X = len(P)

Y = len(T)

# Un ciclo per spostare P[] uno per uno */

per i nell'intervallo (X – Y + 1):

j = 0

# Per l'indice i corrente, controllare

# per la corrispondenza del modello */

per j nell'intervallo (0, X):

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

rottura

se (j == X – 1):

print (“Schema trovato in posizione”, i)

# Codice del conducente

if __name__ == '__main__':

T = “UPGRADEDUBUPGRAABUPGRADEDU”

P = "AGGIORNAMENTO"

cerca(P, T)

Uscita :

Schema trovato alla posizione 0

Schema trovato alla posizione 17

Spiegazione: La prima posizione è la 0 a posizione. Poiché il modello "UPGRAD" è stato individuato per la prima volta qui, l'output ha mostrato che il modello si trova nella posizione 0.

Allo stesso modo, il modello successivo è stato trovato nella posizione 17.

Il miglior caso di ricerca di modelli ingenui

C'è solo un caso migliore per l'algoritmo di ricerca di pattern ingenuo, a differenza dei due casi peggiori.

Il caso migliore si verifica quando il primo carattere nel testo del modello non si trova da nessuna parte nella stringa di input.

Esempio:

T [] = “UPGRADEDUHIJKLUPGRA”;

P [] = “TUPGRA”;

E quindi, il numero di casi di modelli corrispondenti è O(n).

Il peggior caso di ricerca di modelli ingenui

Ci sono due casi peggiori nell'approccio ingenuo della ricerca di stringhe.

1. Quando tutti i caratteri nel modello sono gli stessi della stringa di input.

T [] = “EEEEEEEEEEEEEEEEEE”;

P [] = “AEE”;

1. Quando solo l'ultimo carattere nel modello differisce dalla stringa di input.

T [] = “EEEEEEEEEEED”;

P [] = “EEED”;

In questi casi, il numero di confronti in O(m*(n-m+1)).

Caratteristiche dell'algoritmo di corrispondenza delle stringhe ingenuo

L'algoritmo di corrispondenza delle stringhe è pensato per trovare tutte le occorrenze di un determinato modello in un testo.

Ecco le caratteristiche principali dell'algoritmo.

1. È il metodo più semplice tra tutti per cercare i modelli in un testo di input. Controlla tutti i caratteri uno per uno nella stringa di caratteri data.
2. Trova le corrispondenze esatte della stringa, siano esse più o più esatte occorrenze del modello.
3. È più usato quando c'è del testo piccolo. Inoltre, non necessita di alcuna fase di pre-lavorazione.
4. Questo metodo di ricerca non occupa spazio aggiuntivo per lavorare e cercare i modelli nella stringa.

Leggi anche: Struttura dei dati e algoritmo in Python

Vantaggi della ricerca di modelli ingenui

1. Non ci sono fasi di pre-elaborazione richieste nell'approccio di ricerca ingenuo, poiché il suo tempo di esecuzione è uguale al tempo di corrispondenza.
2. Non è necessario spazio operativo aggiuntivo.
3. I confronti dei modelli con le stringhe possono essere eseguiti in qualsiasi ordine.

Svantaggi dell'abbinamento ingenuo delle stringhe

C'è solo uno svantaggio dell'approccio ingenuo di corrispondenza delle stringhe, che è che è inefficiente. Questo perché quando ha trovato una posizione, non la usa più per trovare l'altra posizione. Ritorna al punto di partenza e cerca di nuovo il modello. E quindi, non utilizza nuovamente le informazioni del turno precedente.

Conclusione

L'ingenuo algoritmo di corrispondenza delle stringhe è l'approccio più preferito per trovare le posizioni di detti modelli in un dato testo per vari motivi come nessun requisito di pre-elaborazione, nessuno spazio aggiuntivo per le operazioni, ecc. Tuttavia, non può essere utilizzato per testi piuttosto grandi perché della sua inefficienza per eseguire più velocemente grandi operazioni.

Speriamo che questo post ti abbia dato un'idea sostanzialmente buona sull'approccio ingenuo di ricerca di modelli in Python. Per conoscere gli usi di questo approccio e ottenere una comprensione più ampia dell'argomento, contatta gli esperti di upGrad. Abbiamo corsi appositamente progettati per le persone che desiderano ampliare le proprie competenze. Contattaci oggi stesso!

Se sei interessato a saperne di più sull'IA e sull'apprendimento automatico, dai un'occhiata al Diploma PG di IIIT-B e upGrad in Machine Learning e AI, progettato per i professionisti che lavorano e offre oltre 450 ore di formazione rigorosa, oltre 30 casi di studio e incarichi, Status di Alumni IIIT-B, oltre 5 progetti pratici pratici e assistenza sul lavoro con le migliori aziende.