Apparatus and methods for pronunciation lexicon compression

A compressed pronunciation lexicon file is generated from a source pronunciation lexicon using a pronunciation prediction algorithm in a multi-output mode. The pronunciation prediction algorithm may generate a deterministic ordered list of phoneme strings from the textual representation of a particular word. The compressed pronunciation lexicon file may include a sorted list of records of compressed textual representations of words and compressed phonetic representations of the words.

BACKGROUND OF THE INVENTION

Pronunciation lexicons may be used to translate textual representation of words into their respective pronunciation, represented by a string of phonemes. A pronunciation lexicon may be stored in memories of electronic devices, mobile or stationary. Memory size constraints in such electronic devices may restrict the size of such a pronunciation lexicon.

It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

Some portions of the detailed description which follow are presented in terms of algorithms and symbolic representations of operations on data bits or binary digital signals within a computer memory. These algorithmic descriptions and representations may be the techniques used by those skilled in the data processing arts to convey the substance of their work to others skilled in the art.

FIG. 1is a block diagram of an exemplary apparatus2, according to some embodiments of the invention. Apparatus2may include a processor4and a memory6coupled to processor4.

A non-exhaustive list of examples for apparatus2includes a cellular telephone, a wireless telephone, a mobile telephone, a game console, a personal digital assistant (PDA), a hand-held computer, a laptop computer, a notebook computer, a desktop personal computer, a work station, a server computer, and the like.

A non-exhaustive list of examples for processor4includes a central processing unit (CPU), a digital signal processor (DSP), a reduced instruction set computer (RISC), a complex instruction set computer (CISC) and the like. Moreover, processor4may be part of an application specific integrated circuit (ASIC) or may be a part of an application specific standard product (ASSP).

Memory6may be fixed in or removable from apparatus2. A non-exhaustive list of examples for memory6includes any combination of the following:a) removable memories, such as compact flash (CF) memory cards, personal computer memory card international association (PCMCIA) memory cards, security identity module (SIM) cards, MEMORY STICK® cards, universal serial bus (USB) KEY® memory cards, and the like,b) semiconductor devices, such as read only memory (ROM), mask ROM, electrically erasable programmable read only memory devices (EEPROM), non-volatile random access memory devices (NVRAM), not AND (NAND) flash memory devices, not OR (NOR) flash memory devices, synchronous dynamic random access memory (SDRAM) devices, RAMBUS dynamic random access memory (RDRAM) devices, double data rate (DDR) memory devices, static random access memory (SRAM), and the like,c) optical devices, such as compact disk read only memory (CD ROM), and the like, andd) magnetic devices, such as a hard disk, a floppy disk, a magnetic tape, and the like.

Apparatus2may include an audio input device8, such as, for example, a microphone, an audio output device10, such as, for example, a loudspeaker, an earphone, a headphone, and the like, and an audio coder-decoder (codec)12.

Codec12may be able to receive a digital representation14of sound waves from processor4and to output a corresponding analog signal16to audio output device10. Audio output device10may be able to receive analog signal16and to output sound waves18corresponding to analog signal16. For example, codec12may receive a digital representation14of sound waves of a voice pronouncing the name “George” and as a result, audio output device10may produce sound waves18corresponding to the name “George”.

In addition, audio input device8may be able to receive sound waves20and to output a corresponding analog signal22to codec12. Codec12may be able to receive analog signal22and to output a digital representation24of analog signal22to processor4. For example, audio input device8may receive sound waves of a user pronouncing the name “Ron”, and as a result, processor4may receive a digital representation24of the voice pronouncing the name “Ron”.

Apparatus2may optionally include a display26coupled to processor4, and may optionally include one or more input devices28, such as, for example, a mouse, a keyboard, a touch screen, a digital pen, and the like, coupled to processor4. In addition, apparatus2may be optionally capable of wireless communication with other apparatuses and for at least that purpose, may optionally include an antenna30and a transceiver32coupled to antenna30.

For clarity, in the following description, the invention is described by way of describing apparatus2as a cellular telephone and by way of describing a specific application. However, the invention is not at all limited in this respect, and it will be obvious to those skilled in the art how to modify the following for other applications and for other kinds of apparatus2.

