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