A polynomial-order algorithm for optimal phrase sequence selection from a phrase lattice and its parallel layered implementation
Kazuhiko Ozeki · 1990
This paper deals with a problem of selecting an optimal phrase sequence from a phrase lattice, which is often encountered in language processing such as word processing and post-processing for speech recognition. The problem is formulated as one of combinatorial optimization and a polynomial order algorithm is derived. This algorithm finds an optimal phrase sequence and its dependency structure simultaneously, and is therefore particularly suited for an interface between speech recognition and various language processing. What the algorithm does is numerical optimization rather than symbolic operation unlike conventional parsers. A parallel and layered structure to implement the algorithm is also presented. Although the language taken up here is Japanese, the algorithm can be extended to cover a wider family of languages.