Compression method, method for compressing entry word index data for a dictionary, and machine translation system

[0002] 1. Field of the Invention

[0003] The present invention relates to a machine translation method for translating or converting original text in a first language (foreign language; e.g., English) to translated text in a second language (native language; e.g., Japanese), and in particular to a machine translation method whereby a computer system performs a translation process using an electronically stored dictionary. More specifically, the present invention pertains to a method for compressing entry word index data in a dictionary; to entry word indexes for a dictionary that have been compressed; and to a method for searching for a word based on an entry word index that has been compressed.

[0004] 2. Background Art

[0005] Over the years, much time and effort has been expended in the study of so-called “machine translation” (or “automatic translation”), a technique involving the use of the hardware resources of a computer system to translate text in one language to text in a second language.

[0006] Not long after the end of the Second World War, for example, following the development in 1946 of ENIAC, the first general purpose computer, many researchers became greatly interested in the possibility of using computers for “machine translation.” And over the next ten years universities and research institutes invested an enormous amount of time, energy and money in its study; but with generally unsatisfactory results.

[0007] Thereafter, interest in machine translation waned somewhat. But today, impelled by recent developments related to the use of the Internet, the focus is once again on machine translation; once again great interest is being shown in developing and producing software for this purpose. This has come about because many users of the Internet, outside the English speaking community of nations, either cannot read English or read it imperfectly, and since most text on Web pages are written in English, these users can not fully utilize the new global information system, the WWW (the World Wide Web). As a result, translation software that once, when first developed, was priced in the tens of millions of yen can now be purchased for tens of thousands of yen, and since such software is therefore more easily acquired by users, it is now widely used on personal computers. Of the machine translation software products that are presently available, some are specifically intended for the translation of text on the Internet, i.e., the translation of Web pages. One example of such a product is the “King of Translation,” which is sold by IBM Japan Co., Ltd.

[0008] In short, machine translation is a technique by which the processing capability of a computer system is applied for the translation of text written in a foreign language, such as English, into text in a native language, such as Japanese (or vice versa). For machine translation, a database is constructed by employing, as a model, the enormous amount of language knowledge that a human possesses (or is assumed to possess), and a translation engine, a type of data processor, is employed to refer to this database and to perform the actual translation.

