Поиск по стеку (также известный как алгоритм декодирования стека ) - это алгоритм поиска, похожий на поиск луча . Его можно использовать для исследования пространств поиска с древовидной структурой и часто используется в приложениях обработки естественного языка , таких как синтаксический анализ естественных языков или для декодирования кодов с исправлением ошибок, где метод называется последовательным декодированием .
Поиск по стеку содержит список из n лучших кандидатов, замеченных на данный момент. Эти кандидаты являются неполными решениями проблем поиска, например, частичные деревья синтаксического анализа. Затем он итеративно расширяет лучшее частичное решение, помещая все результирующие частичные решения в стек, а затем усекая результирующий список частичных решений до первых n кандидатов, пока не будет найдено реальное решение (то есть полное дерево синтаксического анализа).
Поиск по стеку не гарантирует нахождение оптимального решения проблемы поиска. Качество результата зависит от качества эвристики поиска.
Рекомендации
Примеры применения алгоритма поиска в стеке можно найти в литературе:
- Фредерик Елинек. Алгоритм быстрого последовательного декодирования с использованием стека . Журнал исследований и разработок IBM, стр. 675-685, 1969.
- Е-И Ван и Алекс Вайбель. Алгоритм декодирования в статистическом машинном переводе . Материалы 8-й конференции Европейского отделения Ассоциации компьютерной лингвистики, стр. 366-372. Мадрид, Испания, 1997 год.