Memory6may store a contact list34of records36. A record36may include at least a textual representation of a first name38of a person, a textual representation of a last name40of the person and a telephone number42of the person. A user may update or add records36by way of, for example, any of input devices28, an optional synchronization port44of apparatus2or transceiver32. It may be appreciated that contact list34may include several and even hundreds of records, although for clarity, only four records,36A-36D are shown in detail inFIG. 1.

A user may display a partial content of contact list34on display26, may select a particular one of records36and may operate apparatus2to dial the telephone number42stored in that particular record36.

A record36may also include a phonetic representation46of first name38and a phonetic representation48of last name40. In addition, memory6may store a voice dialing module50for at least enabling voice dialing for apparatus2.

In response to a user pronouncing a person's first and/or last names in the vicinity of audio input device8, voice dialing module50may receive from codec12a digital representation of the user's voice pronouncing the first name and/or a digital representation of the user's voice pronouncing the last name.

Voice dialing module50may convert the digital representation of the user's voice pronouncing the first and the last names into textual representations, and may search contact list34for a record36including a first name38and a last name40that substantially match these textual representations. If such a record36is found, voice dialing module50may fetch the corresponding phonetic representations46and48from the found record36.

Voice dialing module50may form a digital representation of a sentence including the corresponding phonetic representations46and48to ask the user to confirm the selection. Voice dialing module50may send the digital representation of the sentence to audio output device10through codec12, and if a confirmation is received from the user by way of, for example, audio input device8or one of input devices28, voice dialing module50may activate dialing the corresponding telephone number42.

Memory6may store a compressed pronunciation lexicon file52, a pronunciation prediction module54and a phoneme string extraction module56. Compressed pronunciation lexicon file52, described in further detail hereinbelow with respect toFIGS. 2-7, may contain, in a compressed form, a vast amount of names and their corresponding phonetic representations, and may be a source for at least some of the phonetic representations stored in contact list34.

Phoneme string extraction module56may implement a method to fetch phonetic representations of names from compressed pronunciation lexicon file52and to store the fetched phonetic representations in contact list34. An exemplary method to be implemented in phoneme string extraction module56is described hereinbelow with respect toFIGS. 8 and 9. Pronunciation prediction module54may implement a pronunciation prediction algorithm in a multi-output mode, in which, in response to receiving a textual representation of a word, pronunciation prediction module54may output a list of one or more phoneme strings of possible pronunciations of the word. The list of possible pronunciations of the word may be used by phoneme string extraction module56while fetching phonetic representations of names from compressed pronunciation lexicon file52. Pronunciation prediction module54may be based on a hidden Markov model (HMM).

FIG. 2is a block diagram of an exemplary apparatus102to generate compressed pronunciation lexicon file52from at least a source pronunciation lexicon106using a pronunciation prediction algorithm in a multi-output mode, according to some embodiments of the invention.

Source pronunciation lexicon106may include a list108of records110. It may be appreciated that list108may include a vast amount of records, for example, 10,000, 25,000 or 75,000, although for clarity only nine records, numbered1-9, are shown in detail inFIG. 2. A record110may include a textual representation of a word112and a respective phonetic representation114, which may be a string of phonemes representing pronunciation of word112. The words in the source pronunciation lexicon may be first names or last names of people, although the present invention is not limited in this respect. For example, the source pronunciation lexicon may include words of a general dictionary.

Apparatus102may include a processor116and a memory118coupled to processor116. Memory118may store a compression module120and pronunciation prediction module54, both to be executed by processor116during generation of compressed pronunciation lexicon file52. Pronunciation prediction module54may implement a pronunciation prediction algorithm in a multi-output mode to receive a textual representation of a word and to output a deterministic ordered list of phoneme strings of possible pronunciations of the word.

Reference is now made in addition toFIG. 3, which is a flowchart illustration of an exemplary method for generating compressed pronunciation lexicon file52from at least source pronunciation lexicon file106using a pronunciation prediction algorithm in a multi-output mode, according to some embodiments of the invention.

Compressed pronunciation lexicon file52may include a sorted list131of records of compressed textual representations and compressed phonetic representations. In the following example, the textual representations are compressed by sorting them in ascending alphabetic order and then separating the textual representations into prefixes and suffixes based on the textual representation of the preceding record (seeFIG. 5), replacing the prefix with a prefix length and Huffman-encoding the suffix (seeFIG. 6). Since Huffman encoding is used, compressed pronunciation lexicon file52includes a Huffman encoding table136or alternatively the corresponding Huffman decoding tree (not shown).

