Fast, efficient hardware mechanism for natural language determination

• US 6,002,998 A
• Filed: 09/30/1996
• Issued: 12/14/1999
• Est. Priority Date: 09/30/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Paulsen, Robert Charles Jr., Martino, Michael John
• Primary Examiner(s): Isen, Forester W.
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/723,818
• Time in Patent Office: 1,170 Days
• Field of Search: 704/1, 704/8-10, 707/530, 707/531, 707/532, 707/534-536
• US Class Current: 704/9
• CPC Class Codes: G06F 40/263 Language identification

Abstract

A language in which a document is written is identified by comparing the words of a document to the most frequently used words in a plurality of candidate languages. The words are stored in a plurality of sets of word tables, each set of word tables for storing a selected set of most frequently used words in a respective candidate language according to letter pairs in the words. In the preferred embodiment, each of the word tables is an N×N bit table, where each bit represents a given letter pair at a particular place in one of the most frequently used words in a respective candidate language. A set of table access registers, is used for accessing a respective set of word tables to compare words from the document to words stored in the word tables; each table access register accesses word tables for a respective candidate language. One or more word counting registers count a number of matches for a respective candidate language. A comparator selects a candidate language which corresponds to the word counting register having the highest count as the language in which the document is written.

Claims

1. A system for identifying a language in which a document is written, comprising:

a plurality of sets of word tables, each set of word tables for storing a selected set of most frequently used words in a respective candidate language according to letter pairs in the words in wherein each of the word tables is an N×

N bit table, wherein each bit represents a given letter pair at a particular place in one of the most frequently used words in a respective candidate language;

a set of table access registers, each table access register for a respective candidate language, for accessing a respective set of word tables to compare words from the document to words stored in the word tables;

a set of word counting registers, each word counting register for counting a number of matches for a respective candidate language; and

a comparator for selecting a candidate language which corresponds to the word counting register having the highest count as the language in which the document is written.

2. The system as recited in claim 1 wherein the sets of tables comprise a plurality of tableaus of tables, each tableau for storing respective length words and further comprising a table access register for accessing word tables in each respective tableau of tables.

3. The system as recited in claim 2 further comprising:

length determining means for determining lengths of words in the document;

truncating means for truncating words in the document to a maximum length of words stored in the word tables.

4. The system as recited in claim 2 further comprising length determining means for determining lengths of words in the document wherein only words having lengths equal to those stored in the tableaus are compared.

5. The system as recited in claim 4 wherein the bits stored in the word tables for the letter pairs of the word from the document are ANDed together to determine whether there is a match.

6. A system for identifying a language in which a document is written, comprising:

a set of word tables for storing a selected set of most frequently used words in a candidate language according to letter pairs in the words, wherein each of the word tables is an N×

N bit table, wherein each bit represents a given letter pair at a particular place in one of the most frequently used words in a respective candidate language;

a table access register for accessing a respective set of word tables to compare words from the document to words stored in the word tables; and

a word counting register for counting a number of matches for a candidate language.

7. The system as recited in claim 6 wherein a plurality of passes through the document are made, each pass loading the selected set of words in the set of word tables for a respective candidate language, the language of the document determined by the pass having the greatest number of matches.

8. The system as recited in claim 6 wherein words of different lengths are stored in the set of word tables and a blank character is used for words of a length less than a maximum length stored in the set of word tables.

9. The system as recited in claim 6 wherein at least one set of most frequently used words for a candidate language is selected to reduce strong aliasing with words of a different candidate language.

10. The system as recited in claim 6 wherein the word tables are stored in content addressable memory.

11. The system as recited in claim 6 wherein at least one of the candidate languages is an ideographic language which uses a single word table loaded with a double byte character set (DBCS) representation of the ideographs;

a comparator for selecting a candidate language which corresponds to the word counting register having the highest count as the language in which the document is written.

12. A method for identifying a language in which a document is written, comprising the steps of:

storing a plurality of sets of word tables, each set of word tables for storing a selected set of most frequently used words in a respective candidate language according to letter pairs in the words, wherein each of the word tables is an N×

N bit table, wherein each bit represents a given letter pair at a particular place in one of the most frequently used words in a respective candidate language;

accessing the word tables with a set of table access registers, each table access register for accessing a respective set of word tables to compare words from the document to words stored in the word tables;

counting a number of matches with a set of word counting registers, each word counting register for counting a number of matches for a respective candidate language; and

selecting a candidate language which corresponds to the word counting register having the highest count as the language in which the document is written.

13. The method as recited in claim 12 wherein the sets of tables comprise a plurality of tableaus of tables, each tableau for storing respective length words and a separate table access register is used for accessing word tables in each respective tableau of tables.

14. The method as recited in claim 13 further comprising the steps of:

determining lengths of words in the document;

truncating words in the document to a maximum length of words stored in the word tables.

15. The method as recited in claim 13 further comprising the steps of:

determining lengths of words in the document;

comparing words having lengths equal to those stored in the respective tableau.

16. The method as recited in claim 15 further comprising the step of ANDing the bits stored in the word tables for the letter pairs of the word from the document to determine whether there is a match.

17. The method as recited in claim 12 further comprising the steps of:

determining whether the number of matches for the respective candidate languages has diverged by a predetermined amount; and

responsive to the determination of the predetermined amount of divergence, halting the comparison process.