Patent ID: 6917936

Claim:
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 intermediate 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 intermediate values for the measure of similarity using the recursive formulation within which functions are computed following a computation order defined using nested loops that include: an outer loop with a first index that ranges over increasing sums of prefix lengths of the first sequence of symbols and the second sequence of symbols, a middle loop with a second index 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 with a third index 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 computed using the intermediate values.