This form of compression of the textual representation implies serial decompression. Since list131may have hundreds of records, serial decompression of the entire list may be time consuming. Therefore, list131may be partitioned into sections, and compressed pronunciation lexicon file52may optionally include an index table150including pointers156to the beginning of each section in list131so that only one section of list131will be serially decompressed when searching for a particular word. Each pointer156may be associated with an index154storing a string of, for example, one or two letters. The record of list131that is the beginning of a section will include a compressed word that begins with the string stored in index154. Records of list131pointed to by pointers156in index table150may be distributed fairly evenly in list131. Index table150may include several and even hundreds of entries152, although for clarity only three entries are show in detail inFIG. 2. The entries152of index table150may be sorted in alphabetical order of the indexes154. The number of sections into which list131is partitioned is a trade-off between processor speed and memory consumption, and may be, for example, 1/50 of the number of words in source pronunciation lexicon file106.

Any other suitable compression for the textual representations is also possible, as is the option of not compressing the textual representations.

Compression module120may receive source pronunciation lexicon106(200), and may sort records110in an alphabetical order of textual representations112to generate a sorted list124, as shown inFIG. 5(202). In the example ofFIG. 5, sorted list124is sorted in ascending alphabetical order. However, any other alphabetical sorting order, such as, for example, descending alphabetical order, is within the scope of the invention.

Compression module120may generate a sorted list125by splitting the textual representation of words112in sorted list124into prefixes and suffixes and by substituting the textual representation of words112in sorted list124with “prefix” fields126and “suffix” fields128(204), as shown inFIG. 5. The prefix field of a particular record may contain a longest string of the beginning letters of the word that are identical to the beginning letters of the word in the preceding record. Although the present invention is not limited in this respect, compression module120may limit the maximum number of letters in a prefix to for example, 5, 7 or 9.

For example, the longest string of beginning letters of the word “ABRAM” in record number2of sorted list124that are identical to the beginning letters of the word “ABRAHAM” in record number1of sorted list124is “ABRA”. Accordingly, the string “ABRA” is defined as the prefix of record number2and the string “M” is defined as the suffix of record number2of list125.

In another example, no beginning letters of the word “MADELINE” in record number422of sorted list124are identical to the beginning letters of the word “KIRA” in record number421of sorted list124. Accordingly, no string of letters is defined as the prefix and the string of letters “MADELINE” is defined as the suffix in record number422of list125.

In a yet another example, for the word in record number1, no string of letters is defined as a prefix and the whole word, i.e. “ABRAHAM” is defined as the suffix in record number1of list125.

Compression module120may generate a histogram table132, shown inFIG. 2. Histogram table132may have twenty-six entries134A-134Z, one each letter in the English alphabet. It may be appreciated that although in the example ofFIG. 2, histogram table132has entries134corresponding to letters of the English alphabet, histogram table132may have instead, or in addition, entries corresponding to letters of other alphabets, such as, for example, Cyrillic, Latin, European, Hebrew, Arabic, and the like.

Compression module120may count the number of times each letter of the alphabet appears in suffix fields128and may store that number in the corresponding entry134(208). For example, compression module120may store in entry134A the number of times the letter “A” appears in suffix fields128.

Compression module120may generate a sorted list129by substituting suffix fields128of sorted list127with respective “Huffman encoded suffix” fields138, as shown atFIG. 6. A Huffman encoded suffix field138may contain a number encoded by compression module120from the corresponding suffix field128using Huffman coding table136(212).

Compression module120may generate sorted list131by substituting phonetic representations14of sorted list129with respective pronunciation fields142, which may have one of three variations142A,142B and142C (214), as shown atFIG. 7. An exemplary method for box (214) is presented inFIG. 4.

Variation142A may include a code field144containing the value zero, for example, and an index field146. Variation142B may include code field144containing the value one, for example, index field146, and an edit operations field148. Variation142C may include code field144having the value two, for example, and the respective phonetic representation114. Code field144may indicate the variation type of pronunciation fields142(A, B or C). Index field146and edit operations field148will be explained in the following paragraphs.

Reference is now made toFIG. 4, which is a flowchart illustration of an exemplary method for generating pronunciation fields of a compressed pronunciation lexicon file using a pronunciation prediction algorithm in a multi output mode, according to some embodiments of the invention.

