Method of text similarity measurement

• US 7,346,491 B2
• Filed: 01/04/2001
• Issued: 03/18/2008
• Est. Priority Date: 01/04/2001
• Status: Expired due to Fees

• Current Assignee: Agency For Science Technology and Research
• Original Assignee: Agency For Science Technology and Research
• Inventors: Pan, Hong, Kanagasabai, Rajaraman
• Primary Examiner(s): Edouard; Patrick N.
• Assistant Examiner(s): YEN, ERIC L
• Application Number:
  US10/250,746
• Publication Number:
  US 20040088156A1
• Time in Patent Office: 2,630 Days
• Field of Search: 704/9, 715/531
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

In one aspect, the present invention provides a for estimating the similarity between at least two portions of text including the steps of forming a set of syntactic tuples, each tuple including at least two terms and a relation betweeen the two terms; classifying the relation between the terms in the tuples according to a predefined set of relations; establishing the relative agreement between syntactic tuples from the portions of text under comparison according to predefined classes of agreement; calculating a value representative of the similarity between the portions of text of each of the classes of agreement; and establishing a value for the similarity between the portions of text by calculating a weighted sum of the values representative of the similarity between the portions of text for each of the classes of agreement. Preferaly, the step of calculating a value representative of the similarity between the portions of text for each of the classes of agreement includes a weighting based upon the number of matched terms occurring in particular parts of speech in which the text occurs. It is also preferred that the step of calculating a value representative of the similarity between the portions of text for each of the classes of agreement include the application of a weighting factor to the estimate of similarity for each of the classes of agreement and the parts of speech in which matched terms occur.

Claims

1. A method for estimating the similarity between at least two portions of text, said method comprising the steps of:

receiving said at least two portions of text;

forming a set of syntactic tuples from said portions of text, each tuple comprising two terms and a relation between the two terms;

classifying the relation between the terms in the tuples according to a predefined set of relations;

predefining classes of agreement between tuples under comparison, comprising a class of full agreement wherein tuples under comparison are identical, a class of partial agreement wherein only two of corresponding elements in tuples under comparison are identical, and a class of term agreement wherein only one of corresponding terms in tuples under comparison are identical;

determining a respective class of relative agreement between each pair of syntactic tuples from the portions of text under comparison according to the predefined classes of agreement;

calculating a value representative of the similarity between the portions of text for each of the classes of agreement, based on the plurality of tuples determined to belong to the respective class of agreement; and

determining and outputting a measure of the similarity between the portions of text by calculating a weighted sum of the values representative of the similarity between the portions of text for each of the classes of agreement.

2. A method according to claim 1 wherein the step of calculating a value representative of the similarity between the portions of text for each of the classes of agreement comprises a weighting based upon the number of matched terms occurring in particular parts of speech.

3. A method according to claim 2 wherein the step of calculating a value representative of the similarity between the portions of text for each of the classes of agreement comprises the application of a weighting factor to the estimate of similarity for each of the classes of agreement and the parts of speech in which matched terms occur.

4. A method according to claim 1 wherein the syntactic tuples comprise two terms and a relation between the terms, the relation being classified according to one of the following classes:

relations between a verb and its subject;

relations between a verb and its object;

relations between a modifier and its modified word;

or

a circumstantial relationship.

5. A method according to claim 1 wherein the syntactic tuples are of the form (relation, term1, term2).

6. A method according to claim 5 wherein a syntactic tuple of a first portion of text, T_i, and a syntactic tuple of a second portion of text, T_j, are associated with the class of full agreement of syntactic tuples, class A, if and only if:

(Ti.relation==Tj.relation) AND

(Ti.term1==Tj.term1) AND

(Ti.term2==Tj.term2).

7. A method according to claim 6 wherein a syntactic tuple of a first portion of text, T_i, and a syntactic tuple of a second portion of text, T_j, are associated with the class of partial agreement of syntactic tuples, class B, if and only if:

((T_i.relation==T_j.relation) AND (T_i.term1==T_j.term1) AND (T_i.term2!=T_j.term2)) OR

((T_i.relation==T_j.relation) AND (T_i.term1!=T_j.term1) AND (T_i.term2==T_J.term2)) OR

((T_i.relation!=T_j.relation) AND (T_i.term1==T_j.term1) AND (T_i.term2==T_J.term2)).

8. A method according to claim 7 wherein a syntactic tuple of a first portion of text, T_i, and a syntactic tuple of a second portion of text, T_j, are associated with the class of term agreement of syntactic tuples, class C, if and only if:

((T_i.relation!=T_j.relation) AND (T_i.term1==T_j.term1)) AND (T_i.term2!=T_j.term2) OR

((T_i.relation!=T_j.relation) AND (T_i.term1!=T_j.term1)) AND (T_i.term2==T_j.term2).

9. A method according to claim 8 wherein a syntactic tuple of a first portion of text, T_i, and a syntactic tuple of a second portion of text, T_j, are associated with a class of a part of speech, POS1, if the part of speech of each matching term in the syntactic tuples is a noun, namely, if:

(T_i.term1==T_j.term1)AND

(T_i.term1.POS==NOUN AND T_j.term1.POS==NOUN)

AND

(T_i.term2==T_j.term2) AND

(T_i.term2.POS==NOUN AND T_j.term2.POS==NOUN).

