Method for dividing sentences into phrases using entropy calculations of word combinations based on adjacent words

• US 6,505,151 B1
• Filed: 03/15/2000
• Issued: 01/07/2003
• Est. Priority Date: 03/15/2000
• Status: Expired due to Fees

• Current Assignee: Bridgewell Incorporated
• Original Assignee: Bridgewell Incorporated
• Inventors: Cheng, Chih-Yuan, Chen, Kuang-Hua, Sung, Tien-Hsiung, Oyang, Yen-Jen, Chou, Peilin
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/525,692
• Time in Patent Office: 1,028 Days
• Field of Search: 704/9, 704/10, 707/3, 707/4, 707/5, 707/6, 707/530, 707/531, 707/532, 707/533, 434/169
• US Class Current: 704/9
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

The process of dividing sentences into phrases is automated. The sentence is divided into sub-sentences using statistical analysis. Then, the sub-sentences are into phrases, using statistical analysis. For example, for each pair of adjacent words in the sentence a metric is calculated which represents a strength of disconnection between the adjacent words. The sentence is divided into sub-sentences at locations in the sentence where the metric exceeds a first threshold.

Claims

1. A method for automating the process of dividing sentences into phrases, comprising the following steps:

(a) dividing a sentence into sub-sentences using statistical analysis, $\mathrm{FE}<br><br>\left(C_i\right)=-\underset{C_j}{\sum <br><br>}<br><br>P_F<br><br>\left(C_j|C_i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>P_F<br><br>\left(C_j|C_i\right)$

 

including the following substeps;

(a.1) for each pair of adjacent words in the sentence calculating a metric which represents a strength of disconnection between the adjacent words, and

(a.2) breaking the sentence into sub-sentences at locations in the sentence where the metric exceeds a first threshold; and

,

(b) dividing the sub-sentences into phrases, using statistical analysis;

wherein in substep (a.1), the metric is a cutability measure that is calculated as a sum of backward entropy, forward entropy and mutual information; and

,

wherein in substep (a.1) forward entropy (FE) of a character C_I, which immediately proceeds a character C_j in a sentence is calculated using the following equation;

where P_F(C_j|C_i) is the probability of C_j following C_j.

2. A method for automating the process of dividing sentences into phrases, comprising the following steps:

(a) dividing a sentence into sub-sentences using statistical analysis, including the following substeps;

(a.1) for each pair of adjacent words in the sentence calculating a metric which represents a strength of disconnection between the adjacent words, and

(a.2) breaking the sentence into sub-sentences at locations in the sentence where the metric exceeds a first threshold; and

,

(b) dividing the sub-sentences into phrases, using statistical analysis;

wherein in substep (a.1), the metric is a cutability measure that is calculated as a sum of backward entropy, forward entropy and mutual information; and

,

wherein in substep (a.1) backward entropy (BE) of a character C_I which immediately follows a character C_j in a sentence is calculated using the following equation;

$\mathrm{BE}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(C_i\right)=-\underset{C_j}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P_B<br><br>\left(C_j<br><br>C_i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>P_B<br><br>\left(C_j<br><br>C_i\right)$

where P_B(C_j|C_i) is the probability of C_j being ahead of C_j.

3. A method for automating the process of dividing sentences into phrases, comprising the following steps:

(a) dividing a sentence into sub-sentences using statistical analysis, including the following substeps;

(a.1) for each pair of adjacent words in the sentence calculating a metric which represents a strength of disconnection between the adjacent words, and

(a.2) breaking the sentence into sub-sentences at locations in the sentence where the metric exceeds a first threshold; and

,

(b) dividing the sub-sentences into phrases, using statistical analysis;

wherein in substep (a.1), the metric is a cutability measure that is calculated as a sum of backward entropy, forward entropy and mutual information; and

,

wherein in substep (a.1) mutual information (MI) of a character C_I which immediately precedes a character C_j in a sentence is calculated using the following equation;

$\mathrm{MI}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(C_i,C_j\right)=\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{P<br><br>\left(C_i<br><br>C_j\right)}{P<br><br>\left(C_i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>P<br><br>\left(C_j\right)}$

where P(C_iC_j) in the probability that C_j exactly comes after C_i,

where P(C_i) is the probability that any character chosen at random in the corpus is C_i, and

where P(C_j) is the probability that any character chosen at random in the corpus is C_j.

4. A method for automating the process of dividing sentences into phrases, comprising the following steps:

(a) dividing a sentence into sub-sentences using statistical analysis; and

,

(b) dividing the sub-sentences into phrases, using statistical analysis, including the following substeps;

(b.1) for a first word in the sub-sentence, determining an occurrence, in a corpus, of word combinations of the sub-sentence beginning with the first word,

(b.2) for a word immediately following the first word in the sub-sentence, determining an occurrence, in the corpus, of word combinations of the sub-sentence beginning with the word immediately following the first word, and

(b.3) for the first word in the sub-sentence, selecting a word combination of a first number of words starting with the first word to be used as a phrase when a ratio of the occurrence of the word combination of the first number of words starting with the first word and continuing with adjacent words in the sub-sentence to occurrence of a word combination of the first number of words starting with the word immediately following the first word and continuing with adjacent words in the sub-sentence is greater than that for any but the first number, provided the first number is less than a predetermine threshold.

5. A method as in claim 4 wherein step (b) additionally includes the following substeps:

(b.4) for a next word in the sub-sentence not included in the word combination of the first number of words starting with the first word, determining an occurrence, in the corpus, of word combinations of the sub-sentence beginning with the next word;

(b.5) for a word immediately following the next word in the sub-sentence, determining an occurrence, in the corpus, of word combinations of the sub-sentence beginning with the word immediately following the next word; and

,

(b.6) for the next word, selecting a word combination of a second number of words starting with the next word to be used as a phrase when a ratio of the occurrence of the word combination of the second number of words starting with the next word and continuing with adjacent words in the sub-sentence to occurrence of a word combination of the second number of words starting with the word immediately following the next word and continuing with adjacent words in the sub-sentence is greater than that for any but the second number, provided the second number is less than the predetermine threshold.

6. A method for automating the process of dividing sentences into sub-sentences comprising the following steps:

(a) for each pair of adjacent words in the sentence calculating a metric $\mathrm{FE}<br><br>\left(C_i\right)=-\underset{C_j}{\sum <br><br>}<br><br>P_F<br><br>\left(C_j|C_i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>P_F<br><br>\left(C_j|C_i\right)$

 

which represents a strength of disconnection between the adjacent words; and

(b) breaking the sentence into sub-sentences at locations in the sentence where the metric exceeds a first threshold;

wherein in step (a), the metric is a curability measure that is calculated as a sum of backward entropy, forward entropy and mutual information; and

,

wherein in step (a) forward entropy (FE) of a character C_I which immediately proceeds a character C_j in a sentence is calculated using the following equation;

where P_F(C_j|C_i) is the probability of C_j following C_j.

7. A method for automating the process of dividing sentences into sub-sentences comprising the following steps:

(a) for each pair of adjacent words in the sentence calculating a metric which represents a strength of disconnection between the adjacent words; and

(b) breaking the sentence into sub-sentences at locations in the sentence where the metric exceed a first threshold;

wherein in step (a), the metric is a cutability measure that is calculated as a sum of backward entropy, forward entropy and mutual information; and

,

wherein in step (a) backward entropy (BE) of a character C_I which immediately follows a character C_j in a sentence is calculated using the following equation;

$\mathrm{BE}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(C_i\right)=-\underset{C_j}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P_B<br><br>\left(C_j<br><br>C_i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>P_B<br><br>\left(C_j<br><br>C_i\right)$

where P_B(C_j|C_i) is the probability of C_j being ahead of C_j.

8. A method for automating the process of dividing sentences into sub-sentences comprising the following steps:

(a) for each pair of adjacent words in the sentence calculating a metric $\mathrm{MI}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(C_i,C_j\right)=\log <br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{P<br><br>\left(C_i<br><br>C_j\right)}{P<br><br>\left(C_i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>P<br><br>\left(C_j\right)}$

 

which represents a strength of disconnection between the adjacent words; and

(b) breaking the sentence into sub-sentences at locations in the sentence where the metric exceeds a first threshold;

wherein in step (a), the metric is a curability measure that is calculated as a sum of backward entropy, forward entropy and mutual information; and

,

wherein in step (a) mutual information (MI) of a character C_I which immediately precedes a character C_j in a sentence is calculated using the following equation;

where P(C_iC_j) is the probability that C_j exactly comes after C_i,

where P(C_i) is the probability that any character chosen at random in the corpus is C_i, and

where P(C_j) is the probability that any character chosen at random in the corpus is C_j.

9. A method for automating the process of dividing a sentence portion into phrases, comprising the following steps:

(a) for a first word in the sentence portion, determining an occurrence, in a corpus, of word combinations of the sentence portion beginning with the first word;

(b) for a word immediately following the first word in the sentence portion, determining an occurrence, in the corpus, of word combinations of the sentence portion beginning with the word immediately following the first word; and

,

(c) for the first word in the sentence portion, selecting a word combination of a first number of words starting with the first word to be used as a phrase when a ratio of the occurrence of the word combination of the first number of words starting with the first word and continuing with adjacent words in the sentence portion to occurrence of a word combination of the first number of words starting with the word immediately following the first word and continuing with adjacent words in the sentence portion is greater than that for any but the first number, provided the first number is less than a predetermine threshold.

10. A method as in claim 9 additionally comprising the following steps:

(d) for a next word in the sentence portion not included in the word combination of the first number of words starting with the first word, determining an occurrence, in the corpus, of word combinations of the sentence portion beginning with the next word;

(e) for a word immediately following the next word in the sentence portion, determining an occurrence, in the corpus, of word combinations of the sentence portion beginning with the word immediately following the next word; and

,

(f) for the next word, selecting a word combination of a second number of words starting with the next word to be used as a phrase when a ratio of the occurrence of the word combination of the second number of words starting with the next word and continuing with adjacent words in the sentence portion to occurrence of a word combination of the second number of words starting with the word immediately following the next word and continuing with adjacent words in the sentence portion is greater than that for any but the second number, provided the second number is less than the predetermine threshold.