Musterotsimisalgoritmid

Musterotsimisalgoritmid on arvutiteaduses algoritmide kogum, mida kasutatakse andmestruktuuris, näiteks tekstis või pildis, kindla mustri leidmiseks. Musterotsingu peamine eesmärk on tuvastada, kas antud muster esineb andmestruktuuris ja kus see täpselt asub.

Lihtsaim ja intuitiivseim musterotsingu algoritm on naivne või brute-force meetod. See meetod võrdleb mustrit iga võimaliku algusasendiga andmestruktuuris. Kui mustri pikkus on m ja andmestruktuuri pikkus on n, siis selle algoritmide ajaline keerukus on O(nm) halvimal juhul.

Mõned levinumad ja tõhusamad musterotsimisalgoritmid on KMP (Knuth-Morris-Pratt) algoritm ja Boyer-Moore algoritm. KMP algoritm kasutab täiustatud eeltöötlust, et vältida tarbetuid võrdlusi, kui muster ei ühti. See saavutab O(n+m) ajalise keerukuse. Boyer-Moore algoritm on sageli veelgi kiirem praktikas, töötades keskmiselt O(n/m) ja halvimal juhul O(nm), kuid selle optimeeritud versioonid saavutavad ka O(n+m).

Lisaks nendele on olemas ka regulaaravaldiste (regular expressions) otsimiseks mõeldud algoritmid, mis kasutavad regulaaravaldiste automaate. Need on eriti võimsad keerukate mustrite otsimisel.

Musterotsimisalgoritme kasutatakse laialdaselt erinevates rakendustes, sealhulgas tekstiredaktorites, otsingumootorites, viirusetõrjes, bioinformaatikas ja pilditöötluses.