Patent ID: 6195638
Filing Date: 2001-02-27
Classification: G10L

Abstract:
A method of determining a value of lowest-weight path of a mapping between two sequences, comprising:determining a first mapping wavefront, comprising a plurality of mapping points, each mapping point corresponding to a mapping between one data-point of one sequence of said two sequences and one data-point of another of said two sequences, each mapping point having associated therewith a value;propagating the wavefront to a second plurality of mapping points;determining a value associated with each of said second plurality of mapping points, responsive to values associated with said first mapping wavefront and to mapping weights determined by said first plurality of mapping points and by said second plurality of mapping points;propagating the wavefront to a third plurality of mapping points;determining a value associated with each of said second plurality of mapping points, responsive to values associated with a previous mapping wavefront and to mapping weights determined by a plurality of mapping points associated with said previous wavefront and by said third plurality of mapping points; andre-propagating the wave front to a fourth plurality of mapping points while retaining in a memory only values of mapping points associated with a limited number of previous wavefronts, wherein said limited number is significantly smaller than a number of data points in a shorter one of said two sequences.