Method and apparatus for measuring similarity between documents

• US 6,917,936 B2
• Filed: 12/18/2002
• Issued: 07/12/2005
• Est. Priority Date: 12/18/2002
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Cancedda, Nicola
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): ABEL JALIL, NEVEEN
• Application Number:
  US10/321,869
• Publication Number:
  US 20040128288A1
• Time in Patent Office: 937 Days
• Field of Search: 707 1-100, 704/9, 704/10, 715/513
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A measure of similarity between a first sequence of symbols and a second sequence of symbols is computed. Memory is allocated 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. A processor computes for the computational unit the values for the measure of similarity using the recursive formulation within which functions are computed using nested loops. The measure of similarity is output by the computational unit to an information processing application.

Claims

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 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.

2. The method according to claim 1, wherein the measure of similarity is output to an information processing application.

3. The method according to claim 2, wherein the information processing application uses the measure of similarity for performing one of information clustering, classification, cross-lingual information retrieval, routing, text comparison and filtering.

4. The method according to claim 2, wherein a first function of the recursive formulation is given by:

$K_n<br><br>\left(\mathrm{sx},t\right)=K_n<br><br>\left(s,t\right)+\underset{j;<br><br>t_j=x}{\sum <br><br>}<br><br>{\mathrm{\lambda <br><br>}}^2<br><br>K_{n-1}^{\mathrm{\prime <br><br>}}<br><br>\left(s,t<br><br>\left[1;<br><br>j-1\right]\right),\mathrm{where}$

n;

is a subsequence length,

K_n;

is the measure of similarity for subsequences of length n,

s;

is any sequence of symbols,

t;

is any other sequence of symbols,

sx;

is the sequence of symbols obtained by appending the symbol x to the end of the sequence of symbols t,

λ

;

is a decay factor for penalizing matching subsequences that are noncontiguous;

t[1;

j−

1];

refers to the first j−

1 symbols of t, $\underset{j;<br><br>t_j=x}{\sum <br><br>};<br><br>$

 

is a sum that ranges over all indices j such that t_j is x,

K′

;

is a second function of the recursive formulation that is given by;

K′

_i(sx,t)=λ

K′

_i(s,t)+K′

_i(sx,t) (i=1, . . . ,n−

1), and

K″

;

is a third function of the recursive formulation that is given by;

$K_i^{\mathrm{″<br><br>}}<br><br>\left(\mathrm{sx},\mathrm{ty}\right)=\{\begin{array}{cc}\mathrm{\lambda <br><br>}<br><br>\left(K_i^{\mathrm{″<br><br>}}<br><br>\left(\mathrm{sx},t\right)+\mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>K_{i-1}^{\mathrm{\prime <br><br>}}<br><br>\left(s,t\right)\right)& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>x=y\\ \mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>K_i^{\mathrm{″<br><br>}}<br><br>\left(\mathrm{sx},t\right)& \mathrm{otherwise}.\end{array}$

5. The method according to claim 4, further comprising defining base values for the recursive formulation to be:

K″

₀(s,t)=0, for all s,t

K″

_i(s,t)=0, if min(|s|,|t|)<

i, (i=1, . . . ,n−

1)

K′

₀(s,t)=1, for all s,t,

K′

_i(s,t)=0, if min(|s|,|t|)<

i, (i=1, . . . ,n−

1)

K_n(s,t)=0, if min(|s|,|t|)<

n,

where

|s|;

is the cardinality of s, and

|t|;

is the cardinality of t.

6. The method according to claim 5, wherein the memory allocated for storing intermediate values of K′

and K″

is sufficient for storing up to (n×

|s|+n×

|t|) values in the memory.

7. The method according to claim 2, wherein ones of the matching subsequences of symbols are noncontiguous matches of symbols between the first sequence of symbols and the second sequence of symbols.

8. The method according to claim 7, wherein the noncontiguous occurrences of matching subsequences of symbols are penalized according to how many gaps exist between matching symbols.

9. The method according to claim 2, wherein the measure of similarity is computed for all possible subsequences of symbols between the first sequence of symbols and the second sequence of symbols.

10. An apparatus for computing a measure of similarity between a first sequence of symbols and a second sequence of symbols, comprising:

a memory for storing;

(a) 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, and (b) processing instructions of a computational unit for carrying out the recursive formulation; and

a processor coupled to the memory for executing the processing instructions of the computational unit;

the processor in executing the processing instructions;

computing 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 meansure of similarity computed using the intermediate values.

11. The apparatus according to claim 10, further comprising an information processing application for receiving the measure of similarity from the computational unit.

12. The apparatus according to claim 11, wherein the information processing application uses the measure of similarity for performing one of information clustering, classification, cross-lingual information retrieval, routing, text comparison and filtering.

13. The apparatus according to claim 11, wherein a first function of the recursive formulation is given by:

$K_n<br><br>\left(\mathrm{sx},t\right)=K_n<br><br>\left(s,t\right)+\underset{j;<br><br>t_j=x}{\sum <br><br>}<br><br>{\mathrm{\lambda <br><br>}}^2<br><br>K_{n-1}^{\mathrm{\prime <br><br>}}<br><br>\left(s,t<br><br>\left[1;<br><br>j-1\right]\right),\text{\hspace{1em}<br><br>}<br><br>\mathrm{where}$

n;

is a subsequence length,

K_n;

is the measure of similarity for subsequences of length n,

s;

is any sequence of symbols,

t;

is any other sequence of symbols,

sx;

is the sequence of symbols obtained by appending the symbol x to the end of the sequence of symbols t,

λ

;

is a decay factor for penalizing matching subsequences that are noncontiguous;

t[1;

j−

1];

refers to the first j−

1 symbols of t, $\underset{j;<br><br>t_j=x}{\sum <br><br>};<br><br>$

 

is a sum that ranges over all indices j such that t_j is x,

K′

;

is a second function of the recursive formulation that is given by;

K′

_i(sx,t)=λ

K′

_i(s,t)+K″

_i(sx,t) (i=1, . . . ,n−

1), and

K″

;

is a third function of the recursive formulation that is given by;

$K_i^{\mathrm{″<br><br>}}<br><br>\left(\mathrm{sx},\mathrm{ty}\right)=\{\begin{array}{cc}\mathrm{\lambda <br><br>}<br><br>\left(K_i^{\mathrm{″<br><br>}}<br><br>\left(\mathrm{sx},t\right)+\mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>K_{i-1}^{\mathrm{\prime <br><br>}}<br><br>\left(s,t\right)\right)& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>x=y\\ \mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>K_i^{\mathrm{″<br><br>}}<br><br>\left(\mathrm{sx},t\right)& \mathrm{otherwise}.\end{array}$

14. The apparatus according to claim 13, wherein base values for the recursive formulation are defined to be:

K″

₀(s,t)=0, for all s,t

K″

_i(s,t)=0, if min(|s|,|t|)<

i, (i=1, . . . ,n−

1)

K′

₀(s,t)=1, for all s,t,

K′

_i(s,t)=0, if min(|s|,|t|)<

i, (i=1, . . . ,n−

1)

K_n(s,t)=0, if min(|s|,|t|)<

n,

where

|s|;

is the cardinality of s, and

|t|;

is the cardinality of t.

15. The apparatus according to claim 14, wherein the memory allocated for storing intermediate values of K′

and K″

is sufficient for storing up to (n×

|s|+n×

|t|) values in the memory.

16. The apparatus according to claim 11, wherein ones of the matching subsequences of symbols are noncontiguous matches of symbols between the first sequence of symbols and the second sequence of symbols, and the noncontiguous occurrences of matching subsequences of symbols are penalized according to how many gaps exist between matching symbols.

17. The apparatus according to claim 11, wherein the measure of similarity is computed for all possible subsequences of symbols between the first sequence of symbols and the second sequence of symbols.

18. An article of manufacture for use in a machine comprising:

a) a memory;

b) instructions stored in the memory 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 for the computational unit with a processor 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.

