Претрага стека

Претрага стека (такође позната као алгоритам за декодирање стека) је алгоритам за претрагу сличан бим претрази. Може се користити за истраживање места за претрагу дрволиких структура и често се користи у апликацијама Процесирања природних језика, као што је рашчлањивање језика, или за декодирање кода за исправљање грешака техником која се назива секвенцијално декодирање.

Претрага стека садржи листу сачињену од најбољих n кандидата који су до сада виђени. Ови кандидати су непотпуна решења проблема претраге, познатих као, парцијално парсираних стабала. Затим итеративно шири најбоље парцијално решење, стављајући све резултујуће парцијалне на стек а онда скраћује листу резултата парцијалних решења на топ n кандидата, док се право решење не пронађе.

Претрага стека неће вам гарантовано пронаћи оптимално решење за проблем претраге. Квалитет резултата зависи од квалитета хеуристике претраге.

Референце

Примери апликација који користе алгоритме за претрагу стека се могу наћи у литератури:

• 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.