10. A method according to claim 9 wherein a syntactic tuple of a first portion of text, T_i, and a syntactic tuple of a second portion of text, T_j, are associated with a class of a part of speech, POS2, if the part of speech of one, and only one, matching term in the syntactic tuples is a noun, namely, if:

((T_i.term1==T_j.term1) AND

(T_i.term1.POS==NOUN AND T_j.term1.POS==NOUN)

AND

(T_i.term2==T_j.term2) AND

(T_i.term2.POS!=NOUN OR T_j.term2.POS!=NOUN))

OR

((T_i.term1==T_j.term1) AND

(T_i.term1.POS!=NOUN OR T_j.term1.POS!=NOUN)

AND

(T_i.term1==T_j.term1) AND

(T_i.term1.POS==NOUN AND T_j.term1.POS==NOUN).

11. A method according to claim 10 wherein a syntactic tuple of a first portion of text, T_i, and a syntactic tuple of a second portion of text, T_j, are associated with a class of a part of speech, POS3, if they are not associated with either class POS1 or POS2.

12. A method according to claim 11 wherein the step of calculating a value representative of the similarity between the portions of text for each of the classes of agreement comprises a weighting based upon the number of matched terms occurring in particular parts of speech, the calculation of the value for Class A comprising parameters relating to the number of matching syntactic tuples according to Class A and POS1, nA₁, the number of matching syntactic tuples according to Class A and POS2, nA₂, and the number of matching syntactic tuples according to Class A and POS3, nA₃, and separate weighting factors w₁, w₂ and w₃ also being applied to the POS1, POS2 and POS3 matchings, the value, sim_A(D_i,D_J), being calculated as:

${\mathrm{sim}}_A<br><br>\left(D_i,D_j\right)=\frac{\underset{i=1}{\overset{3}{\sum <br><br>}}<br><br><br><br>n<br><br><br><br>A_i·<br><br>w_i}{\min <br><br>\left(N_i,N_j\right)}$

where min(N_i,N_j) represents the lesser value of the two lengths of the vectors of syntactic tuples formed for the portions of text D_i and D_j, respectively.

13. A method according to claim 12 wherein the step of calculating a value representative of the similarity between the portions of text for each of the classes of agreement comprises a weighting based upon the number of matched terms occurring in particular parts of speech, the calculation of the value for Class B comprising parameters relating to the number of matching syntactic tuples according to Class B and POS1, nB₁, the number of matching syntactic tuples according to Class B and POS2, nB₂, and the number of matching syntactic tuples according to Class B and POS3, nB₃, and separate weighting factors w₁, w₂ and w₃ also being applied to the POS1, POS2 and POS3 matchings, the value, sim_B(D_i,D_j), being calculated as:

${\mathrm{sim}}_B<br><br>\left(D_i,D_j\right)=\frac{\underset{i=1}{\overset{3}{\sum <br><br>}}<br><br><br><br>n<br><br><br><br>B_i·<br><br>w_i}{3·<br><br>\min <br><br>\left(N_i,N_j\right)}$

where min(N_i,N_j) represents the lesser value of the two lengths of the vectors of syntactic tuples formed for the portions of text D_i and D_j respectively.

14. A method according to claim 13 wherein the step of calculating a value representative of the similarity between the portions of text for each of the classes of agreement comprises a weighting based upon the number of matched terms occurring in particular parts of speech, the calculation of the value for Class C comprising parameters relating to the number of matching syntactic tuples according to Class C and POS1, nC₁, the number of matching syntactic tuples according to class C and POS2, nC₂, and the number of matching syntactic tuples according to Class C and POS3, nC₃, and separate weighting factors w₁, w₂ and w₃ also being applied to the POS1, POS2 and POS3 matchings, the value, sim_c(D_i,D_j), being calculated as:

${\mathrm{sim}}_C<br><br>\left(D_i,D_j\right)=\frac{\underset{i=1}{\overset{3}{\sum <br><br>}}<br><br><br><br>n<br><br><br><br>C_i·<br><br>w_i}{2·<br><br>\min <br><br>\left(N_i,N_j\right)}$

where min(N_i, N_j) represents the lesser value of the two lengths of the vectors of syntactic tuples formed for the portions of text D_i and D_j respectively.

15. A method according to claim 12 wherein the weighting factors, w₁, w₂ and w₃ are such that:

w₁+w₂+w₃=1.00 and w₁≧

w₂≧

w₃.

16. A method according to claim 13 wherein the weighting factors, w₁, w₂ and w₃ are such that:

w₁+w₂+w₃=1.00 and w₁≧

w₂≧

w₃.

17. A method according to claim 14 wherein the weighting factors, w₁, w₂ and w₃ are such that:

w₁+w₂+w₃=1.00 and w₁≧

w₂≧

w₃.

18. A method according to claim 17 wherein the step of determining and outputting a measure of the similarity between the portions of text by calculating a weighted sum of the values representative of the similarity between the portions of text for each of the classes of agreement, sim(D_i,D_j), is calculated as:

sim(D_i,D_j)=w_a×

sim_A(D_i,D_j)+w_b×

sim_B(D_i,D_j)+w_c×

sim_C(D_i,D_j)

where w_a, w_b and w_c are weighting factors.

19. A method according to claim 18 wherein the weighting factors, wa, wb and wc are such that:

w_a+w_b+w_c=1.0 and w_a≧

w_b≧

w_c.