Hahmonsovitusalgoritmit

Hahmonsovitus (engl. pattern matching) voidaan määritellä seuraavasti:

Olkoon $S=s_1s_2s_3 ... s_n \in \Sigma^*$ merkkijono (teksti) ja $P=p_1p_2p_3 ... p_m \in \Sigma^*$ toinen merkkijono (hahmo) aakkostossa $\Sigma$. Hahmontunnistuksen tavoitteena on selvittää, sisältääkö $S$ osajononaan $P$:n eli onko $S$ muotoa $S=S'PS''$ jollain merkkijonoilla $S', S''$. Tekstihaun sovellutuksissa $m$ on yleensä varsin pieni (alle 256 merkkiä), kun taas $n$ on hyvin suuri (gigatavuja eli miljardeja merkkejä). Käytännössä hahmonsovitusalgoritmien tehokkuuteen vaikuttaa $n$:n ja $m$:n lisäksi myös aakkoston koko $\vert\Sigma\vert$ (eli kaikkien mahdollisten merkkien lukumäärä). Kansainvälisissä merkistöissä, kuten unicode [uni96], on kymmeniätuhansia symboleja. Ainoastaan Euroopassa ja Yhdysvalloissa selvitään 8-bittisillä merkistökoodauksilla.

Tehtäessä tekstihakua hahmonsovitusalgoritmeja käyttäen ajatellaan avainsanojen olevan hahmoja ja dokumenttikokoelman olevan teksti.

Tässä luvussa on lähteenä käytetty kirjoja [CR94] ja [FBY92], sekä Jorma Tarhion merkkijonomenetelmien kurssin luentomonistetta syksyltä 1994.