Proiect Analiza Algoritmilor
Algoritmii care vor fi descrişi au o istorie interesantă ce va fi rezumată īn cele ce urmează.
Există un algoritm naiv de procesare a şirurilor (algoritmul forţei brute) care este folosit pe scară largă. Cu toate că are un timp de execuţie īn cazul cel mai defavorabil proporţional cu MN ( algoritmul are complexitate Θ(MN) ), şirurile care apar īn multe aplicaţii conduc la un timp de execuţie care este practic proporţional cu M + N. Mai mult decāt atāt, o versiune optimizată pune la dispoziţie un "standard" care este dificil de "īnvins" cu un algoritm inteligent.
Īn 1970, S. A. Cook a demonstrat un rezultat teoretic cu privire la un tip particular de maşină abstractă, rezultat care arăta existenţa unui algoritm pentru rezolvarea problemei potrivirii şabloanelor cu timpul de execuţie īn cel mai defavorabil caz proporţional cu M + N. Donald E. Knuth şi V. R. Pratt au urmărit construcţia folosită de Cook pentru demonstrarea teoremei (care nu intenţiona să fie neapărat practică) şi au obţinut un algoritm pe care l-au rafinat īntr-o formă relativ simplă, practică. Acesta părea un rar şi satisfăcător exemplu de rezultat teoretic, cu aplicabilitate practică. Dar s-a dovedit că J. H. Morris a descoperit practic acelaşi algoritm ca o soluţie la o problemă practică enervantă cu care se confruntase cānd implementa un editor de text (nu dorea să se "īntoarcă" mereu īn text). Īn orice caz, faptul că acelaşi algoritm a fost descoperit din două abordări aşa de diferite a dus la creşterea credibilităţii ca o soluţie fundamentală pentru problemă.
Knuth, Morris şi Pratt nu au publicat nimic pānă īn 1976, şi īntre timp R. S. Boyer şi J. S. Moore (şi independent, R. W. Gosper ) au descoperit un algoritm care este mult mai rapid īn multe situaţii, din moment ce examinează numai o fracţiune din caracterele din şir. Multe editoare de text folosesc acest algoritm pentru a obţine timpi de răspuns buni pentru căutări pe şiruri.
Ambii algoritmi (Knuth - Morris - Pratt şi Boyer - Moore) necesită preprocesări relativ complicate asupra şablonului care pot fi dificil de īnţeles şi care au limitat măsura īn care sunt aplicate. De fapt, se pare că un programator de sistem a considerat algoritmul lui Morris prea dificil de īnţeles şi l-a īnlocuit cu algoritmul forţei brute.
Īn 1980, R. M. Karp şi M. O. Rabin au observat că problema nu este aşa de diferită faţă de problema clasică de căutare după cum păruse, şi au inventat un algoritm aproape la fel de simplu ca cel al forţei brute, care are un timp de execuţie practic īntotdeauna proporţional cu M + N. Īn plus, acest algoritm se extinde uşor īn cazul şabloanelor şi textelor "bidimensionale", fapt care-l face mai util decāt celelalte īn procesarea imaginilor.
Această istorie ilustrează faptul că interesul pentru un "algoritm mai bun" este īncă justificat; īntr-adevăr, se crede că pe viitor se vor putea dezvolta algoritmi "superiori" chiar pentru această problemă.