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

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.