A mintaillesztést széles körben használják a számítástechnikában és sok más területen. A mintaillesztési algoritmusok nagyobb szövegen vagy adathalmazon belüli minták keresésére szolgálnak. A mintaillesztés egyik legnépszerűbb algoritmusa a Boyer-Moore Ebben a cikkben a C-ben használható mintaillesztési algoritmusokat és azok működését tárgyaljuk.
Mi az a mintaillesztési algoritmus?
A mintaillesztési algoritmusok nagyobb adat- vagy szövegkészleten belüli minták keresésére szolgálnak. Ezek az algoritmusok úgy működnek, hogy egy mintát egy nagyobb adatkészlettel vagy szöveggel hasonlítanak össze, és meghatározzák, hogy a minta jelen van-e vagy sem. A mintaillesztési algoritmusok azért fontosak, mert lehetővé teszik, hogy nagy adathalmazokban gyorsan keressünk mintákat.
javascript nyomtatás
Brute Force Pattern Matching Algorithm:
A Brute Force Pattern Matching a legegyszerűbb mintaillesztési algoritmus. Ez magában foglalja a minta karaktereinek egyenkénti összehasonlítását a szöveg karaktereivel. Ha az összes karakter egyezik, az algoritmus visszaadja a minta kezdőpozícióját a szövegben. Ha nem, akkor az algoritmus a szöveg következő helyére lép, és addig ismétli az összehasonlítást, amíg egyezést nem talál, vagy a szöveg végét el nem éri. A nyers erő algoritmus időbeli összetettsége az O(MXN) , ahol M jelöli a szöveg hosszát és N a minta hosszát jelöli.
Naiv mintaillesztési algoritmus:
A Naive Pattern Matching algoritmus továbbfejlesztése a Brute Force algoritmushoz képest. A szöveg egyes pozícióinak kihagyásával elkerüli a felesleges összehasonlításokat. Az algoritmus elkezdi összehasonlítani a mintát az első helyen lévő szöveggel. Ha a karakterek egyeznek, a következő helyre lép, és megismétli az összehasonlítást. Ha a karakterek nem egyeznek, az algoritmus a következő helyre lép a szövegben, és ismét összehasonlítja a mintát a szöveggel. A Naiv algoritmus időbeli összetettsége is O(MXN) , de a legtöbb esetben gyorsabb, mint a Brute Force algoritmus.
Knuth-Morris-Pratt algoritmus:
A Knuth-Morris-Pratt (KMP) algoritmus egy fejlettebb Pattern Matching algoritmus. Azon a megfigyelésen alapszik, hogy ha eltérés lép fel, a szöveggel és a mintával kapcsolatos információk felhasználhatók a szükségtelen összehasonlítások elkerülésére. Az algoritmus előre kiszámít egy táblázatot, amely információkat tartalmaz a mintáról. A táblázat meghatározza, hogy a minta hány karaktere ugorható át eltérés esetén. Az idő összetettsége a KMP algoritmus az O(M+N) .
A Boyer-Moore algoritmus:
Az egyik legnépszerűbb mintaillesztési algoritmus a Boyer-Moore algoritmus. Ezt az algoritmust először 1977-ben tette közzé Robert S. Boyer és J Strother Moore. A Boyer-Moore algoritmus összehasonlítja a mintát nagyobb adathalmazzal vagy szöveggel jobbról balra, nem balról jobbra, mint a legtöbb más mintaillesztő algoritmusnál.
A Boyer-Moore Az algoritmusnak két fő összetevője van: a rossz karakter szabály és a jó utótag szabály. A rossz karakter szabály úgy működik, hogy összehasonlítja a mintában szereplő karaktert az adat vagy szöveg megfelelő karakterével. Ha a karakterek nem egyeznek, az algoritmus jobbra mozgatja a mintát, amíg meg nem találja a megfelelő karaktert. A jó utótag szabálya összehasonlítja a minta utótagját az adat vagy szöveg megfelelő utótagjával. Ha az utótagok nem egyeznek, az algoritmus jobbra mozgatja a mintát, amíg meg nem találja a megfelelő utótagot.
A Boyer-Moore Az algoritmus hatékonyságáról ismert, és számos alkalmazásban széles körben használják. Ez az egyik leggyorsabb mintaillesztő algoritmusnak tekinthető.
A Boyer-Moore algoritmus implementálása C nyelven:
Végrehajtására a Boyer-Moore algoritmus C-ben, kezdhetjük a rossz karakter szabály definiálásával. Egy tömb segítségével tárolhatjuk a mintában szereplő egyes karakterek utolsó előfordulását. Ez a tömb meghatározhatja, hogy milyen messzire kell elmozdítanunk a mintát jobbra, ha eltérés lép fel.
Íme egy példa arra, hogyan valósíthatjuk meg a rossz karakter szabályt C-ben:
linux operációs rendszer
C kód:
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;>