Algoritm naiv de potrivire a șirurilor în Python: exemple, caracteristici și avantaje și dezavantaje

Când este nevoie de a găsi un model de intrare într-un șir de caractere, codificatorii și programatorii folosesc algoritmul de potrivire a șirurilor. De obicei, în cazul unui șir scurt, programatorii python preferă să folosească abordarea naivă în care programul verifică fiecare poziție din șirul de intrare pentru modelul de interogare. În cazul în care se potrivește, a dat o ieșire cu numărul poziției.

Unul dintre cele mai mari motive pentru care se folosește algoritmul naiv de potrivire a șirurilor este că este rapid și oferă rezultate destul de precise. În plus, nu necesită preprocesare. În orice caz, vom discuta despre aceste avantaje într-o etapă ulterioară în această postare. Să înțelegem mai întâi algoritmul de căutare a modelelor folosind abordarea naivă.

Algoritmul naiv de căutare a modelelor

În căutarea naivă a modelului de șir, programul testează poziția modelului de intrare P [1……i] într-un șir de caractere T [1…..m].

Rețineți că lungimea textului sau șirului introdus va fi întotdeauna mai mare sau egală cu cea a modelului.

Iată algoritmul naiv de căutare a modelelor pentru diferite limbaje de programare.

Începe

pat = model Size

str = dimensiunea șirului

pentru i = 0 la (str – pat), do

pentru j = 0 pentru a pat, face

dacă text[i+j] ≠ model[j], atunci

rupe bucla

Terminat

dacă j == pat, atunci

afișați poziția lui i ca model găsit

Terminat

Sfârșit

Acest algoritm este unul destul de important în informatică, deoarece ajută la obținerea rezultatelor căutării ca rezultat.

Citiți: Tipuri de algoritmi AI pe care ar trebui să le cunoașteți

Exemple de potrivire naivă de șiruri pe Python

Iată un exemplu în care abordarea naivă de căutare a modelelor este utilizată într-un cod python.

# Program Python pentru potrivirea șirurilor naive

# Algoritm de căutare

căutare def (P, T):

X = len(P)

Y = len(T)

# O buclă pentru a schimba P[] unul câte unul */

pentru i în interval (X – Y + 1):

j = 0

# Pentru indexul i actual, verificați

# pentru potrivirea modelului */

pentru j în intervalul (0, X):

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

pauză

dacă (j == X – 1):

imprimare („Model găsit în poziție”, i)

# Cod șofer

if __name__ == '__main__':

T = „UPGRADEDUBUPGRAABUPGRADEDU”

P = „ACTUALIZARE”

căutare (P, T)

Ieșire :

Model găsit la poziția 0

Model găsit la poziția 17

Explicație: Prima poziție este a 0- a poziție. Deoarece modelul „UPGRAD” a fost observat pentru prima dată aici, rezultatul a arătat că modelul se găsește în poziția 0.

În mod similar, următorul model a fost găsit la poziția 17.

Cel mai bun caz de căutare naivă de modele

Există doar un singur caz cel mai bun pentru algoritmul de căutare a modelului naiv, spre deosebire de cele mai rele două cazuri.

Cel mai bun caz apare atunci când primul caracter din textul modelului nu se află nicăieri în șirul de intrare.

Exemplu:

T [] = „UPGRADEDUHIJKLUPGRA”;

P [] = „TUPGRA”;

Și, prin urmare, numărul de modele de potrivire caz este O(n).

Cel mai rău caz de căutare naivă de modele

Există două cazuri cele mai grave în abordarea naivă a căutării șirurilor.

1. Când toate caracterele din model sunt aceleași cu cele din șirul de intrare.

T [] = „EEEEEEEEEEEEEEEE”;

P [] = „EEE”;

1. Când doar ultimul caracter din model diferă de șirul de intrare.

T [] = „EEEEEEEEEEED”;

P [] = „EEEED”;

În astfel de cazuri, numărul de comparații în O(m*(n-m+1)).

Caracteristicile algoritmului de potrivire a șirurilor naive

Algoritmul de potrivire a șirurilor este menit să găsească toate aparițiile unui model dat într-un text.

Iată care sunt caracteristicile de top ale algoritmului.

1. Este cea mai simplă metodă dintre toate de a căuta modele într-un text introdus. Verifică toate caracterele unul câte unul din șirul de caractere dat.
2. Găsește potrivirile exacte ale șirului – fie că este vorba de apariții mai exacte sau mai exacte ale modelului.
3. Este mai folosit când există text mic. În plus, nu necesită nicio etapă de preprocesare.
4. Această metodă de căutare nu ocupă spațiu suplimentar pentru a lucra și a căuta modelele din șir.

Citiți și: Structura datelor și algoritmul în Python

Avantajele căutării naive de modele

1. Nu sunt necesare faze de preprocesare în abordarea căutării naive, deoarece timpul de rulare al acesteia este egal cu timpul de potrivire.
2. Nu este nevoie de spațiu suplimentar de operare.
3. Comparațiile tiparelor cu șirurile se pot face în orice ordine.

Dezavantajele potrivirii naive șiruri

Există un singur dezavantaj al abordării naive de potrivire a șirurilor, și anume că este ineficientă. Acest lucru se datorează faptului că atunci când a găsit o poziție, nu o mai folosește pentru a găsi cealaltă poziție. Se întoarce la punctul de plecare și caută din nou modelul. Și astfel, nu folosește din nou informațiile din tura precedentă.

Concluzie

Algoritmul naiv de potrivire a șirurilor este abordarea cea mai preferată pentru a găsi pozițiile respectivelor modele într-un text dat din diverse motive, cum ar fi nicio cerință de pre-procesare, nici spațiu suplimentar pentru operare etc. Cu toate acestea, nu poate fi utilizat pentru texte destul de mari, deoarece a ineficienței sale de a efectua operațiuni mari mai rapid.

Sperăm că această postare v-a oferit o idee substanțial bună despre abordarea naivă de căutare a modelelor în python. Pentru a afla despre utilizările acestei abordări și pentru a obține o înțelegere mai largă a subiectului, luați legătura cu experții de la upGrad. Avem cursuri special concepute pentru persoanele care doresc să-și extindă setul de abilități. Contactează-ne astăzi!

Dacă sunteți interesat să aflați mai multe despre AI, învățarea automată, consultați Diploma PG de la IIIT-B și upGrad în Învățare automată și AI, care este concepută pentru profesioniști care lucrează și oferă peste 450 de ore de formare riguroasă, peste 30 de studii de caz și sarcini, Statut de absolvenți IIIT-B, peste 5 proiecte practice practice și asistență pentru locuri de muncă cu firme de top.