[0009] An example database for a machine translation system is a dictionary. Recent machine translation systems prepare a dedicated dictionary for each genre, such as an art dictionary and a sports dictionary, in addition to a system dictionary that serves as a basic dictionary. Machine translation systems use dictionaries in accordance with the genre to which an object to be translated belongs, and thus the accuracy of a translation can be improved (see the specification in Japanese Unexamined Patent Application Hei 8-272755. and corresponding U.S. Pat. No. 6,119,078 issued on Sep. 12, 2000. Generally, a single machine translation dictionary is constituted by an entry word index portion and a main portion that describes translation data for entry words (includes “morpheme analysis data). The translation engine searches through the entry word indexes to acquire corresponding translation data.

[0010] For distribution, a machine translation system, i.e., the machine translation software, is generally recorded on a storage medium, such as a CD (compact disk) or a FD (floppy disk). To activate the machine translation software, an end user inserts into a drive unit of his or her computer system a CD or FD he or she purchased and installs a program recorded thereon in the computer.

[0011] An entry word index portion of a machine translation system is generally not stored in text form; usually it is compressed or encoded before being stored. This is done because an index portion that has an easily readable form may be employed or examined by a third party, especially by a competitor, and because the size of compressed entry word index data is reduced and can thus be held resident in memory. This last is important because the entry word index data must be accessed each time a word search is conducted, and when the entry word index data is resident in memory, the speed of a search is greatly increased. In particular, the sizes of entry word indexes for a machine translation system that prepares some dictionaries must be reduced, so that all of them can be held resident in memory. Conventionally, a common compression algorithm, such as “LHA” for the general-purpose personal computer (PC) or a compression command “compress” for UNIX, is employed to compress entry word index data, or only an encoding process is performed for the index data without being compressed. However, these conventional techniques have the following shortcomings.

[0012] First, time is required for compression and recovery processing. In particular, once entry word index data are compressed, a search for data can not be performed, and thus, two steps are required: the decompression of the entry word index data and a search for the resultant data. As a result, the search efficiency is deteriorated.

[0013] In addition, since the individual entry words are short character strings (20 to 30 bytes at most), the compression rate is not good.

[0014] Further, only the simple encoding of data does not reduce data size.

[0015] It is, therefore, one object of the present invention to provide a method for compressing entry word index data for a dictionary to be used for machine translation, compressed entry word indexes for a dictionary, and a method for searching for a word using the compressed entry word index data.

[0016] It is another object of the present invention to provide a compression method that enables a search for compressed data to be performed without a decompression process being required, entry word indexes for a dictionary to be generated by such a compression method, and a method for searching for a word using the compressed entry word index.

[0017] To achieve the above objects, according to a first aspect of the present invention, a compression method comprises the steps of: (a) extracting character strings, constituted by n (n is an integer greater than 1) or more characters that frequently appear in an object to be compressed, which consists of many words; (b) calculating compression contribution values for the individual extracted character strings; (c) assigning highly ranked character strings having a high compression contribution value to empty columns in a character translation code table; and (d) substituting for a corresponding character translation code the character strings that are registered in the character translation code table.

[0018] According to the compression method in the first aspect of the present invention, the object to be compressed may be the entry word index data in a dictionary used for machine translation.

[0019] At step (b), for calculating the compression contribution value, the compression contribution value may be represented by (n−k)×count, which is a product of (n−k), a compression value obtained by replacing a character string S having n characters with a character string having k characters (n>k), and count, the frequency at which the character string S of the object to be compressed appears.

[0020] The character translation code table may be an ASCII (American Standard Code for Information Interchange) code table that conforms to the specifications prescribed by ANSI (American National Standards Institute).

[0021] According to a second aspect of the present invention, a method for compressing entry word index data for a dictionary used in a machine translation system, comprises the steps of: (a) extracting character strings constituted by n (n is an integer greater than 1) or more characters that frequently appear in the entry word index data; (b) calculating compression contribution values for the individual extracted character strings; (c) assigning highly ranked character strings having a high compression contribution value to empty columns in a character translation code table; and (d) substituting for a corresponding character translation code the character strings, in the entry word index data, that are registered in the character translation code table.

[0022] According to the compression method in the second aspect, at step (b), for calculating the compression contribution value, the compression contribution value may be represented by (n−k)×count, which is a product of (n−k), a compression value obtained by replacing a character string S having n characters with a character string having k characters (n>k), and count, the frequency at which the character string S in the entry word index data appears.

[0023] The character translation code table may be an ASCII (American Standard Code for Information Interchange) code table that conforms to the specification prescribed by ANSI (American National Standards Institute).

[0024] According to a third aspect of the present invention, a machine translation system for employing the processing capabilities of a computer system to translate text in a first language into text in a second language, comprises: a dictionary, including entry word index data compressed using the compression method according to the second aspect, and a main body in which are described translation data concerning entry words; and a translation engine for referring to the dictionary when translating text in the first language into text in the second language.

[0025] In the machine translation system according to the third aspect of the present invention, when the translation engine searches through the entry word index for a word included in text in the first language, the translation engine may, first, replace a character string included in a word registered in a character translation code table with a corresponding character translation code, and then perform search of the entry word index.

[0026] According to a fourth aspect of the present invention, provided is a computer-readable storage medium for physically storing a machine translation program that is operated by a computer system, which includes a processor for performing a software program, a memory for temporarily storing program code and data being progressed, an external storage device, input devices used by a user to enter data and a display for displaying processed data, the machine translation program comprising: (a) an entry word index data module compressed using the compression method according to the second aspect; (b) a dictionary main body module in which are described translation data concerning individual entry words; and (c) a translation engine module for referring to the dictionary constituted by the modules (a) and (b) to translate text in a first language into text in a second language.

[0027] In the computer-readable storage medium according to the fourth aspect of the present invention, when the translation engine module searches the entry word index for a word included in the text in the first language, the translation engine module may, first, replace a character string in the word, which is registered in a character translation code table, with a corresponding character translation code, and then perform search of the entry word index.

[0028] According to a fifth aspect of the present invention, a method for compressing entry word index data, for a dictionary used in a machine translation system, comprises the steps of: (a) translating original entry word index data into first entry word index data in which individual entry word character strings are represented by a difference from an entry word character string immediately above; (b) selecting, at step (a), an entry word I character string that has a large difference from an entry word character string immediately above, as a reference entry word character string to be described, unchanged, into the first entry word index data; (c) extracting character strings constituted by n (n is an integer greater than 1) or more characters that frequently appear in the first entry word index data; (d) calculating compression contribution values for the individual extracted character strings; (e) assigning highly ranked character strings having a high compression contribution value to empty columns in a character translation code table; and (f) replacing, with corresponding character translation codes, character strings in the first entry word index data that are registered in the character translation code table and generating second entry word index data.

[0029] According to the compression method in the fifth aspect, at step (d), for calculating the compression contribution value, the compression contribution value may be represented by (n−k)×count, which is a product of (n−k), a compression value obtained by replacing a character string s having n characters with a character string having k characters (n>k), and count, a frequency at which the character string S in the entry word index data appears.

[0030] The character translation code table may be an ASCII (American Standard Code for Information Interchange) code table that conforms to the specifications prescribed by ANSI (American National Standards Institute).

[0031] According to a sixth aspect of the present invention, a machine translation system, for employing the processing capability of a computer system to translate text in a first language into text in a second language, comprises: a dictionary including the second entry word index data compressed by the compression method according to the fifth aspect and a main body in which translation data concerning entry words are described; and a translation engine for referring to the dictionary to translate the text in the first language into the text in the second language.

[0032] In the machine translation system according to the sixth aspect of the present invention, when the translation engine conducts search of the entry word index for a word included in the text in the first language, the translation engine may, first, recover the original entry word character strings from character strings in the second entry word index data in accordance with the character translation code table, and compare the word with the recovered entry word character string.

[0033] According to a seventh aspect of the present invention, provided is a computer-readable storage medium for physically storing a machine translation program that is operated by a computer system, which includes a processor for performing a software program, a memory for temporarily storing program code and data being progressed, an external storage device, entry means used by a user to enter data and a display for displaying processed data, the machine translation program comprising: (a) a second entry word index data module compressed using the compression method according to the firth aspect; (b) a dictionary main body module in which translation data concerning individual entry words are described; and (c) a translation engine module for referring to the dictionary constituted by the modules (a) and (b) to translate text in a first language into text in a second language.

[0034] In the computer-readable storage medium according to the seventh aspect of the present invention, when the translation engine module performs search of the entry word index for a word included in the text in the first language, the translation engine module may, first, recover the original entry word character strings from character strings in the second entry word index data in accordance with the character translation code table, and compare the word with the recovered entry word character string.

[0035] In the natural language processing field, the statistical characteristics of languages have been pointed out as the basic characteristics, and have been studied and researched. One of the statistical characteristics of language that has been focused on most is the frequency at which a character appears. Especially since a number of Indo-European languages have alphabets of only 26 characters, the use frequencies of the individual letters in the alphabets have been examined in detail.

[0036] To represent the feature of an English character string, not only the frequency at which a single character appears has been studied, but also the frequencies at which combinations of two or three characters appear have been examined. These combinations are called 2-gram or 3-gram, but generally “In-gram strings.” The order of the frequencies is affected by the type of text used to derive the statistics. In 2-gram statistics, character strings th, he, in, an, er, re and on frequently appear; in 3-gram statistics, character strings that seem to be part of a spelling of a word are extracted; and in n-gram statistics, character strings that appear frequently and conform to the English characteristics are extracted.

[0037] The compression method of the present invention employs the statistical characteristics of language. More specifically, the n-gram statistical analysis is employed to acquire frequently appearing character strings of n characters or more, and individual character strings having n characters or more are replaced by character strings having fewer than n characters, (e.g., character translation codes of 1 byte each). The correlation between the original character strings having n characters and the character translation codes is registered in the correlation table i.e., a character translation code table.

[0038] Assume that a character string of three characters, i.e., a character string of three bytes, “sta,” is registered as 1-byte code “e5” and that a character string of four characters, i.e., a character string of four bytes, “tion,” is registered as 1-byte code “f1.” Then, the word “station,” which consists of a character string of seven characters, i.e., seven bytes, is represented by the 2-byte code “e5 f1,” so that this contributes to a compression of five bytes. When a character string “e5 f1” is found in compressed text data, columns for “e5” and “f1” in the code table prepared in advance are referred to, and the character string can be easily translated to the original character string “station.” That is, the original word can be searched for without decompressing the compressed text.

[0039] According to the first aspect of the present invention, character strings constituted by n (n is an integer greater than 1) or more characters are extracted that frequently appear in an object to be compressed that consists of many words, and a compression contribution value is calculated for the individual extracted character strings. The compression contribution value is represented by (n−k)×count, which is a product of (n−k), the compression value obtained by replacing a character string S having n bytes with a character string having k bytes, and count, a frequency at which the character string S of the object to be compressed appears.

[0040] Then, highly ranked character strings having a higher compression contribution value are assigned to empty columns in a predetermined character translation code table. Assuming that as a result of the n-gram statistics, the compression contribution values of character strings “sta” and “tion” are high and that the columns “e5” and “f1” in the table are unused, the character strings “sta” and “tion” are registered in the respective columns.

[0041] The character strings to be compressed that are registered in the character translation code table are replaced by the corresponding character translation codes. For example, a character string “station” of seven characters is compressed to a character code of “e5 f1” in accordance with the character translation code table.

[0042] The compression method according to the second aspect of the present invention is the one where the compression method of the first aspect is applied for the compression of entry word index data in a dictionary used for machine translation. According to the second aspect, first, character strings constituted by n (n is an integer greater than 1) or more characters that frequently appear are extracted from the entry word index data, and a compression contribution value is calculated for the individual extracted character strings. The compression contribution value is represented by (n−k)×count, which is a product of (n−k), a compression value obtained by replacing a character string S having n bytes with a character string having k bytes, and count, the frequency at which the character string S of the object to be compressed appears.

[0043] Then, highly ranked character strings having a higher compression contribution value are assigned to empty columns in a predetermined character translation code table. The character translation code table may be an ASCII (American Standard Code for Information Interchange) code table that conforms to the specifications prescribed by ANSI (American National Standards Institute). An ASCII code table is well known in this field as a table where alphanumeric characters are assigned for code. Assuming that as a result of the n-gram statistics, the compression contribution values of character strings “sta” and “tion” are high, the character strings “sta” and “tion” are assigned to the respective empty columns “e5” and “f1” in the ASCII code table.

[0044] The character strings in the entry word index data that are registered in the character translation code table are replaced with corresponding character translation codes. For example, an entry word “station” in the entry word index data is compressed to a character code of “e5 f1” in accordance with a modified ASCII code table that is newly generated. In this case, a word “station,” which consists of a character string of seven characters, i.e., seven bytes, is represented by the 2-byte code “e5 f1,” so that this contributes to a compression of five bytes. This compression process is performed for all the entry word index data. It should be noted that as a result, a great amount of entry word index data can be compressed. Thus the compressed entry word index data can remain resident in a main memory having a limited storage capacity without being withdrawn (swapped out).

[0045] The third aspect of the present invention is a machine translation system that employs entry word index data compressed in the second aspect. The machine translation system, for employing the processing capability of a computer system to translate text in a first language into text in a second language, comprises: a dictionary including entry word index data compressed by the compression method according to the second aspect and a main body in which translation data concerning entry words are described; and a translation engine for referring to the dictionary to translate the text in the first language into the text in the second language.

[0046] In the machine translation system according to the third aspect of the present invention, when the translation engine conducts search of the entry word index data for a word included in the text in the first language, the translation engine, first, replaces a character strings in the word, which are registered in a character translation code table (the modified ASCII code table generated by the compression method in the second aspect) with corresponding character translation code, and conducts search of the entry word index. When, for example, a word “station” is found in an English document, which is the text in the first language, the word is translated into character codes “e5 f1” in accordance with the ASCII code table (assuming that the character codes “e5” and “f1” are assigned to “sta” and “tion”). Then, search is conducted of the entry word index data for the character code “e5 f1,” and translation data corresponding to the original character string “station” are acquired.

[0047] In the compressed entry word index data, the character string “station” of seven characters, i.e., seven bytes, is compressed into the 2-byte code “e5 f1.” To search for the word “station” in the entry word index data, the word need only be translated into the corresponding character code “e5 f1,” and the entry word index data do not have to be decompressed. That is, since to examine the index data the decompression process of the compressed entry word index data is not required, a reduction in the search speed does not occur.

[0048] The compression method of the fifth aspect is an example where the compression method of the first aspect, as well as the second aspect, is employed for the compression of entry word index data in a dictionary used for machine translation. The compression method in the fifth aspect differs from the method in the second aspect in that, before entry word index data are compressed according the n-gram statistics, the differences between closely related entry word character strings is obtained to further increase the compression rate.

[0049] According to the compression method of the fifth aspect, first, original entry word index data are translated into first entry word index data in which individual entry word character strings are represented by a difference from an entry word character string immediately above. A character string for which a large difference exists with an immediately preceding entry word character string is maintained, unchanged, as the reference entry word character string in the first entry word index. When “abatable,” “abate” and “abatement” are arranged in ascending order in the original entry word index, entry word “abate” is substituted into character count 4, which is a count matching the immediately preceding entry word “abatable,” and “e,” which is a difference with the word “abatable.” An entry word “abatement” is substituted into character count 5, which is a count matching the immediately preceding entry word “abate,” and “ment,” which is a difference with the word “abate.” These replacements are written into the first entry word index. Further, when the matching character count of the entry word “abatable” is extremely low relative to the immediately preceding entry word, that entry word is defined as the reference character string, so that the original entry word character string remains unchanged in the first entry word index and the matching character count is reset to 0.

[0050] Following this, the n-gram statistics is conducted for the character string difference in the first entry word index. The character strings constituted by n (n is an integer greater than 1) or more characters that frequently appear are extracted, and a compression contribution value is calculated for the individual extracted character strings. The compression contribution value is represented by (n−k)×count, which is a product of (n−k), a compression value obtained by replacing a character string S having n bytes with a character string having k bytes, and count, a frequency at which the character string S in the entry word index data appears.

[0051] Then, highly ranked character strings having a higher compression contribution value are assigned to empty columns in a predetermined character translation code table. The character translation code table may be an ASCII (American Standard Code for Information Interchange) code table that conforms to the specifications prescribed by ANSI (American National Standards Institute). An ASCII code table is well known in this field as a table in which alphanumeric characters are assigned to code. Assuming that as a result of the n-gram statistical analysis the compression contribution values of character strings “able” and “lity” are high, the character strings “able” and “lity” are assigned to the respective empty columns “03” and “ad” in the ASCII code table.

[0052] The character strings in the first entry word index data that are registered in the character translation code table are replaced by corresponding character translation codes. For example, an entry word in the first entry word index, “06 (matching character count) ion (character string difference)” (original entry word is “abjection”), is compressed to a character code of 1106 99” in accordance with the newly generated ASCII code table. In this case, a word “abjection,” which consists of a character string of nine characters, i.e., nine bytes, is represented by the 2-byte code “06 99,” so that this contributes to a compression of seven bytes. This compression process is performed for all the entry word index data. Thus, the entry word index that has been substituted into the corresponding character translation code is the second entry word index, which is used for searching for a word in the dictionary during the machine translation processing.

[0053] According to the fifth aspect of the present invention, as is described above, an n-gram statistical analysis is conducted for a difference between the entry word character strings, and their compression contribution values are compared. As a result of the acquisition of the difference, the character string at the end portion of each entry word can be effectively extracted. For example, suffixes, such as “ion,” “ness” and “ly,” which are inherent to the English language and appear frequently, are extracted as character string differences. Therefore, compared with the compression method of the second aspect whereby an n-gram statistical analysis is conducted only for entry words, a long character string may be set in the high compression contribution ranks, and the compression rate can be further increased. The thus compressed entry word index data can be held resident in a main memory having a limited storage capacity without being withdrawn (swapped out). Especially for machine translation software program that prepares some dictionaries, compression of data and reduction in data size are effective means for holding the entry word index data resident in memory.

[0054] The sixth aspect of the present invention is a machine translation system that employs the entry word index data compressed in the fifth aspect. The machine translation system, for employing the processing capability of a computer system to translate text in a first language into text in a second language, comprises: a dictionary that includes the second entry word index data compressed by the compression method according to the fifth aspect, and a main body in which translation data concerning entry words are described; and a translation engine for referring to the dictionary to translate the text in the first language into the text in the second language.

[0055] In the machine translation system according to the sixth aspect of the present invention, when the translation engine performs search of the entry word index for a word included in the text in the first language, first, the translation engine recovers the original entry word character strings from character strings in the second entry word index data in accordance with the character translation code table, and then compares the word with the recovered entry word character string.

[0056] In the second entry word index, the reference entry word character string is maintained as the original entry word character string. Therefore, first, the reference character string that is most similar to a word is searched for in the second entry word index. When, for example, a word “abjection” is found in an English document, which is the text in the first language, a reference character string “abidance” in the second entry word index is extracted as a candidate character string. If the word being searched for completely matches the candidate character string, the search of the dictionary is terminated. If the word does not match the candidate character string, an entry word that immediately succeeds the candidate character string is examined. If the immediately succeeding entry word is compressed, the original entry word character string must be recovered. If “04 (matching character count) 65 (character string difference code)” is an entry word that succeeds the reference entry word “abidance,” which is first extracted as a candidate character string, the first four characters “abid” are extracted form the immediately preceding entry word character string “abidance,” and a character “ell >a assigned to column “65” in the ASCII code table. The character strings “abid” and “e” are coupled to recover the original character string “abide.” When the candidate character string that is recovered matches the word being searched for, the dictionary search is terminated. If they do not match, the recovering and comparison process is repeated for a succeeding entry word in the index. As a result of repetition, the word “abjection” is obtained from the entry word index, and corresponding translation data can be acquired.

[0057] In the second entry word index data, the character string “abjection” of nine characters, i.e., nine bytes, is compressed into the 2-byte code “06 99,” which is held. The entire entry word index data do not have to be decompressed in order to search for the word “abjection” from the entry word index data. That is, since the decompression process for the compressed entry word index data is not required for an examination of the index data, a reduction in the search speed does not occur.

[0058] According to a computer-readable storage medium of the fourth or the seventh aspect of the present invention, the structural or functional cooperative relationship between a computer program and a storage medium is defined in order to implement the function of a computer program in a computer system. That is, when the computer storage medium is loaded into a computer system (or a computer program is installed in a computer system), the cooperative operation can be demonstrated by the computer system. As a result, the same operating effect as in the machine translation system according to the third or the sixth aspect of the present invention can be obtained.

[0059] Other objects, features and advantages of the present invention will become apparent during the course of the following detailed description of the preferred embodiment, given while referring to the accompanying drawings of which:

[0060] FIG. 1 is a schematic diagram illustrating the hardware arrangement of a typical personal computer (PC) appropriate for implementing the present invention.

[0061] FIGS. 2(a) and 2(b) are conceptual diagrams showing machine translation systems

[0062] FIG. 3 is a flowchart showing the processing for calculating compression contribution values for individual entry words (first embodiment).

[0063] FIG. 4 is a detailed flowchart showing the n-gram statistical analysis process routine at step S108 (first embodiment).

[0064] FIG. 5 is a flowchart showing a process routine for generating a new character translation code table according to the compression contribution values in accordance with the n-gram statistical analysis processing (first embodiment).

[0065] FIG. 6 is a flowchart showing a process routine for generating a dictionary entry word index (first embodiment).

[0066] FIG. 7 is a flowchart showing a process routine for acquiring a difference between entry words that are adjacent to each other (second embodiment).

[0067] FIG. 8 is a flowchart for the processing for calculating the compression contribution values of individual differential character strings (second embodiment).

[0068] FIG. 9 is a detailed flowchart showing the n-gram statistical analysis process routine at step S608 (second embodiment).

[0069] FIG. 10 is a flowchart showing a process routine for generating a new character translation code table in accordance with the compression contribution values provided by the n-gram statistical analysis processing (second embodiment).

[0070] FIG. 11 is a flowchart showing a process routine for generating a dictionary entry word index (second embodiment).

[0071] FIG. 12 is a flowchart showing a morphological analysis operation for machine translation.

[0072] FIG. 13 is a flowchart for dictionary search processing (first embodiment).

[0073] FIG. 14 is a flowchart for dictionary search processing (second embodiment).

[0074] FIG. 15 is a flowchart for a character string recovery operation (second embodiment).

[0075] The preferred embodiment of the present invention will now be described in detail while referring to the accompanying drawings.

[0076] A. Hardware environment for implementing machine translation

[0077] Entry word index data compressed by a compression method according to the present invention are employed by a dedicated machine translation processing apparatus, or by a general purpose personal computer for the execution of a machine translation program.

[0078] FIG. 1 is a schematic diagram illustrating the hardware arrangement of a typical personal computer (PC) 100 according to the present invention. The PC 100 conforms to the OADG (PC open Architecture Developer's Group) specifications, and either “Windows 95” ? of Microsoft Corp. or “Os/2” of IBM Corp. is mounted as an operating system (Os). The individual sections will now be described.

[0079] A CPU 11, a main controller, executes various programs under the control of the OS. The CPU 11 is, for example, a CPU “Pentium” chip or an “MMX technology Pentium” chip, each of which is produced by Intel Corp.

[0080] The CPU 11 is connected to hardware components, which will be described later, through a processor bus 12, which is connected to its external pins; a PCI (Peripheral Component Interconnect) bus 16, which acts as a local bus; and an ISA bus (Industry Standard Architecture) bus 18, which acts as a system bus.

[0081] The processor bus 12 and the PCI bus 16 communicate with each other across a bridge circuit (a host-PCI bridge) 13. The bridge circuit 13 in this embodiment includes a memory controller for controlling an operation for accessing a main memory 14, and a data buffer for absorbing a data transfer speed difference between the buses 12 and 16.

[0082] The main memory 14 is volatile memory and is used as a writing area for an executing program, or as a work area for the program. Generally, the main memory 14 consists of a plurality of DRAM (Dynamic RAM) chips. A memory capacity of, for example, 32 MB is provided as a standard and can be expanded to 256 MB. The programs to be executed include device drivers that access an OS, such as Windows 95 or peripheral devices, and various application programs, such as a machine translation program.

[0083] An L2-cache 15 is high-speed memory for absorbing the time required by the CPU 11 to access the main memory 14. A very limited amount of code and data that the CPU 11 frequently accesses are temporarily stored in the L2-cache 15. Generally, the L2-cache 15 consists of SRAM (static RAM) chips, and its memory capacity is, for example, 512 KB.

[0084] The PCI bus 16 is a bus for a relatively fast data transfer (a bus width of 32/64 bits, a maximum operating frequency of 33/66 MHz and a maximum data transfer speed of 132/264 MBps). PCI devices, such as a video controller 20 and a card bus controller 23, that are operated at relatively high speeds are connected to the PCI bus 16. The PCI architecture was originated and advocated by Intel Corp., and implements a so-called PnP (Plug-and-Play) function.

[0085] The video controller 20 is a dedicated controller for the actual processing of graphics commands received from the CPU 11. The processed graphics information is temporarily written in a screen buffer (VRAM) 21, and is then read from the VRAM 21 and output as graphics data to an LCD (liquid crystal display) or a CRT (Cathode Ray Tube) display 22.

[0086] The card bus controller 23 is a dedicated controller for directly transmitting a bus signal on the PCI bus 16 to the interface connector (card bus) of a PC card slot 24A. A PC card 24B, which conforms to the specifications (e.g., “PC Card Standard 95”) established by the PCMCIA (Personal Computer Memory Card International Association)/JEIDA (Japan Electronic Industry Development Association), can be inserted into the card slot 24A. An example PC card 24B is a LAN card for network connection, an HDD incorporated card employed as an external storage device, or a SCSI (Small Computer System Interface) card for external connection to a SCSI device.

[0087] The PCI bus 16 and the ISA bus 18 are mutually connected by a bridge circuit (PCI-ISA bridge) 19. The bridge circuit 19 in this embodiment includes a DMA controller, a programmable interrupt controller (PIC) and a programmable interval timer (PIT). The DMA controller is a dedicated controller for performing a data transfer between a peripheral device (e.g., an FDD) and the main memory 14 that does not pass through the CPU 11. The PIC is a dedicated controller for executing a specific program (an interrupt handler) in response to interrupt requests (IRQ) from individual peripheral devices. The PIT is a device for generating a timer signal at a predetermined cycle. The cycle for the timer signal generated by the PIT is programmable.

[0088] The bridge circuit 19 in this embodiment also includes an IDE (Integrated Drive Electronics) interface for connecting external storage devices that conform to the IDE specifications. An IDE hard disk drive (HDD) 25 is connected to the IDE interface, and an IDE CD-ROM drive 26 is also installed by using an ATAPI (AT Attachment Packet Interface) connection. Another type of IDE device, such as a DVD (Digital video Disc or Digital Versatile Disc) drive, may be installed instead of the IDE CD-ROM drive. These external storage devices are exchangeably stored in a storage space called a “media bay” or a “device bay” in the system 100.

[0089] The data transfer speed of the HDD 25 is superior to that of other external storage devices. A software program (an OS or an application) copied to the HDD 25 is in the standby state for use by the system 100 (i.e., installation is completed). The CD-ROM drive 26 and a DVD drive handle storage mediums, such as a CD and a DVD. A computer program to be installed in the system 100, for example, can supplied on a CD or a DVD.

[0090] The bridge circuit 19 in this embodiment has a USB route controller for connecting a USB (Universal Serial Bus), a general purpose bus, and a USB port 27. The USB supports a hot plugging function for the insertion and removal of an additional peripheral device (a USB device) while the system 100 is powered on, and a plug-and-play function for automatically identifying a newly connected peripheral device and for re-configuring a system configuration. A maximum 63 USB devices can be connected to a single USB port in a daisy chain manner. An example USB device is a keyboard, a mouse, a display motor or a printer (not shown).

[0091] The ISA bus 18 is a bus that has a lower data transfer speed (a bus width of 16 bits and a maximum data transfer speed of 4 MBps) than has the PCI bus 16. The ISA bus 18 is used for the connection of peripheral devices, such as a ROM 17, a modem card 28, a real time clock (RTC) 29, an I/O controller 30, a keyboard/mouse controller (KMC) 34 and an audio controller 37, that are driven at a relatively low speed.

[0092] The ROM 17 is nonvolatile memory for the permanent storage of a code group (BIOS: Basic Input/Output System) for the input and output signals for the hardware components, such as a keyboard 35 and a floppy disk drive (FDD) 31, and a test program (POST: Power On Self Test) that is run when the system 100 is first powered on.

[0093] The modem card 28 is a device for transmitting digital computer data across an analog public switched telephone network (PSTN). The modem card 28 includes circuit components, such as a signal processor (a modem chip), for modulating data to be transmitted and demodulating received data, and a data access arrangement circuit (DAA) for connecting a modem to a public switched telephone network in accordance with the line switch standards of individual countries.

[0094] The real time clock (RTC) 29 is a device for measuring the current time. Generally, the RTC 29 and a CMOS memory (not shown) are mounted together on a single chip. The CMOS memory is used to store information, such as system configuration information (a BIOS setup value) and a power ON password, that is required for the security/safety of the system 100. The RTC/CMOS 29 is backed up by a reserve battery (ordinarily a coin battery: not shown) so that the contents obtained by measurement and the stored data are not lost when the system 100 is powered off.

[0095] The I/O controller 30 is a peripheral controller for driving the floppy disk drive (FDD) 31, and for controlling the input/output of parallel data (PIO) through a parallel port 32 and the input/output of serial data (SIO) through a serial port 33. A printer, for example, is connected to the parallel port 32 and a joystick is connected to the serial port 33.

[0096] The keyboard/mouse controller (KMC) 34 is a peripheral controller for fetching as scan code data input at the keyboard 35, or as coordinate locations designated by the pointing device 36.

[0097] The audio controller 37 is a dedicated controller for processing the input/output of an audio signal, and includes a CODEC circuit (Coder-DEcoder, an A/D and D/A converter having a mixing function) for digital recording and the playing of audio signals. An audio signal that is received originates as input at a microphone 39, or as line input data originating at an external audio device (not shown). A generated audio signal is amplified by an audio amplifier and the resultant signal is released at a loudspeaker 38, or an audio signal is output to a line to an external audio device (not shown). one or more PCI bus slots 16A or ISA bus slots 18A are provided at one end of the bus 16 or the bus 18. PCI adaptor cards 16B and ISA adaptor cards 18B respectively can be plugged into the bus slots 16A and 18A. An example adaptor card is a LAN card for the connection of the PC 100 to a network. Another example is the SCSI card for the external connection of the PC 100 to a SCSI device, such as an HDD, a CD-ROM drive or a printer.

[0098] A typical user of the personal computer 100 can operate the system by using the keyboard 35 or the mouse 36 to execute various application programs, such as word processing, spreadsheet and communication programs, and to provide assistance in the performance of a job while he or she is viewing a display screen. For example, a user can install, in the computer system 100, a machine translation program recorded on a CD or an FD by copying it from the CD-ROM drive 26 or the FDD 31 to the HDD 25. Or, a desired software program can be installed in the computer system 100 by transferring a file from a remote server (Web server) to the HDD 25 through a network. A computer system 100 in which a machine translation program is installed and is executing serves as a machine translation system.

[0099] So-called personal computers that are currently available on the market fully satisfy the hardware conditions that will enable them to serve as a computer system 100 such as is shown in FIG. 1. Although many electric circuits other than those shown in FIG. 1 are required to construct the computer system 100, they are well known to one having ordinary skill in the art. And as they are not directly related to the subject of the present invention, no explanation for them will be given. Further, it should be noted that, to avoid making the drawings too complex, only one part of the connections between the hardware blocks in FIG. 1 is shown.

[0100] B. Machine translation system

[0101] A machine translation system incorporating dedicated hardware for machine translation, or a general purpose personal computer for executing a machine translation program, one of the conceptual system structures shown in FIG. 2.

[0102] In FIG. 2(a) is schematically shown a general machine translation system 200. The system 200 comprises a data processor 210, an input unit 220, a display unit 230 and an output unit 240. The data processor 210 includes components, such as a CPU 11 and a memory 14, mounted on a motherboard. The display unit 230 is equivalent to a display 22. The input unit 220 includes a keyboard 35 and a mouse 36. The output unit 240 includes a printer for printing the obtained processing results, and external storage devices, such as an HDD 25 and an FDD 31 for storing data.

[0103] The data processor 210 includes an editing section, a translation engine and a dictionary. The editing section reads text to be translated from an external storage device, such as the HDD 25, or provides, with the input unit 220, an environment for the editing of text on the display unit 230.

[0104] The translation engine, the core of the system 200, refers to the dictionary to translate original text in the first language (English), which is supplied by the editing section, to translated text in the second language (Japanese).

[0105] The dictionary generally consists of entry word index data and storage space where translation data are stored for individual entry words. The translation engine performs search of the entry word index to acquire the translation data. A currently available machine translation system 200 tends to prepare a dedicated dictionary for each genre, such as an art dictionary or a sports dictionary, in addition to the basic system dictionary.

[0106] In FIG. 2(b) is schematically shown a special machine translation system 200 for the translation of text on the Internet, i.e., the translation of Web pages. The system 200 comprises a data processor 210 and a network sub-system 250.

[0107] The network sub-system 250 includes a device for connecting the computer system 100 to the Internet; specifically, a device such as a modem card 28 for effecting a connection across a public switched telephone network, or a LAN adaptor card 16B for effecting a connection with a LAN. If the modem card 28 is employed, a dial-up IP connection to the Internet is established by a service provider, and if the LAN adaptor card 16B is employed, a gateway connection to the Internet across a router can be established.

[0108] The data processor 210 is physically constituted by components mounted on a motherboard, including the CPU 11 and the memory 14, and theoretically is constituted by cooperative operation with a translation proxy, a translation engine and a WWW browser.

[0109] The WWW browser is a computer program that serves as a so-called “Internet tour guide,” and is, for example, the “Netscape Navigator” program from of Netscape Corp. The WWW browser provides a user interface for input or for making a site connection using a URL (Universal Resource Locator), and can also acquire a file (normally an HTML (HyperText Markup Language) file) from a WWW server designated by the URL, interpret the contents of the file and display the results on the display 22.

[0110] The machine translation system in this embodiment has a proxy function, and upon the receipt of a request from the WWW browser, performs a file download process, while being interposed with the WWW server inbetween. The translation proxy transmits the text portion in a downloaded HTML file to the translation engine to charge it with the translation work. The translation engine refers to the dictionary and translates the received original text in the first language (English) into translated text in the second language (Japanese). When the WWW browser receives the translation results from the translation proxy, it displays the results on the display 22 along with an image file (a GIF file or a JPEG file) described in the HTML file.

[0111] The dictionary generally consists of entry word index data and storage space where translation data are stored for individual entry words. The translation engine performs search of the entry word index to acquire the translation data. A currently available machine translation system 200 tends to prepare a dedicated dictionary for each genre, such as an art dictionary or a sports dictionary, in addition to the basic system dictionary.

[0112] C. Processing for the compression of entry word index data in a dictionary

[0113] The processing for the compression of entry word index data will now be described in detail.

[0114] Table 1 shown an example entry word index. This is an extract of one part of an upper portion of an entry word index for a system dictionary that is included in the “King of Translation” sold by IBM Japan, Co., Ltd. In the following explanation, it is assumed that one character is represented by one byte. Table 1

[0115] a-bomb

[0116] a-cappella

[0117] a-deux

[0118] a-fond

[0119] a-fortiori

[0120] a-la-carte

[0121] a-la-king

[0122] a-la-mode

[0123] a-level

[0124] a-number

[0125] a-posteriori

[0126] a-priori

[0127] a-tempo

[0128] a.c.

[0129] a.m.

[0130] a.w.O.l.

[0131] a/c

[0132] aardvark

[0133] ab-initio

[0134] ab.

[0135] abaci

[0136] aback

[0137] abacus

[0138] abaft

[0139] abalone

[0140] abandon

[0141] abandoned . . .

[0142] Then compressed entry word index data are loaded into the memory 14 of the computer 100, which functions as the translation system, or is resident in the memory 14. Each time the system 100 activates the machine translation program, the compression process for the entry word index data may be performed, and the compressed entry word index data may be loaded into the memory 14. However, taking into consideration the use of the same compressed entry word index data, a maker for a machine translation program may compress entry word index data in advance, and may store the compressed entry word index data, in addition to the machine translation program, on a storage medium, such as a compact disk, which is then sold or distributed. Also in such a case, the compression process can be performed in a hardware environment (see FIG. 1) equivalent to the general purpose computer system 100 employed by a user that operates a machine translation program.

[0143] C-1. First embodiment

[0144] First, a first embodiment for compressing entry word index data will be described while referring to FIGS. 3 to 6.

[0145] n-gram statistical analysis process:

[0146] FIG. 3 is a flowchart showing the processing for calculating a compression contribution value for each entry word. The processing is positioned as a pre-process for the entry word index data compression processing.

[0147] The compression contribution value represents the compression effect imposed on the entry word index data when a character string of n characters (i.e., n bytes) or more is replaced by a character string of less than n characters (one byte in this case). It would be easily understood that the compression contribution value is large when a character string that frequently appears in an entry word index, or a character string that consists of many characters (many bytes), is replaced by a single character (i.e., a one-byte code). The frequencies at which character strings having n characters (n=2, 3, . . . ) appear in the entry word index are calculated using the so-called n-gram statistical analysis. The compression contribution value when a character string having n characters, i.e., n bytes, is substituted with one byte code is acquired by multiplying the count at which the character string appears in the entry word index, and a byte difference (n−1). The individual steps in the flowchart in FIG. 3 will now be described in detail.

[0148] A first IF loop constituted by a conditional sentence (step S100), “Is there an unused entry word?” is used to examine the n-gram statistics for the entire entry word index.

[0149] In the first IF loop, initially, the first remaining entry word is read from the original entry word index, and is substituted into variable REST (step S102). Then, value 2 is substituted into N (step S104), and the processing is initiated for the 2-gram statistical analysis.

[0150] In the second IF loop constituted by a conditional sentence (step S106), “Is N equal to or smaller than the length of the REST character string?,” the n-gram statistical analysis process is performed for the character string REST (step S108, described in detail later). When the n-gram statistical analysis process for N=2, i.e., the 2-gram statistical analysis process has been completed, N is incremented by one (step S110), and the same IF loop processing (i.e., the (N+1)-gram statistical analysis process) is repeated.

[0151] When N exceeds the length of the character string REST, it is assumed that the n-gram statistical analysis process for the character string REST has been terminated, and at branch “No” of the decision block S106, program control exits the second IF loop and returns to step S100.

[0152] At step S100, the acquisition of the next entry word in the entry word index is attempted. If the n-gram statistical analysis process is terminated for all the entry words in the entry word index, program control exists the first IF loop at branch “No” of decision block S100. The termination of the first IF loop represents the completion of the collection of the n-gram statistic data. At this time, a tentative n-gram statistic table is generated.

[0153] Table 2 shows an example tentative n-gram statistic table. This reflects the results obtained by the statistical analysis process when the first IF loop is terminated in FIG. 3 for the entry word index data in a system dictionary that is included in the machine translation software the “King of Translation” sold by IBM Japan Co., Ltd. The individual entries in the statistic table include extracted character strings having n characters, i.e., n bytes, and fields in which are stored the frequencies at which these character strings appear in the entry word index. For example, the 25th entry in Table 2 indicates that character string “ess” appears in the entry word index at 4321 times.

[0154] Then, a compression contribution value when each character string having n characters, i.e., n bytes, in the statistics data is replaced with a one byte code is calculated (step S120). Sequentially, the entries in the statistic table are sorted in the descending order of their compression contribution values (step S122). As is described above, a compression contribution value is acquired by multiplying the frequency count and a difference of bytes (n−1).

[0155] At step S124, overlaps in the statistics are removed. An overlap in the statistics is, for example, where for a long character string “ABCD,” the frequency counts for shorter character strings “ABC,” I^?BCD,” “AB,” “IBC” and “CD,” which are included in “ABCD,” are obtained by overlapping the frequency count of the string “ABCD.” Since the longer character string has a greater compression contribution value, the long character string should remain in the statistic table. Therefore, the frequency count for the character string “ABCD” must be subtracted from the frequency counts in the individual entries for the short character strings “ABC,” “BCD,” “AB,” “BC” and “CD.” For example, when the frequency counts for “ation” and “tion,” in the statistic table generated immediately after the first IF loop is terminated, are 1622 and 2398, the frequency count 1622, which is a double count for “ation,” is subtracted from the frequency count 2398 of “tion,” and the value 776 (=2398−1622) is the true frequency count for the character string “tion.”

[0156] After the overlaps of the statistics are removed at step S124, the entries in the statistic table are sorted again in accordance with the descending order of the compression contribution values (step S126).

[0157] Table 3 shows a statistic table obtained by sorting the entries in accordance with their compression contribution values. This is the result obtained by processing the entry word index data in a system dictionary included in the “King of Translation.”

[0158] As is apparent from Table 3, the compression contribution value 9315 for character string “ness,” which is the first entry, is the highest, and compression contribution value 6488 for character string “ation” is the second highest.

[0159] FIG. 4 is a detailed flowchart showing the n-gram statistical analysis process routine at step S108. The individual steps will now be described.

[0160] At step S200, the length of a character string for an entry word that is being processed (i.e., it is substituted into the variable REST) is substituted into variable LEN. At step S202 a check is performed to determine whether N is equal to or smaller than LEN. When N exceeds LEN, the n-gram statistical analysis process is not required (there are no n-gram statistics for character strings having (N−1) characters, for example). Program control exits at branch “No” at decision block S202 and the process routine is terminated. When N is equal to or smaller than LEN, program control branches to “Yes” and the following process is performed.

[0161] At step S204 a value of 1 is substituted into variable J. The variable J is a variable for designating a character string segment that consists of the Jth and the following characters of the character string REST.

[0162] In the IF loop constituted by a conditional sentence (S206), “Is J equal to or smaller than LEN−N+1, ” the n-gram statistic analysis is conducted for character strings having N characters, which are included in the character string segment consisting of the Jth and following characters of the character string REST in the process. When J exceeds LEN−N+1, no character strings having N or more characters remain in the segment consisting of Jth and following characters of the character string REST. Program control exits at branch “No” at decision block S206 and the process routine is terminated. When J is equal to or smaller than LEN−N+1, the following step is performed.

[0163] At step S208 a check is performed to determine whether a character string having N characters beginning with the Jth character of the character string REST already exists in the statistic table. If REST=“ABCD,” and J=2 and N=2, a check is performed to determine whether character string BC, which consists of two characters beginning with the second character of the character string ABCD, is present in the statistic table. If a corresponding entry exists in the statistic table, the frequency count of the entry is incremented by one (step S210). When no such entry is found in the statistic table, a new entry is added and its frequency count is set to 1 (step S212).

[0164] The n-gram statistical analysis has been conducted for a character string having N characters beginning at the Jth character of the character string REST, and J is incremented by one (step S214). Program control then returns to step S206 to repeat the n-gram statistical analysis for a character string having N characters beginning at the (J+1)th character.

[0165] Generation of character translation code table:

[0166] After the statistic table has been prepared in which entries are arranged in accordance with the descending order of their compression contribution values in the process routine in FIGS. 3 and4, a character code translation table for replacing a character string with code is generated. To embody the present invention, a new table for translating characters into code may be designed. In this embodiment, an ASCII (American Standard Code for Information Interchange) code table is employed that is well known and widely used as a table for assigning alphanumerical characters to code, and unused columns in this code table are newly assigned for character strings having high compression contribution values. The advantage of the employment of the ASCII code table is that conventional code can be used unchanged for regular alphanumerical characters, such as a, b, c, . . . and 0, 1, 2, . . . . The ASCII code table conforms to the specifications established by ANSI (American National Standards Institute).

[0167] FIG. 5 is a flowchart showing a process routine for generating a new character translation code table in accordance with compression contribution values obtained in the n-gram statistical analysis process. The individual steps will now be explained.

[0168] First, character strings in a count equivalent to the number of unused areas in the character translation code table are extracted from the high ranks of the statistic table (step S300). When the ASCII code table is used as the character translation code table, there are 185 unused columns (a case where English capital letters are not used), and only 185 highly ranked entries in the statistic table need be acquired.

[0169] Then, the obtained character strings are sorted in alphabetical order (step S302). Each of the sorted character strings is assigned a position, beginning with the first unused area of the character translation code table (step S304). The character strings are assigned positions in alphabetical order because this facilitates the performance of a following dictionary search process, which will be described later.

[0170] Table 4 shows a character translation code table prepared during the process routine in FIG. 5. The table is based on the ASCII code table, and conventional codes are assigned unchanged for regular alphanumerical characters, such as a, b, c . . . and 0, 1, 2, . . . (in Table 4, the conventional column assignments in the ASCII code table displayed are enclosed in frames). A character string “ab” having a high compression contribution value is assigned for unused column 0x01 in the ASCII code table, and character string “ot” is assigned for unused column 0xc9 in the table.

[0171] It should be noted that Table 4 shows the results obtained by processing the previously described entry word index data in a system dictionary included in the “King of Translation.”

[0172] Generation of dictionary entry word index:

[0173] When a new character translation code table is prepared, this is employed to generate a new dictionary entry word index. In Table 4 representing character translation code, a character string having n characters, i.e., n bytes (n is an integer greater than 1) is replaced with a one-byte code (previously described). Among the entry words, since a character string of n bytes that has a high compression contribution value is replaced by one byte code in accordance with the character translation code table, a compression effect of (n−1) bytes can be provided by preparing a new entry word index.

[0174] FIG. 6 is a flowchart showing the process routine for generating (compressing) a dictionary entry word index. The individual steps will now be explained.

[0175] The first IF loop, constituted by the conditional sentence (step S400), “Is there an unprocessed entry word?,” initiates the compression process for the entire entry word index.

[0176] In the first IF loop, the first remaining entry word is extracted from the original entry word index, and is substituted into a variable STR (step S402). An initial value of 1 is substituted into variables I and J, and the length of the character string STR is substituted into variable LEN (step S404). The variable I is used to designate the Ith character of the original character string STR, and the variable J is used to designate the Jth character of a new character string NEW.

[0177] In the second IF loop, constituted by the conditional sentence (step S406), “Is I equal to or smaller than LEN,” the compression process for the character string STR is performed. In the compression process, the individual character string segments of the character string STR are replaced by codes from the character translation code table.

[0178] First, a character string segment that consists of the Ith and the following characters of the character string STR is compared with each character string in the character translation code table shown as Table 4 (step S408). This comparison is performed in the reverse direction, starting at the last entry in the character translation code table. Since character strings are assigned in the character translation code table in alphabetic order (see Table 4), the table is searched in the reverse direction so that character string having more characters can be examined first in the comparison process. When, for example, a character string segment “lity” exists at the Ith and the following characters of the character string STR, “lit” and “lity” are selected as candidate matching character strings in the Table 4, and the character string segment is first compared with “lity,” which appears later in the alphabet order (i.e., has more characters).

[0179] If a character string that matches the character string segment that consists of the Ith and the following characters of the character string STR is found in the character translation code table, the matching code is substituted into the Jth character of a new character string NEW (step S410), and the variable I is incremented by a number equivalent to the number of characters of this matching character string (step S412). For example, when the segment that consists of the Ith and the following characters of the string STR includes a 4-byte character string “ness,” the character string segment is replaced by a one-byte character “b9,” in accordance with the character translation code table. At this time, the variable I is incremented by four.

[0180] If in the code table there is no character string that matches the character string segment that consists of the Ith and the following characters of the character string STR, the Ith character of the original character string STR is substituted into the Jth character string of the new character string NEW (step S414), and the variable I is incremented by one (step S416).

[0181] After a matching code, or one character of the original string, is substituted into the Jth character of the new character string NEW, and the variable J is incremented by one (step S418), program control returns to step S406 to repeat the above described IF loop processing. When the variable I exceeds the character string length LEN, it means that the process for translating the original character string STR into the new character string NEW has been terminated. Program control exits the second IF loop at branch “No” at decision block S406. At step S420, the original entry STR in the entry word index is replaced by the translated code NEW, and program control thereafter returns to step S400.

[0182] At step S400, a check is performed to determine whether unprocessed entry words remain in the entry word index. If so, the above described process is repeated for the remaining entry words. If there is no unprocessed entry word, it is assumed that the entire entry word index has been processed. Program control thereafter exits the routine at branch “No” at decision block S400, and the processing routine is terminated.

[0183] Table 5 shows one part of the new entry word index that is generated while being compared with the original entry words. In the new entry word index, one byte numbers are listed using the hexadecimal numbering system.

[0184] As is apparent from Table 5, entry word “a-bomb” is compressed into five bytes of code, “61 2d 19 6d 62,” whereas entry word “abandon,” which has seven characters, i.e., seven bytes, is replaced by the three-byte code “01 0c c3,” so that a compression effect of four bytes is obtained. Entry word “able,” which has four characters, i.e., four bytes, is replaced by the one-byte code “02,” so that a compression effect of three bytes is obtained.

[0185] As an experimental result, when the compression method in this embodiment was applied for the entry word index of the system dictionary for the “King of Translation,” the original entry word index of 625 Kbytes was compressed to a length of 388 Kbytes. When the amount of entry word index data is small, they can be made resident in the main memory 14 of the computer system 100, without being exchanged (swapped out). Since the access speed for memory-resident data is high, an increase in the dictionary search speed is obtained. Especially for a machine translation system that prepares some dictionaries, the compression of data to reduce its Isize is very effective when it is desired to make the entry word index data memory resident.

[0186] C-2. Second embodiment

[0187] A second embodiment for compressing entry word index data will now be described while referring to FIGS. 7 to 11. The second embodiment differs from the first embodiment in that a difference between entry word character strings that are adjacent to each other is acquired prior to the performance of a compression process based on the n-gram statistical analysis.

[0188] Differential process for entry word index data:

[0189] FIG. 7 is a flowchart showing the process routine for calculating a difference between adjacent entry word character strings. The individual steps will now be explained.

[0190] An empty character is entered as an immediately preceding character string PREV (step S500).

[0191] An IF loop, constituted by the conditional sentence (step S502), “Is there an unprocessed entry word?,” initiates the differential process for all the entry words.

[0192] In the IF loop, initially, the first remaining entry word character string is extracted from the original entry word index, and is substituted into the current character string CURR (step S504).

[0193] Then, a check is performed to determine how many characters starting at the beginning of the preceding character string PREV match those in the current character string CURR (step S506). The count of the matching characters and the difference in the character strings PREV and CURR are output (step S508).

[0194] The current character string CURR is substituted into the immediately preceding character string PREV (step S510), and program control returns to step S502.

[0195] At step S502, the acquisition of an entry word remaining in the original entry word index is attempted. If there is an unprocessed entry word, program control branches to “Yes” at the decision block S502, and the above described differential process is repeated. If the differential process has been completed for all the entry words, program control exits the routine at branch “No” at decision block S502, and the process routine is terminated.

[0196] Table 6 shows one part of the entry word index for which the differential process is performed while being compared with the original entry word index. The character string “a-bomb” is defined as the head of the entry word index. The original entry word index is that of a system dictionary in the “King of Translation.”

[0197] As is shown in Table 6, since the first to the sixth characters of entry word “abjection,” which is just below “abject,” match the character string “abject,” the matching character count 06 and a differential character string “ion” form a new entry word. Further, since the first to the sixth characters of the next entry word “abjectly,” which is in the two line below from “abject,” match the immediately preceding entry word “abjection,” the matching character count 06 and a differential character string “ly” forms a new entry word. An entry word index for which the differential process is performed is hereinafter called a “tentative entry word index.”

[0198] n-gram statistical analysis process:

[0199] FIG. 8 is a flowchart showing the processing for calculating a compression contribution value for each entry word. The processing is positioned as a pre-process for the tentative entry word index data compression processing.

[0200] The compression contribution value represents the compression effect imposed on the tentative entry word index data when a character string of n characters (i.e., n bytes) or more is replaced by a character string of less than n characters (one byte in this case). It would be easily understood that the compression contribution value is large when a character string that frequently appears in a tentative entry word index, or a character string that consists of many characters (many bytes), is replaced by a single character (i.e., a one-byte code). The frequencies at which character strings having n characters (n=2, 3, . . . ) appear in the tentative entry word index are calculated using the so-called n-gram statistical analysis. The compression contribution value when a character string having n bytes is substituted with one byte code is acquired by multiplying the count at which the character string appears in the entry word index, and a byte difference (n−1). The individual steps in the flowchart in FIG. 8 will now be described in detail.

[0201] A first IF loop constituted by a conditional sentence (step S600), “Is there an unprocessed entry word?” is initiated to examine the n-gram statistics for the entire tentative entry word index.

[0202] In the first IF loop, initially, a differential character string of the first remaining entry word is read from the tentative entry word index, and is substituted into variable REST (step S602). Then, value 2 is substituted into N (step S604), and the processing is initiated for the 2-gram statistical analysis.

[0203] In the second IF loop constituted by a conditional sentence (step S606), “Is N equal to or smaller than the length of the REST character string?,” the n-gram statistical analysis process is performed for the character string REST (step S608, described in detail later). When the n-gram statistical analysis process for N=2, i.e., the 2-gram statistical analysis process has been completed, N is incremented by one (step S610), and the same IF loop processing (i.e., the (N+1)-gram statistical analysis process) is repeated.

[0204] When N exceeds the length of the character string REST, it is assumed that the n-gram statistical analysis process for the character string REST has been terminated, and at branch “No” of the decision block S606, program control exits the second IF loop and returns to step S600.

[0205] At step S600, the acquisition of a differential character string for the next entry word in the tentative entry word index is attempted. If the n-gram statistical analysis process is terminated for all the entry words in the tentative entry word index, program control exists the first IF loop at branch “No” of decision block S600. The termination of the first IF loop represents the completion of the collection of the n-gram statistic data. At this time, a tentative n-gram statistic table is generated.

[0206] Then, a compression contribution value when each character string having n bytes in the statistics data is replaced with a one byte code is calculated (step S620). Sequentially, the entries in the statistic table are sorted in the descending order of their compression contribution values (step S622). As is described above, a compression contribution value is acquired by multiplying the frequency count and a difference of bytes (n−1).

[0207] At step S624, overlaps in the statistics are removed. An overlap in the statistics is, for example, where for a long character string “ABCD,” the frequency counts for shorter character strings “ABC,” “BCD,” “AB,” “BC” and “CD,” which are included in “ABCD,” are obtained by overlapping the frequency count of the string “ABCD.” Since the longer character string has a greater compression contribution value, the long character string should remain in the statistic table. Therefore, the frequency count for the character string “ABCD” must be subtracted from the frequency counts in the individual entries for the short character strings “ABC,” “BCD,” “BC,” “BC” and “CD.”

[0208] After the overlaps of the statistics are removed at step S624, the entries in the statistic table are sorted again in accordance with the descending order of the compression contribution values (step S626).

[0209] Table 7 shows a statistic table obtained by sorting the entries in accordance with their compression contribution values. This is the result obtained by processing the entry word index data in a system dictionary included in the “King of Translation.”

[0210] As is apparent from Table 7, the compression contribution value 9162 for character string “ness,” which is the first entry, is the highest, and compression contribution value 3745 for character string “ly” is the second highest.

[0211] FIG. 9 is a detailed flowchart showing the n-gram statistical analysis process routine at step S608. The individual steps will now be described.

[0212] At step S700, the length of a differential character string for an entry word being processed (i.e., it is substituted into the variable REST) is substituted into variable LEN. At step S702 a check is performed to determine whether N is equal to or smaller than LEN. When N exceeds LEN, the n-gram statistical analysis process is not required (there are no n-gram statistics for character strings having (N−1) characters, for example). Program control exits at branch “No” at decision block S702 and the process routine is terminated. When N is equal to or smaller than LEN, program control branches to “Yes” and the following process is performed.

[0213] At step S704 a value of 1 is substituted into variable J. The variable J is a variable for designating a character string segment that consists of the Jth and the following characters of the character string REST.

[0214] In the IF loop constituted by a conditional sentence (S706), “Is J equal to or smaller than LEN−N+1,1” the n-gram statistic analysis is conducted for character strings having N characters, which are included in the character string segment consisting of the Jth and following characters of the character string REST in the process. When J exceeds LEN−N+1, no character strings having N or more characters remain in the segment consisting of Jth and following characters of the character string REST. Program control exits at branch “No” at decision block S706 and the process routine is terminated. When J is equal to or smaller than LEN−N+1, the following step is performed.

[0215] At step S708 a check is performed to determine whether a character string having N characters beginning with the Jth character of the character string REST already exists in the statistic table. If REST=“ABCD,” and J=2 and N=2, a check is performed to determine whether character string BC, which consists of two characters beginning with the second character of the character string ABCD, is present in the statistic table. If a corresponding entry exists in the statistic table, the frequency count of the entry is incremented by one (step S710). When no such entry is found in the statistic table, a new entry is added and its frequency count is set to 1 (step S712).

[0216] The n-gram statistical analysis has been conducted for a character string having N characters beginning at the Jth character of the character string REST, and J is incremented by one (step S714). Program control then returns to step S706 to repeat the n-gram statistical analysis for a character string having N bytes beginning at the (J+1)th character.

[0217] Generation of character translation code table:

[0218] After the statistic table has been prepared in which entries are arranged in accordance with the descending order of their compression contribution values in the process routine in FIGS. 8 and 9, a character code translation table for replacing a character string with code is generated. To embody the present invention, a new table for translating characters into code may be designed. In this embodiment, an ASCII (American Standard Code for Information Interchange) code table is employed that is well known and widely used as a table for assigning alphanumerical characters to code, and unused columns in this code table are newly assigned for character strings having high compression contribution values. The advantage of the employment of the ASCII code table is that conventional code can be used unchanged for regular alphanumerical characters, such as a, b, c, . . . and 0, 1, 2, . . . . The ASCII code table conforms to the specifications established by ANSI (American National Standards Institute).

[0219] FIG. 10 is a flowchart showing a process routine for generating a new character translation code table in accordance with compression contribution values obtained in the n-gram statistical analysis process. The individual steps will now be explained.

[0220] First, character strings in a count equivalent to the number of unused areas in the character translation code table are extracted from the high ranks of the statistic table (step S800). When the ASCII code table is used as the character translation code table, there are 185 unused columns (a case where English capital letters are not used), and only 185 highly ranked entries in the statistic table need be acquired.

[0221] Then, the obtained character strings are sorted in alphabetical order (step S802). Each of the sorted character strings is assigned a position, beginning with the first unused area of the character translation code table (step S804). The character strings are assigned positions in alphabetical order because this facilitates the performance of a following dictionary search process, which will be described later.

[0222] Table 8 shows a character translation code table prepared during the process routine in FIG. 10. The table is based on the ASCII code table, and conventional codes are assigned unchanged for regular alphanumerical characters, such as a, b, c . . . and 0, 1, 2, . . . (in Table 8, the conventional column assignments in the ASCII code table displayed are enclosed in frames). A character string “abil” having a high compression contribution value is assigned for unused column 0x01 in the ASCII code table, and character string “ouse” is assigned for unused column 0xc9 in the table.

[0223] It should be noted that Table 8 shows the results obtained by processing the previously described entry word index data in a system dictionary included in the “King of Translation.”

[0224] Generation of dictionary entry word index:

[0225] When a new character translation code table is prepared, this is employed to generate a new dictionary entry word index. In Table 8 representing character translation code, a character string having n characters, i.e., n bytes (n is an integer greater than 1) is replaced with a one-byte code (previously described). Among the entry words, since a character string of n bytes that has a high compression contribution value is replaced by one byte code in accordance with the character translation code table, a compression effect of (n−1) bytes can be provided by preparing a new entry word index.

[0226] FIG. 11 is a flowchart showing the process routine for generating a dictionary entry word index from the tentative entry word index. The individual steps will now be explained.

[0227] First, at step S900 all the contents at the tentative entry word index (see Table 6), i.e., the original entry word character strings for individual entries in the index, matching character counts and differential character strings are read.

[0228] Then, the read data are arranged in ten entry groups, and for each group, the entry word that has the smallest matching character count is defined as a reference entry word (step S902). The “reference entry word” is an entry word for which the compression process for a differential character string is not performed and for which the original character string is registered unchanged in the dictionary entry word index. The matching character count for the entry word is reset to 0. The thus defined “reference entry word” is used when examining a dictionary to find a word. For details of this operation see sub-division D-2, which will be described later.

[0229] Following this, the original entry word character string for the first entry is extracted from the tentative entry word index, and is substituted into a variable STR (step S904). The first IF loop, constituted by the conditional sentence, “Is variable STR empty?,” initiates the compression process for the entire tentative entry word index.

[0230] At step S908, a check is performed to determine whether the acquired entry word is a reference entry word. Whether or not the character string is a reference entry word is determined by ascertaining whether a matching character count M in the entry is 0. If the obtained entry word is a reference entry word, it is not compressed and the original character string is registered unchanged. Program control branches to “Yes” at decision block S908, and the character string STR is output unchanged as a dictionary entry word index. Then, the original entry word in the succeeding entry is extracted from the tentative entry word index, and is substituted into the variable STR (step S950). Program control thereafter returns to step S906.

[0231] If the obtained entry word is not a reference entry word, its differential character string is compressed. In this case, first, a differential character string of an entry word is substituted into the variable STR (step S920). If the obtained entry word is “abhorrence,” differential character string “rence” is substituted into the variable STR (see Table 6). The initial value 1 is set in the variables I and J, and the length of the differential character string STR is set as the value in the variable LEN (step S922).

[0232] In the second IF loop, constituted by the conditional sentence (step S924), “Is I equal to or smaller than LEN,” the compression process for the differential character string STR is performed. In the compression process, the individual character string segments of the differential character string STR are replaced by codes from the character translation code table.

[0233] First, a character string segment that consists of the Ith and the following characters of the differential character string STR is compared with each character string in the character translation code table shown as Table 8 (step S926). This comparison is performed in the reverse direction, starting at the last entry in the character translation code table. Since character strings are assigned in the character translation code table in alphabetic order (see Table 8), the table is searched in the reverse direction so that character string having more characters can be examined first in the comparison process. When, for example, a character string segment “lity” exists at the Ith and the following characters of the differential character string STR, “lit” and “lity” are selected as candidate matching character strings in the Table 8, and the character string segment is first compared with “lity,” which appears later in the alphabet order (i.e., has more characters).

[0234] If a character string that matches the character string segment that consists of the Ith and the following characters of the differential character string STR is found in the character translation code table, the matching code is substituted into the Jth character of a new character string NEW (step S928), and the variable I is incremented by a number equivalent to the number of characters of this matching character string (step S930). For example, when the segment that consists of the Ith and the following characters of the string STR includes a 4-byte character string “ness,” the character string segment is replaced by a one-byte character “b9,” in accordance with the character translation code table. At this time, the variable I is incremented by four.

[0235] If in the code table there is no character string that matches the character string segment that consists of the Ith and the following characters of the differential character string STR, the Ith character of the original character string STR is substituted into the Jth character string of the new character string NEW (step S932), and the variable I is incremented by one (step S934).

[0236] After a matching code, or one character of the original string, is substituted into the Jth character of the new character string NEW, and the variable J is incremented by one (step S936), program control returns to step S924 to repeat the above described IF loop processing. When the variable I exceeds the character string length LEN, it means that the process for translating the differential character string STR into the new character string NEW has been terminated. Program control exits the second IF loop at branch “No” at decision block S924, and coded character string NEW is output as an entry word in the dictionary entry word index (step S940). The original entry word of the next entry is extracted from the tentative entry word index and is substituted into the variable STR (step S950). Program control thereafter returns to step S906.

[0237] At step S906, a check is performed to determine whether unprocessed entry words remain in the tentative entry word index. If so, the above described process is repeated for the remaining entry words. If there is no unprocessed entry word, it is assumed that the entire entry word index has been processed. Program control thereafter exits the routine at branch “No” at decision block S906, and the processing routine is terminated.

[0238] Table 9 shows one part of a dictionary entry word index that is generated by the processing routine in FIG. 11 in addition to data concerning the original entry words. Each entry in the dictionary entry word index need have only two fields (up to the second column from the left in the table) for entering a matching character count and differential character string code, and there is no necessity to include a matching character string or a differential character string, or the original character string.

[0239] As is apparent from Table 9, the original entry word “abhorrence” of ten characters, i.e., ten bytes, is replaced by the three byte code “05 d3 b7.” In other words, a compression effect of 7 (=10−3) bytes can be provided for this entry word.

[0240] As an experimental result, when the compression method in this embodiment was applied for the entry word index of the system dictionary for the “King of Translation,” the original entry word index of 625 Kbytes was compressed to a length of 315 Kbytes. When the amount of entry word index data is small they can be made resident in the main memory 14 of the computer system 100, without being exchanged (swapped out). Since the access speed for memory-resident data is high, an increase in the dictionary search speed is obtained. Especially for a machine translation system that prepares some dictionaries, the compression of data to reduce its size is very effective when it is desired to make the entry word index data memory resident.

[0241] The compression process for the dictionary entry word index data according to the first and the second embodiments, which have been described in detail in sub-division C, can be implemented when, for example, the computer system 100 in FIG. 1 performs a computer program that includes for each embodiment a compression processing routine.

[0242] D. Machine translation using a compressed entry word index

[0243] In this sub-division, machine translation processing using a compressed entry word index will now be described. The machine translation processing is implemented by performing on the computer system 100 a machine translation program that was explained in sub-division A. In the following explanation, it is assumed that one character is one byte.

[0244] In machine translation processing, generally, original text (English text in this case) is read for each sentence, and each word in the sentence is extracted and morphological analysis of the word is performed. FIG. 12 is a flowchart showing a morphological analysis operation. The individual steps will now be explained.

[0245] First, at step S1000 one sentence is read from the original text to be translated.

[0246] At step S1002, the first word is extracted, with a space being regarded as a separation. An IF loop, constituted by a conditional sentence (step S1004), “Has a word been extracted?,” initiates the sequential morphological analysis process for the individual words included in the sentence that has been read.

[0247] In the IF loop, at step S1006 the conjugated or inflected form of a word is examined to recover the base form. Conjugation and inflection include the following:

[0248] 1) “(e)s” for a plural form of a noun, or the present tense of a verb for a singular, third person form

[0249] 2) “ed” for the past tense/past participle form of a verb

