Pattern Matching on laajalti käytössä tietojenkäsittelytieteessä ja monilla muilla aloilla. Pattern Matching -algoritmeja käytetään kuvioiden etsimiseen suuremmasta tekstistä tai tietojoukosta. Yksi suosituimmista kuvioiden yhteensovittamisen algoritmeista on Boyer-Moore Algoritmi, joka julkaistiin ensimmäisen kerran vuonna 1977. Tässä artikkelissa keskustelemme kuvioiden täsmäysalgoritmeista C:ssä ja niiden toiminnasta.
Mikä on kuvioiden sovitusalgoritmi?
Pattern Matching -algoritmeja käytetään kuvioiden etsimiseen suuremmasta data- tai tekstijoukosta. Nämä algoritmit toimivat vertaamalla kuviota suurempaan tietojoukkoon tai tekstiin ja määrittämällä, onko kuvio olemassa vai ei. Pattern Matching -algoritmit ovat tärkeitä, koska niiden avulla voimme etsiä malleja suurista tietojoukoista nopeasti.
kartan iterointi javassa
Brute Force Pattern Matching Algorithm:
Brute Force Pattern Matching on yksinkertaisin kuvioiden sovitusalgoritmi. Se sisältää kuvion merkkien vertaamisen tekstin merkkeihin yksitellen. Jos kaikki merkit täsmäävät, algoritmi palauttaa kuvion aloituspaikan tekstissä. Jos ei, algoritmi siirtyy seuraavaan kohtaan tekstissä ja toistaa vertailua, kunnes osuma löytyy tai tekstin loppu on saavutettu. Brute Force -algoritmin aika monimutkaisuus on O(MXN) , missä M ilmaisee tekstin pituuden ja N ilmaisee kuvion pituuden.
Naiivin kuvion sovitusalgoritmi:
Naive Pattern Matching -algoritmi on parannus brute Force -algoritmiin verrattuna. Se välttää turhat vertailut ohittamalla joitain kohtia tekstistä. Algoritmi aloittaa kuvion vertaamisen ensimmäisessä kohdassa olevaan tekstiin. Jos merkit täsmäävät, se siirtyy seuraavaan kohtaan ja toistaa vertailun. Jos merkit eivät täsmää, algoritmi siirtyy seuraavaan kohtaan tekstissä ja vertaa kuviota uudelleen tekstiin. Naive-algoritmin aikamonimutkaisuus on myös O(MXN) , mutta se on nopeampi kuin Brute Force -algoritmi useimmissa tapauksissa.
Knuth-Morris-Pratt-algoritmi:
The Knuth-Morris-Pratt (KMP) Algorithm on kehittyneempi Pattern Matching -algoritmi. Se perustuu havaintoon, että epäsuhtautuessa voidaan käyttää jotakin tietoa tekstistä ja kuviosta tarpeettomien vertailujen välttämiseksi. Algoritmi laskee valmiiksi taulukon, joka sisältää tietoja kuviosta. Taulukko määrittää, kuinka monta merkkiä kuviosta voidaan ohittaa, kun epäsuhta ilmenee. Aika monimutkaisuus KMP algoritmi on O(M+N) .
Boyer-Mooren algoritmi:
Yksi suosituimmista Pattern Matching-algoritmeista on Boyer-Moore algoritmi. Tämän algoritmin julkaisivat ensimmäisen kerran vuonna 1977 Robert S. Boyer ja J Strother Moore. The Boyer-Moore algoritmi vertaa kuviota suurempaan tieto- tai tekstijoukkoon oikealta vasemmalle eikä vasemmalta oikealle, kuten useimmat muut kuvionsovitusalgoritmit.
The Boyer-Moore Algoritmissa on kaksi pääkomponenttia: huono merkkisääntö ja hyvän jälkiliitteen sääntö. Virheellisen merkin sääntö toimii vertaamalla kuviossa olevaa merkkiä datan tai tekstin vastaavaan merkkiin. Jos merkit eivät täsmää, algoritmi siirtää kuviota oikealle, kunnes se löytää sopivan merkin. Hyvä suffiksisääntö vertaa kuvion päätettä vastaavaan datan tai tekstin pääteeseen. Jos jälkiliitteet eivät täsmää, algoritmi siirtää kuviota oikealle, kunnes se löytää vastaavan päätteen.
The Boyer-Moore Algoritmi tunnetaan tehokkuudestaan ja sitä käytetään laajasti monissa sovelluksissa. Sitä pidetään yhtenä nopeimmista saatavilla olevista kuvionsovitusalgoritmeista.
Boyer-Moore-algoritmin toteuttaminen C:ssä:
Toteuttaaksesi Boyer-Moore Algoritmi C:ssä, voimme aloittaa määrittelemällä huonon merkin säännön. Voimme käyttää taulukkoa tallentaaksemme kunkin kuvion merkin viimeisen esiintymän. Tämä taulukko voi määrittää, kuinka pitkälle kuviota on siirrettävä oikealle, kun epäsuhta ilmenee.
Tässä on esimerkki siitä, kuinka voimme toteuttaa huonojen merkkien säännön C:ssä:
milloin win 7 ilmestyi
C-koodi:
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>