Compact encoding of multi-lingual translation dictionaries

• US 5,787,386 A
• Filed: 06/03/1996
• Issued: 07/28/1998
• Est. Priority Date: 02/11/1992
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Mullins, Atty T., Kaplan, Ronald M.
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): Thomas, Joseph
• Application Number:
  US08/657,229
• Time in Patent Office: 785 Days
• Field of Search: 704/10, 704/8, 704/1, 704/2, 704/3, 704/4, 704/5, 704/6, 704/7, 395/794, 395/601, 395/611, 395/612, 395/613, 395/615, 707/532, 707/536, 707/101, 707/102, 707/4
• US Class Current: 704/8
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06F 40/55 Rule-based translation

Abstract

A computerized multilingual translation dictionary includes a set of word and phrases for each of the languages it contains, plus a mapping that indicates for each word or phrase in one language what the corresponding translations in the other languages are. The set of words and phrases for each language are divided up among corresponding concept groups based on an abstract pivot language. The words and phrases are encoded as token numbers assigned by a word-number mapper laid out in sequence that can be searched fairly rapidly with a simple linear scan. The complex associations of words and phrases to particular pivot language senses are represented by including a list of pivot-language sense numbers with each word or phrase. The preferred coding of these sense numbers is by means of a bit vector for each word, where each bit corresponds to a particular pivot element in the abstract language, and the bit is ON if the given word is a translation of that pivot element. Then, to determine whether a word in language 1 translates to a word in language 2 only requires a bit-wise intersection of their associated bit-vectors. Each word or phrase is prefixed by its bit-vector token number, so the bit-vector tokens do double duty: they also act as separators between the tokens of one phrase and those of another. A pseudo-Huffman compression scheme is used to reduce the size of the token stream. Because of the frequency skew for the bit-vector tokens, this produces a very compact encoding.

Claims

1. A method for making a database stored upon a computer readable medium used with a computer for use as a computerized multi-lingual dictionary for translating words and phrases in a first language into words and phrases in at least a second language, comprising the steps:

(a) defining a set of abstract concept groups capable of encompassing all words and phrases to be translated of the first and second languages, each concept group containing words and phrases having related meanings and all of said words and phrases to be translated being included in at least one of the concept groups, such phrases comprising a string made up of words and punctuations,

(b) providing a word-number mapper capable of inversely associating a unique first number between 0 and N-1 with each of the unique words or punctuations of the first language with N being the total number of unique words and punctuations in the first language,

(c) mapping each unique word or punctuation to a unique first number using the mapper of step (b) and storing the resultant mapping,

(d) separating one or more first numbers from one or more other first numbers with a second number,

(e) forming a set of pairs of first and second numbers representative of each of the concept groups in said first language,

(f) forming a translator file for said first language by combining the first and second number pairs of all the concept groups.

2. The method of claim 1, wherein the first numbers lie within a numeric range which excludes said second numbers.

3. The method of claim 2, wherein the smallest second number is offset from the smallest first number by a value substantially equal to the total number of words and punctuations in the first language.

4. The method of claim 2, wherein each of the second numbers represent bit-mapped sense vectors.

5. The method of claim 2, wherein the first and second numbers are encoded using a pseudo-Huffinan scheme.

6. The method of claim 5, wherein some of the numbers are encoded as 1-byte, and the remaining numbers are encoded as 2-bytes.

7. A method for making a database stored upon a computer readable medium used with a computer for use in a computerized multi-lingual dictionary for translating words and phrases in a first language into words and phrases in at least a second language, comprising the steps:

storing in the database each word and word separator in a phrase as one or more first numbers paired with a second number associated with a bit-mapped sense vector for easy matching with other bit-mapped sense vectors.

8. The method of claim 7, wherein the first and second numbers occupy different numeric intervals.

9. The method of claim 8, wherein the stored numbers are encoded using a pseudo-Huffman compression scheme.

10. A method of making a compressed translator file as part of a database stored upon a computer readable medium used with a computer for use as a computerized multi-lingual dictionary for translating words and phrases in a first language into words and phrases in at least a second language, comprising the steps:

(a) defining a set of abstract concept groups capable of encompassing all words and phrases to be translated of the first and second languages, each concept group containing words and phrases having related meanings and all of said words and phrases to be translated being included in at least one of the concept groups, such phrases comprising a string made up of words and punctuations,

(b) establishing a collection of N unique tokens made up of each unique word or punctuation,

(c) providing a word-number mapper capable of inversely associating a unique first number between 0 and (N-1) with each of the unique tokens,

(d) mapping each unique token established in step (b) to a unique first number using the mapper of step (c) and storing the resultant mapping,

(e) creating and storing a translation vector constituting a sequence of second numbers for each word or phrase that can be translated of the first language, each translation vector including those numbers representative of different senses in the same concept group that the word or phrase can express, the total T of said translation vectors that are unique across all the concept groups being substantially less than the total number of words and phrases, said translation vectors being constituted by fixed length bit vectors,

(f) computing from each translation vector a unique translation vector indicator third number having a value between N and N+(T-1),

(g) forming a temporary first file made up of a sequence of first numbers denoting words and punctuations and third numbers denoting the translation vector indicators,

(h) computing the frequencies of the numbers in the temporary first file and encoding same with fourth numbers of different length such that shorter fourth numbers are used to encode higher frequency numbers in the temporary first file and longer fourth numbers are used to encode lower frequency numbers,

(i) forming and storing a temporary second file made up of a sequence of the fourth numbers,

(j) computing the length of each concept group represented by fourth numbers in the temporary second file,

(k) storing the length of each concept group as a prefix to the sequence of fourth numbers representative of each concept group to form a final stored translator file made up solely of numbers and representing every word and phrase of the first language,

(l) repeating steps (e)-(k) for each word and phrase of the second language.

11. A data structure stored on a computer readable medium accessed by an application program executed on a computer system, the data structure comprising

string data having a plurality of data units, each of which can be accessed by a processor of a dictionary system;

the data units representing separated words among a sequence of G concept groups of a first language, the concept groups corresponding to those of an abstract language also containing G concept groups such that each gth concept-group of the first language corresponds to a gth concept group of the abstract language; and

said string data represent solely numbers.

12. The data structure of claim 11, wherein said data units also represent separated words among a sequence of G concept groups of a second language also corresponding to those of the abstract language.

13. The data structure of claim 11, wherein the data further represent bit-mapped sense vectors representing senses of words within a concept group.

14. The data structure of claim 11, wherein computer-readable program code represents the string data and wherein the computer readable program code representing the string data causes the application program of the computer system to form a translation file for use in translating between the first language and the abstract language.

15. A program product for making a database stored upon a computer readable medium used with a computer for use as a computerized multi-lingual dictionary for translating words and phrases in a first language into words and phrases in at least a second language, comprising:

(a) computer readable program code for causing a computer to define a set of abstract concept groups capable of encompassing all words and phrases to be translated of the first and second languages, each concept group containing words and phrases having related meanings and all of said words and phrases to be translated being included in at least one of the concept groups, such phrases comprising a string made up of words and punctuations,

(b) computer readable program code for causing a computer to provide a word-number mapper capable of inversely associating a unique first number between 0 and N-1 with each of the unique words or punctuations of the first language with N being the total number of unique words and punctuations in the first language,

(c) computer readable program code for causing a computer to map each unique word or punctuation to a unique first number using the computer readable program code for causing a computer to map of step (b) and storing the resultant mapping,

(d) computer readable program code for causing a computer to separate one or more first numbers from one or more other first numbers with a second number,

(e) computer readable program code for causing a computer to form a set of pairs of first and second numbers representative of each of the concept groups in said first language, and

(f) computer readable program code for causing a computer to form a translator file for said first language by combining the first and second number pairs of all the concept groups.

16. The product of claim 15, wherein the first numbers lie within a numeric range which excludes said second numbers.

17. The product of claim 16, wherein the smallest second number is offset from the smallest first number by a value substantially equal to the total number of words and punctuations in the first language.

18. The product of claim 16, wherein the first and second numbers are encoded using a pseudo-Huffman scheme.