[0250] 3) “ing” for the present participle form of a verb

[0251] 4) “er” for the comparative form of an adjective

[0252] 5) “est” for the superlative form of an adjective (no process is performed for an irregular conjugation.)

[0253] At step S1008 a word stem is searched for in the dictionary (for an irregularly conjugated word, the irregular conjugated form is employed for the search), and morphological analysis data, such as the part of speech and the definition, are acquired. The dictionary search is conducted in accordance with the procedures for performing search of the dictionary entry word index to find an entry word that corresponds to a word stem, and for acquiring morphological analysis data corresponding to that entry word.

[0254] As is described in sub-division C, the dictionary entry word index data are compressed, and are preferably resident in the main memory 14 of the computer system 100 during the machine translation processing. The dictionary search routine at step S1008 differs depending on which of the compression methods in the first and the second embodiment is employed for the compression of the entry word index. This will be explained in detail later.

[0255] When the morphological analysis data for the word are acquired, the succeeding word is extracted from the sentence (step S1010), and program control returns to step S1004.

[0256] When the above process routine is terminated for the entire sentence that was read, program control exits the IF loop at branch “No” at decision block S1004. At this time, since the part of speech and the definition data for each word in the sentence have been obtained (step S1012), the morphological analysis process for the sentence is terminated.

