Pretraga steka
Pretraga steka (takođe poznata kao algoritam za dekodiranje steka) je algoritam za pretragu sličan bim pretrazi. Može se koristiti za istraživanje mesta za pretragu drvolikih struktura i često se koristi u aplikacijama Procesiranja prirodnih jezika, kao što je raščlanjivanje jezika, ili za dekodiranje koda za ispravljanje grešaka tehnikom koja se naziva sekvencijalno dekodiranje.
Pretraga steka sadrži listu sačinjenu od najboljih n kandidata koji su do sada viđeni. Ovi kandidati su nepotpuna rešenja problema pretrage, poznatih kao, parcijalno parsiranih stabala. Zatim iterativno širi najbolje parcijalno rešenje, stavljajući sve rezultujuće parcijalne na stek a onda skraćuje listu rezultata parcijalnih rešenja na top n kandidata, dok se pravo rešenje ne pronađe.
Pretraga steka neće vam garantovano pronaći optimalno rešenje za problem pretrage. Kvalitet rezultata zavisi od kvaliteta heuristike pretrage.
Reference
[uredi | uredi izvor]Primeri aplikacija koji koriste algoritme za pretragu steka se mogu naći u literaturi:
- Frederick Jelinek. Fast sequential decoding algorithm using a stack. IBM Journal of Research and Development, pp. 675-685, 1969.
- Ye-Yi Wang and Alex Waibel. Decoding algorithm in statistical machine translation. Proceedings of the 8th conference on European chapter of the Association for Computational Linguistics, pp. 366-372. Madrid, Spain, 1997.