19. The article of manufacture according to claim 18, wherein the measure of similarity is output to an information processing application that uses the measure of similarity for performing one of information clustering, classification, cross-lingual information retrieval, routing, text comparison and filtering.

20. The article of manufacture according to claim 19, wherein a first function of the recursive formulation is given by:

$K_n<br><br>\left(\mathrm{sx},t\right)=K_n<br><br>\left(s,t\right)+\underset{j;<br><br>t_j=x}{\sum <br><br>}<br><br>{\mathrm{\lambda <br><br>}}^2<br><br>K_{n-1}^{\mathrm{\prime <br><br>}}<br><br>\left(s,t<br><br>\left[1<br><br>\text{;<br><br>}<br><br>j-1\right]\right),\text{\hspace{1em}<br><br>}<br><br>\mathrm{where}$

n;

is a subsequence length,

K_n;

is the measure of similarity for subsequences of length n,

s;

is any sequence of symbols,

t;

is any other sequence of symbols,

sx;

is the sequence of symbols obtained by appending the symbol x to the end of the sequence of symbols t,

λ

;

is a decay factor for penalizing matching subsequences that are noncontiguous;

t[1;

j−

1];

refers to the first j−

1 symbols of t, $\underset{j;<br><br>t_j=x}{\sum <br><br>}<br><br>\text{;<br><br>}$

is a sum that ranges over all indices j such that t_j is x,

K′

;

is a second function of the recursive formulation that is given by;

K′

_i(sx,t)=λ

K′

_i(s,t)+K″

_i(sx,t) (i=1, . . . ,n−

1), and

K″

;

is a third function of the recursive formulation that is given by;

$K_i^{\mathrm{″<br><br>}}<br><br>\left(\mathrm{sx},\mathrm{ty}\right)=\{\begin{array}{cc}\mathrm{\lambda <br><br>}<br><br>\left(K_i^{\mathrm{″<br><br>}}<br><br>\left(\mathrm{sx},t\right)+\mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>K_{i-1}^{\mathrm{\prime <br><br>}}<br><br>\left(s,t\right)\right)& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>x=y\\ \mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>K_i^{\mathrm{″<br><br>}}<br><br>\left(\mathrm{sx},t\right)& \mathrm{otherwise};<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}\end{array}$

wherein base values for the recursive formulation are defined to be;

K″

₀(s,t)=0, for all s,t

K″

_i(s,t)=0, if min(|s|,|t|)<

i, (i=1, . . . ,n−

1)

K′

₀(s,t)=1, for all s,t,

K′

_i(s,t)=0, if min(|s|,|t|)<

i, (i=1, . . . ,n−

1)

K_n(s,t)=0, if min(|s|,|t|)<

n, where

|s|;

is the cardinality of s, and

|t|;

is the cardinality of t.

21. The article of manufacture according to claim 20, wherein the memory allocated for storing intermediate values of K′

and K″

is sufficient for storing up to (n×

|s|+n×

|t|) values in the memory.