Patent Document ID: 20040128288
Application ID: 10321869
Patent Flag: 0

Claim One:
1. A dynamic programming method for computing a measure of similarity between a first sequence of symbols and a second sequence of symbols, comprising: allocating memory for a computational unit for storing values that are computed using a recursive formulation that computes the measure of similarity based on matching subsequences of symbols between the first sequence of symbols and the second sequence of symbols; computing with a processor for the computational unit the values for the measure of similarity using the recursive formulation within which functions are computed using nested loops that include: an outer loop that ranges over increasing sums of prefix lengths of the first sequence of symbols and the second sequence of symbols, a middle loop that ranges over increasing prefixes of the first sequence of symbols, for each sum of prefix lengths of the outer loop, and an inner loop that ranges over increasing subsequence lengths, for each prefix of the first sequence of symbols of the middle loop; and outputting the measure of similarity.