[0257] D-1. First embodiment

[0258] The first embodiment in this sub-division is a dictionary search process performed using an entry word index that is compressed using the compression method described in detail in sub-division C-1.

[0259] FIG. 13 is a flowchart showing the dictionary search processing. The individual steps will now be described.

[0260] First, at step S1100 a character string to be searched for is substituted into the variable STR. The character string to be searched for corresponds to a word that is extracted at step S1002 or S1010 and is returned to its base form at step S1006.

[0261] An initial value of 1 is substituted into variables I and J, and the length of the character string STR is substituted into variable LEN (step S1102). The variable I is used to designate the Ith character of the original character string STR, and the variable J is used to designate the Jth character of a new character string NEW.

[0262] In the IF loop, constituted by the conditional sentence (step S1104), “Is I equal to or smaller than LEN,” the compression process for the character string STR is performed in accordance with the character translation code in Table 4.

[0263] First, a character string segment that consists of the Ith and the following characters of the character string STR is compared with each character string in the character translation code table shown as Table 4 (step S1106). This comparison is performed in the reverse direction, starting at the last entry in the character translation code table. Since character strings are assigned in the character translation code table in alphabetic order, the table is searched in the reverse direction so that character string having more characters can be examined first in the comparison process. When, for example, a character string segment “lity” exists at the Ith and the following characters of the character string STR, “lit” and “lity” are selected as candidate matching character strings in the Table 4, and the character string segment is first compared with “lity,” which appears later in the alphabet order (i.e., has more characters).

