Merkkijonohaku

Merkkijonohaku on tietojenkäsittelytieteen ala, jossa etsitään esiintymiä annettuun patterniin teksti- tai datajoukossa. Etsittävä malli voi olla yksittäinen merkkijono tai laajempi kuvio. Etsintä voidaan suorittaa sekä tarkasti että epätarkasti; epätarkka hakeminen sallii virheitä tai puuttuvia merkkejä, jolloin käytetään etäisyyksiä kuten Levenshtein-etäisyyttä.

Tunnettuja hakualgoritmeja ovat naive-haku, Knuth–Morris–Pratt (KMP), Boyer–Moore sekä Rabin–Karp. KMP ja Rabin–Karp ovat lineaarisia suhteessa tekstiin, kun mallin pituus on suhteellisen pieni. Boyer–Moore voi olla erittäin nopea tietyissä tapauksissa. Monien mallien hakuun käytetään Aho–Corasick -automaattia. Säännölliset lausekkeet tarjoavat korkean tason tavan määritellä hakumallit, ja niitä käytetään laajalti ohjelmoinnissa.

Sovelluksia ovat tekstinkäsittely, hakutyökalut kuten grep, tietokanta- ja tiedostohakulut sekä bioinformatiikka sekvenssien etsinnässä. Tärkeitä huomioita ovat merkkijonojen koko ja sisältö, Unicode-merkistö sekä päällekkäisten esiintymien käsittely ja case-sensitivity.

Merkkijonohaku liittyy laajemmin pattern matchingiin, regulaarilausekkeisiin ja automaattiteoriaan.