Method of text similarity measurement

• US 20040088156A1
• Filed: 11/26/2003
• Published: 05/06/2004
• Est. Priority Date: 01/04/2001
• Status: Active Grant

• Current Assignee: Agency For Science Technology and Research
• Original Assignee: Agency For Science Technology and Research
• Inventors: Kanagasabai, Rajaraman, Pan, Hong
• Granted Patent: US 7,346,491 B2
• Time in Patent Office: Days
• 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 including the steps of:

forming a set of syntactic tuples, each tuple including at least 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;

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

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 includes 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 includes 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 include 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 a class of agreement of syntactic tuples, class A, if and only if:

(T_i.relation==T_j.relation) AND (T_i.term1==T_j.term1) AND (T_i.term2==T_j.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 a class of agreement of syntactic tuples, class B, if and only if:

((T_i.relation==T_j.relation) AND (T_i.term1==T_j.term1)) OR ((T_i.relation==T_j.relation) AND (T_i.term2==T_j.term2)) OR ((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 a class of agreement of syntactic tuples, class C, if and only if:

(T_i.term1==T_j.term1) OR (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.term2==T_j.term2) AND (T_i.term2.POS==NOUN AND T_j.term2.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 the classes of agreement includes a weighting based upon the number of matched terms occurring in particular parts of speech, the calculation of the value for Class A including 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:

13. A method according to claim 12 wherein the step of calculating a value representative of the similarity between the portions of text for the classes of agreement includes a weighting based upon the number of matched terms occurring in particular parts of speech, the calculation of the value for Class B including 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:

14. A method according to claim 13 wherein the step of calculating a value representative of the similarity between the portions of text for the classes of agreement includes a weighting based upon the number of matched terms occurring in particular parts of speech, the calculation of the value for Class C including 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:

15. A method according to claim 12 wherein the weighting factors, w1, w2 and w3 are such that:

w₁₊w₂₊w₃₌1.00 and w₁≧

w₂≧

w₃.

16. A method according to claim 13 wherein the weighting factors, w1, w2 and w3 are such that:

w₁₊w₂₊w₃₌1.00 and w₁≧

w₂≧

w₃.

17. A method according to claim 14 wherein the weighting factors, w1, w2 and w3 are such that:

w₁₊w₂₊w₃₌1.00 and w₁≧

w₂≧

w₃.

18. A method according to claim 17 wherein the step of 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, sim(Di,Dj), 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, w_a, w_b and w_c are such that:

w_a+w_b+w_c=1.0 and w_a≧

w_b≧

w_c.