[0264] If a character string that matches the character string segment that consists of the Ith and the following characters of the character string STR is found in the character translation code table, the matching code is substituted into the Jth character of a new character string NEW (step S1108), and the variable I is incremented by a number equivalent to the number of characters of this matching character string (step S1110). For example, when the segment that consists of the Ith and the following characters of the string STR includes a 4-byte character string “ness,” the character string segment is replaced by a one-byte character “b9,” in accordance with the character translation code table. At this time, the variable I is incremented by four.

[0265] If in the code table there is no character string that matches the character string segment that consists of the Ith and the following characters of the character string STR, the Ith character of the original character string STR is substituted into the Jth character string of the new character string NEW (step S1112), and the variable I is incremented by one (step S1114).

[0266] After a matching code, or one character of the original string, is substituted into the Jth character of the new character string NEW, and the variable J is incremented by one (step S1116), program control returns to step S1104 to repeat the above described IF loop processing. When the variable I exceeds the character string length LEN, it means that the process for translating the original character string STR into the new character string NEW has been terminated. Program control exits the IF loop at branch “No” at decision block S1104.

[0267] At step S1118, the generated code NEW is searched for in the entry word index in Table 5. When, for example, the original word is “abandonment,” the code NEW is “01 0c c3 af” and an entry word corresponding to this code need only be searched for in the entry word index. The binary search may be employed for this search. When an entry word exists in the entry word index, corresponding morphological analysis data are output, and the processing routine is terminated.

