Compact encoding of multi-lingual translation dictionaries

• US 5,523,946 A
• Filed: 05/05/1995
• Issued: 06/04/1996
• 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: Kaplan, Ronald M., Mullins, Atty T.
• Primary Examiner(s): Weinhardt, Robert A.
• Assistant Examiner(s): Thomas, Joseph
• Application Number:
  US08/435,242
• Time in Patent Office: 396 Days
• Field of Search: 364/419.02, 364/419.04, 364/419.07, 364/419.05, 364/419.08, 364/419.19, 395/600
• US Class Current: 704/2
• 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 computer-implemented process for translating words or phrases in a first language to a corresponding word or phrase in a second language, comprising the steps:

(a) defining an abstract language comprising a set of concept groups, each concept group in the set comprising a set of words and phrases of the abstract language that have related meanings,

(b) separating the words and phrases of the first language and the second language into a set of concept groups corresponding in meaning to those of the abstract language, each word and phrase in the first and second languages being represented by a number,

(c) determining the words or phrases of the first language that match the word or phrase to be translated,

(d) determining the concept group of each word or phrase found in step (c),

(e) determining a translation vector associated with each word or phrase found in step (c) in the concept group determined in step (d),

(f) determining the concept group of the second language corresponding to that determined in step (d),

(g) comparing the translation vector determined in step (e) with a translation vector of each of the words and phrases in the corresponding concept group of said second language determined in step (f),

(h) reporting the word or phrase of said second language as the translation of the word or phrase in the first language when their associated translation vectors match at least in part,

(i) steps (c) through (h) being implemented by a computer.

2. The process of claim 1, wherein step (c) is carried out by comparing number representations.

3. The process of claim 2, wherein the number representations are pseudo-Huffman encoded.

4. The process of claim 1, wherein a plurality of second languages is involved in the process.

5. The process of claim 1, further comprising constructing a compressed translator file for each of the first and second languages, wherein each compressed translator file comprises a sequence only of numbers representing words or phrases.

6. The process of claim 5, wherein the sequence of numbers includes representations of each word or phrase in the concept groups, ordered by concept group.

7. The process of claim 6, wherein each word or phrase is associated with a unique translation vector indicator representing a particular sense or senses of the associated word or phrase within the concept group.

8. The process of claim 7, wherein each concept group is prefixed with a length indicator.

9. The process of claim 1, wherein each translation vector is represented by a bit string, said comparing step being carried out by executing a bitwise logical AND of the translation vector determined in step (g) with each translation vector of the words and phrases in the corresponding concept group of the second language and identifying each of the latter translation vectors forming a non-zero result when logically ANDed with the translation vector determined in step (e).

10. The process of claim 9, wherein each concept group comprises at least 4 senses.

11. A computer-implemented process for translating words or phrases in a first language to a corresponding word or phrase in a second language, comprising the steps:

(a) creating an abstract language comprising a set of concept groups, each concept group in the set comprising a set of words and phrases of the abstract language that have related meanings,

(b) separating the words and phrases of the first language and the second language into a set of concept groups corresponding in meaning to those of the abstract language,

(c) determining the words or phrases of the first language that match the word or phrase to be translated,

(d) determining the concept group of each word or phrase found in step (c),

(e) determining a first translation vector associated with each word or phrase found in step (c) in the concept group determined in step (d),

(f) determining the concept group of the second language corresponding to that determined in step (d),

(g) determining a plurality of second translation vectors each associated with one word or phrase of the concept group determined in step (f),

(h) said translation vectors being bit vectors comprising at least one of a plurality of bits with each bit representing one possible sense of a set of senses associated with each concept group,

(i) comparing the first translation vector determined in step (e) with each of the second translation vectors determined in step (g),

(j) reporting the word or phrase of said second language as the translation of the word or phrase in the first language when their associated translation vectors match at least in part,

(k) steps (c) through (j) being implemented by a computer.

12. The process of claim 11, wherein each word and phrase in the first and second languages is represented by a number.

13. The process of claim 12, wherein step (c) is carried out by comparing number representations.

14. The process of claim 11, wherein a plurality of second languages is involved in the process.

15. The process of claim 11, wherein step (i) is carried out by comparing the first and second translation vectors by intersecting the first translation vector determined in step (e) with each second translation vector determined in step (g) and determining each non-empty intersection, and step (j) is carried out by reporting the word or phrase represented by the second translation vector determined in step (i) which formed a non-empty intersection with the first translation vector determined in step (e).

16. The process of claim 11, wherein each of the first and second translation vectors comprise one number or a sequence of numbers wherein each number uniquely represents one sense of a word or phrase in a concept group.

17. A computer-implemented process for translating words or phrases in a source first language to a corresponding word or phrase in at least one other target second language, comprising the steps:

(a) defining an abstract third language comprising a set of concept groups, each concept group in the set comprising a set of words and phrases of the abstract language that have related meanings,

(b) separating the words and phrases of the source first language and target second language into a set of concept groups corresponding in meaning to those of the abstract third language,

(c) constructing and storing a number and a bit vector representing each word or phrase in said source first and said target second languages and a sense of each word or phrase, respectively,

(d) comparing the bit vector of the word or phrase of the source first language to be translated with the bit vectors of the words and phrases in the corresponding concept group of said target second language,

(e) reporting the word or phrase of said target second language as the translation of the word or phase in the source first language when their associated bit vectors have at least one corresponding matched bit,

(f) steps (c) through (e) being implemented by a computer.

18. The process of claim 17, wherein the comparing step comprises a linear scan of the target second language'"'"'s set of concept groups.

19. The process of claim 18, wherein the stored numbers represent a compressed encoding of the associated word or phrase.

20. The process of claim 19, wherein the compressed encoding is of the pseudo-Huffman type.

21. A computer-implemented process for translating words or phrases in a first language to a corresponding word or phrase in a second language, comprising the steps:

(a) providing first and second files containing words and phrases in the first and second languages, respectively, each said file representing the sense of each of said words and phrases by a respective first and second translation vector associated therewith, said words and phrases being divided among one or more corresponding concept groups that have related meanings, said translation vectors being bit vectors comprising at least one of a plurality of bits with each bit representing one possible sense of a set of senses associated with each concept group,

(b) inputting the word or phrase in the first language to be translated into the word or phrase of the second language,

(c) scanning the first file to determine a word or phrase therein matching the inputted word or phrase and the concept group of said matching word or phrase,

(d) upon finding a matching word or phrase in the first file, determining its first translation vector,

(e) scanning the corresponding concept group of the second file searching for a second translation vector that indicates a match to the first translation vector determined in step (d),

(f) upon finding a second translation vector in the second file in step (e), reporting the word or phrase associated therewith as the translation of the inputted word or phrase,

(g) steps (c) through (f) being implemented by a computer.

22. The process of claim 21, wherein step (e) is carried out by executing a bitwise logical AND of the first translation vector with each second translation vector and identifying each second translation vector forming a non-zero result when logically ANDed with the first translation vector.

23. The process of claim 21, wherein the translation vectors and words and phrases are encoded in the first and second files using a pseudo-Huffman encoding scheme in which high frequency items are encoded differently from low frequency items, and providing in each file a high frequency table for decoding encoded items, said high frequency table being accessed upon retrieval of an item from a file to decode its stored file value.