Compression module120may activate pronunciation prediction module54to receive textual representation of a word112of a particular record110, and to generate a respective deterministic ordered list158of phoneme strings160to optionally match phonetic representation field114of the particular record110(300). List158may be deterministic in the sense that identical input words to pronunciation prediction module54produce identical lists158having the same phoneme strings160in the same order.

Compression module120may compare phoneme strings160to the phonetic representation field114, and if one of phoneme strings160exactly matches phonetic representation field114(302), compression module120may substitute phonetic representation field114of sorted list129with a pronunciation field142of type A (304). In pronunciation field142A, index field146may contain an index of the matching phoneme string160in list158. In other words, if a record in list131has a pronunciation field142of type A, it means that the phonetic representation114of the corresponding record in list129exactly matches one of the list158of phoneme strings160generated by pronunciation prediction module54, and therefore it is sufficient to store only the index to the correct phoneme string in list158.

If none of phoneme strings160exactly matches phonetic representation field114, compression module120may evaluate the edit operations required to convert each of phoneme strings160to phoneme representation field114(306). For the phoneme string160having the fewest required edit operations (308), compression module120may check if the required number of edit operations is lower than a threshold162, of, for example, one edit operation or two edit operations (310).

If the required number of edit operations is smaller than threshold162, compression module120may substitute phonetic representation field114of sorted list129with a pronunciation field142of type B (312). In pronunciation field142B, edit operations field148may contain an encoded description of the required edit operations. In other words, if a record in list131has a pronunciation field142of type B, it means that the phonetic representation114of the corresponding record in list129differs from one of the list158of phoneme strings160generated by pronunciation prediction module54only by a small number of edit operations, and therefore it is sufficient to store only the index to the phoneme string in list158and an encoded description of the edit operations.

However, if the required number of edit operations is equal to or higher than threshold162, the method may substitute phonetic representation field114of sorted list129with a pronunciation field142of type C (314), containing a code to indicate that the pronunciation field is of type C and phonetic representation field114.

Reference is now made toFIGS. 8 and 9, which are a flowchart illustration of an exemplary method to extract a phoneme string from a compressed pronunciation lexicon file using a pronunciation prediction algorithm in a multi-output mode, according to some embodiments of the invention. The method ofFIGS. 8 and 9may be implemented in phoneme string extraction module56ofFIG. 1.

Phoneme string extraction module56may receive a textual representation of an input word (400) and may read Huffman coding table136and index table150of compressed pronunciation lexicon file52(402). Phoneme string extraction module56may scan index table150for a particular entry152having a particular index154that alphabetically succeeds all indexes154that alphabetically precedes the input word (404).

Phoneme string extraction module56may get to the record in list131pointed to by pointer156of the particular entry152(406), and may decode a textual string from Huffman coding table136and from prefix length field130and Huffman encoded suffix field138of the record (408). If the textual string is not identical to the input word (410), and if the textual string is alphabetically larger than the input word (412), phoneme string extraction module56may report that the input word is not found in compressed pronunciation lexicon file52(414), and the method may terminate.

If the textual string is not alphabetically larger than the input word, phoneme string extraction module56may point to the next record (416) and may continue to box (408). The sequence (408), (410), (412), (416) may be repeated until a textual string decoded from a record is identical to the input word (410), or until a textual string decoded from a record is alphabetically larger than the input word (412).

If a textual string that is decoded from a particular record is found to be identical to the input word in (410), phoneme string extraction module56may read code field144of the particular record (418). If code field144equals the number two (420), phoneme string extraction module56may read the phonetic representation114from the particular record (422), may output a phoneme string that is equal to the phonetic representation114(424) and may terminate.

However, if code field144does not equal the number two, phoneme string extraction module56may call pronunciation prediction module54with the input word as a parameter. As a result, pronunciation prediction module54may output a deterministic ordered list500of phoneme strings502(426), shown inFIG. 1. Phoneme string extraction module56may select the phoneme string502indexed by index field146of the particular record (428).

If code field144equals the number one (428), phoneme string extraction module56may read edit operations field148of the particular record (432) and may edit the phoneme string502indexed by the index field of the record accordingly (434). Phoneme string extraction module56may output the edited phoneme string (436) and may terminate.