[0268] According to this dictionary search method, the recovery of the entry word index data is not required in order to search for the original entry word. Therefore, the decompression process is not required for the search conducted in the compressed entry word index, and the search speed is not deteriorated.

[0269] D-2. Second embodiment

[0270] The second embodiment in this sub-division is a dictionary search process that is performed using an entry word index compressed using the compression method described in detail in sub-division C-2.

[0271] FIG. 14 is a flowchart showing the dictionary search processing. The individual steps will now be described.

[0272] First, at step S1200 a character string to be searched for is substituted into the variable STR. The character string to be searched for corresponds to a word that is extracted at step S1002 or S1010 and is returned to its base form at step S1006.

[0273] At Step 71202, the dictionary entry word index in Table 9 is examined to find a reference entry word that either matches the character string STR or has a greatest matching character count.

[0274] The binary search may be employed for this search. The found reference entry word is substituted into a variable CAN as a candidate character string. When there are some reference entry words found that have the same matching character count, the entry word placed first in the alphabetic order is selected. When, for example, the character string STR is “abdication,” the most similar reference entry word “abdicable” is substituted into the variable CAN as a candidate character string.

[0275] At step S1204, a check is performed to determine whether the search character string STR matches the candidate character string CAN. If the character string STR matches the character string CAN, it means that the dictionary search has been successful. Program control therefore exits the loop at branch “Yes” at decision block S1204, and the processing routine is terminated.

