A new optimal algorithm for the solution of a generalised assignment problem-application in automatic text alignment

A new optimal algorithm is presented, which is a modification of the Viterbi algorithm (VA), that produces the optimum (in a maximum likelihood sense) set of connections between the entries of two not necessarily aligned vectors. Each connection may treat single entries of the two vectors or groups of (not necessarily consecutive) entries, and therefore the two vectors need not be of the same length. The proposed algorithm is described, its complexity is evaluated and potential applications are proposed from the area of natural language processing (NLP)