[0276] When the character string STR does not match the character string CAN, at step S1206 the entry word next to the candidate character string CAN is extracted and is examined to determine whether it is a reference character string. In the process routine in FIG. 14, when the search character string STR is not a reference character string, it is compared with each entry word in a descending order, beginning with the reference entry word that has the largest matching character count. If, for example, the search character string STR is “abdication,” each entry word, “06 te,” “07 ion,” etc., is extracted in descending order beginning at the most similar reference entry word “abdicable,” and is compared with the character string STR. When the candidate character string CAN does not match the search character string STR and the next reference entry word is reached, it is assumed that no entry word that corresponds to the search character string STR exists in the entry word index. In this case, program control exits the loop at branch “No” at decision block S1206, and the dictionary search process is terminated.

[0277] When the entry word next to the candidate character string CAN is not a reference character string, the original character string for this entry word is recovered (which will be described later), and is substituted into the candidate character string CAN (step S1208). Program control then returns to step S1204, and the comparison process relative to the character string STR is repeated.

[0278] FIG. 15 is a flowchart showing the process (step S1208) for recovering a character string in the entry word index in Table 9 Fly that is not a reference entry word, i.e., the compressed entry word used to obtain the original entry word character string. The individual steps will now be described.

[0279] At step S1300, of an entry word character string to be recovered, a matching character count is substituted into a variable M, a differential character string is substituted into a variable DIFF, and the length of the differential character string (character count) is substituted into a variable LEN. The “entry word character string to be recovered” corresponds to an entry word succeeding the candidate character string CAN in the entry word index (see step S1206 in FIG. 14). When, for example, the candidate character string CAN is reference entry word “abhor,” the succeeding entry word is “05 d3 b7” (see Table 9), and the variable values M=5, DIFF=“d3 b7,” and LEN=2 are set.

[0280] At step S1302 the first M characters of the candidate character string CAN remain, while the (M+1)th and following characters are eliminated. For example, when CAN=“abhor” and M=5, the resultant string CAN=“abhor.”

[0281] At step S1304 an initial value of 1 is substituted into a variable I.

[0282] In the IF loop constituted by a conditional sentence, “Is I equal to or smaller than LEN?,” the process is repeated for recovering the original character strings from individual codes in the variable DIFF, while referring to the character translation code table in Table 8. At step S1308 the original character string is recovered from the first character translation code of the variable DIFF. If, for example, DIFF=“d3 b7” and I=1, a character string “re” that corresponds to the column “d3” in Table 8 is found and is added to the end of the candidate character string CAN (CAN=“abhorre”).

[0283] At step S1310 the variable I is incremented by one, and program control returns to step S1306, whereat the above described process for translating the character code into a character string is repeated.

[0284] When the variable I exceeds the character string length LEN, it means that all the character translation code in the variable DIFF have been replaced with the original character strings and the candidate character string CAN has been recovered. Program control exists the IF loop at branch “No” at decision block S1306, and the recovered candidate character string CAN is returned to the routine requesting source (step S1312). The processing is thereafter terminated.

[0285] According to this dictionary search method, at most only ten entry words need be recovered in order to search for the original entry word, and the recovery of the entire entry word index data is not required. Therefore, the decompression process is not required for the search performed in the compressed entry word index, and the search speed is not deteriorated.

[0286] E. Appendix

[0287] The present invention has been described in detail while referring to specific embodiments. However, it should be obvious to one having ordinary skill in the art that various modifications or revisions of the embodiments are possible within the scope of the present invention.

[0288] In these embodiments, an explanation was given for a machine translation apparatus (and an apparatus for compressing entry word index data for a dictionary) that is based on a so-called PC/AT compatible machine (“PC/AT” is a trademark of IBM Corp.) that conforms to the OADG specifications. However, the present invention can be applied in the same way by using another type of apparatus (e.g., an apparatus based on the NEC PC 98 series, or on the Macintosh from Apple computer Inc.), a machine that is compatible with either computer, or an apparatus for which the specified application is machine translation.

[0289] In addition, in these embodiments entry word index data for a dictionary are compressed using the compression methods that utilize the n-gram statistical analysis. It should be here noted that the compression methods of the present invention can also be used effectively for compressing another object (e.g., a common text sentence).

[0290] That is, although the present invention has been disclosed by using an example, it should not be limited to that example. To fully understand the subject of the present invention, the claims should be referred to.

[0291] Advantages of the Invention

[0292] As is described above, according to the present invention, provided are a method for compressing entry word index data for a dictionary to be used for machine translation; compressed entry word index data for a dictionary; and a method for searching for a word using the compressed entry word index data.

[0293] Further, according to the present invention, provided are a compression method that enables a search for compressed data to be performed without a decompression process being required; entry word index data for a dictionary to be generated by such a compression method; and a method for searching for a word using the compressed entry word index.