Language processing resources for automated mobile language translation

Automated language translation often involves language translation resources of significant size (e.g., 50-gigabyte phrase tables) and significant computational power exceeding the capabilities of many mobile devices. Remotely accessible servers capable of near-realtime, automated translation may be inaccessible or prohibitively costly while traveling abroad. Presented herein are adaptations of language translation techniques for offline mobile devices involving reducing the size and raising the efficiency of the language modeling resources. A word index may be provided that stores respective string representations of the words of a language, and maps respective words to a location (e.g., address or offset) of respective word representations within the word index. Language translation resources (e.g., phrase tables) may then specify logical relationships using the word index addresses of the involved words, rather than the string equivalents. This technique significantly condenses the language resources and provides faster, bidirectional access to the word representations of the language.

BACKGROUND

Within the field of computing, many scenarios involve automated language translation between input provided in a source language and output provided in a target language. Such techniques may not only include automated translation from a source natural language to a target natural language, but also between a first modality and a second modality of the same language (e.g., spoken and written words), and between two domains within the same language (e.g., describing a topic in technical language and in non-technical language).

Many types of language translation techniques may be applied to such scenarios. For example, for a request to translate a word sequence in a source language into a target language, a device may utilize a phrase table to map various phrases in the source language to equivalent phrases in the target language (e.g., using an English-to-French word reference identifying corresponding pairs or sets of words in each language). Additionally, the device may apply a language model that is capable of identifying, among two or more candidate selections and orderings of words in the target language, the candidate that is likely to be the most accurate and/or fluent translation of the word sequence in the source language. Such architectures may utilize a wide variety of techniques to perform the phrase selection and/or language modeling in order to provide automated translation techniques presenting an acceptable accuracy and/or fluency.

SUMMARY

While many types of translation techniques may be utilized in order to provide automated language translation, it may be appreciated that many such techniques are computationally intensive. In particular, the amount of data that is indexed for and accessed by such language translation techniques may be voluminous (e.g., phrase tables may approach fifty gigabytes), and applying complex analysis to the phrase table and/or language model may involve considerable memory consumption and processing power for cross-referencing and random access. Such models are typically feasible for computing devices with plentiful resources, such as computationally robust servers, but implementing such techniques on portable devices may be difficult due to resource constraints. Accordingly, many portable devices provide language translation by utilizing a remote server, e.g., sending the language portion for translation to the remote server over a wireless network and receiving back the translation. However, scenarios where language translation is often utilized also frequently involve high fees for mobile communication services, such as high roaming charges while using a mobile phone in a foreign country. Thus, while remote devices may provide plentiful connectivity to remote services while used in a home region, the accessibility of such services on an on-demand basis while traveling abroad may be limited or not feasible.

Provided herein are architectures for enabling the implementation of language translation techniques on mobile devices that do not involve on-demand, just-in-time communication with a translation server. In accordance with these considerations, mobile translation on a device may involve techniques for reducing the amount of data involved in translation resources, e.g., by reconfiguring the phrase table and/or language model to refer to the words of the source language and/or target language in a condensed manner. In particular, if respective words of a phrase in the source and/or target language are replaced with identifiers such as 32-bit integers, the phrase table and language model may be considerably reduced in size. Additionally, the logic specified thereby may be more efficiently executed if the data is presented as a comparison among integer arrays rather than more lengthy character strings (particularly where such character strings may involve typographical errors and homonyms). This result may be achieved by providing a word index for one or both languages, where the word maps respective character-based words of the source language as a number, such as an integer. While this technique marginally increases the computational burden by adding this mapping technique to the translation process, the application of the logic specified by the word index as numbers rather than a character string may alleviate or outweigh this computational burden. Additionally, it may be possible to use one word index both to translate words to index-based integers and vice versa, e.g., by specifying in the word index, for selective integers, the location of the string representation of the word in the word index (e.g., an offset from the start of the file, or from a particular location in the file). Thus, the same file may be used to identify the integer representation of the word from the string representation of the word, and may also, even more efficiently, identify the string representation of the word from the integer representation of the word (simply by seeking to the file position within the file and reading the string). This access technique be may particularly advantageous on devices having a limited amount of system memory and a larger but slower storage, because the language translation resources may be efficiently read directly from storage rather than being loaded into system memory. These and other features may provide various advantages in the configuration of a mobile device to perform offline translation in accordance with the techniques presented herein.

DETAILED DESCRIPTION

Within the field of computing, many scenarios involve automated translation of input from a first language into a second language for presentation to a user. Such translation techniques may include, e.g., translation from a first native language of the user into a second natural language; translation from a first modality of a language to a second modality of the same or a different language (e.g., translating spoken text to written text); and translation from a first domain of a language into a second domain (e.g., a conversion of a text from a technical presentation of information to a colloquial presentation of information). Many techniques have been devised for partially or wholly automating such translation, where various techniques may present comparative advantages with respect to translating to or from particular types of languages; various translation features, such as accuracy, fluency, and speed; and various scenarios wherein such techniques may be implemented.

Many such techniques utilize a translation model that provides logic for translating input from a first language into a second language. For example, a device may store a phrase table that specifies phrases in a target language that are equivalent to an input phrase in a source language. The phrase table may also provide many possible variations in a phrase, and the phrases of a passage in the source language may be arranged in many ways to suit the features of the target language, such as reordering the words to suit the characteristics and customs of the language. Accordingly, a language model may be provided that assists in selecting among and ordering the phrases identified by the phrase table in order to provide a translation resembling a native expression of the input in the second language. However, the language translation resources often provide an extensive set of translations, e.g., in order to cover a wide range of the translations of a phrase that may suit different scenarios and cover variations in meaning. For example, a phrase table that provides translations of single words between a source language and a target language may be comparatively small (e.g., providing one or more translations10,000source language words), but a bigram language model, providing one or more translations of each valid two-word sequence in the source language and possible translations, may cover 100 million two-word sequences, and trigram or longer n-gram language models may involve even larger amounts of data. Accordingly, the phrase table and/or language model may grow to sizes of 50 gigabytes or more in order to provide accurate translations, and may involve significant amounts of computational power to consider, concurrently, a large number of possible variations among candidate translations of a word sequence. Accordingly, the resources are often provided on high-capacity computational units, such as powerful servers with plentiful storage and computational capacity, in order to provide automated, near-realtime translation with acceptable accuracy.

FIG. 1presents an illustration of an exemplary scenario100featuring a user102of a device104providing a word sequence106in a source language110(e.g., in the Spanish language) and requesting the device104to provide a translation112in a target language114(e.g., in the English language). In this exemplary scenario100, the device104sends the word sequence106to a language translation server116for translation. The language translation server116evaluates respective words108of the word sequence106, and, using the phrase table118, identifies one or more candidate translations120corresponding to the word108, optionally identifying a prediction of the accuracy and fluency of the candidate translation120. Combinations of words108may also be evaluated using the phrase table118; e.g., identifying “un,” “buen,” and “dia” independently may result in the one-word translations “one,” “fair,” and “day,” but evaluating the word sequence “un buen dia” may yield the more likely phrase “a good day.” The language translation server116may then evaluate the candidate translations120using a language model122(often evaluated together with the logic specified by the phrase table118) to choose the translation112having the highest match with the source language116(e.g., having a highly predicted fluency in the target language according to the target language model). In this manner, the language translation server116may automatically provide the translation112to the device104for presentation to the user102.

B. Presented Techniques

While the exemplary scenario100ofFIG. 1provides an exemplary technique for configuring a language translation server116having plentiful computing resources to generate and provide the translation112to the user102of the device104, which may be accessed over a wired or wireless network while the user102is traveling. However, in many such scenarios, the connectivity of the device104while traveling may be unavailable, or may be prohibitively expensive due to roaming charges. Such connectivity limitations may restrict the reliance of the device104on a remote server for translation services, which is exacerbated by the high likelihood of demand for such services while traveling.

In view of these circumstances, it may be advantageous to provide language translation services that may be performed by the device104while not connected to a server. That is, while the device104may communicate with a server to receive language translation resources for later use, it may be desirable to enable the device104to use such resources in a disconnected manner. It may be appreciated that the limiting characteristics of such resources (particularly, the typical size and usage patterns) that complicate implementation on the device104may be resolvable.

Presented herein are techniques for generating and providing language translation resources that may be suitable for devices104having limited connectivity and/or limited computational resources, such as processor capacity and memory capacity (and in particular, devices104operating in a disconnected manner). Such techniques may also provide other general features, such as efficiency and flexibility, that may be advantageous for many types of devices104and scenarios. In particular, a phrase table108and/or language model122sometimes specify the words108and candidate translations120as comparisons between strings, but due to the large amount of data provided in these resources and comparisons involved, encoding string representations for direct comparison may be inefficient. Alternatively, respective words may be associated with arbitrarily selected identifiers that are more compact and easier to compare, such as an integer representing a hashcode of a string representation of a word108. However, using hashcodes may be disadvantageous due to the one-way nature of the computation (e.g., it may be difficult to identify the particular word108from a hashcode value) and the lack of uniqueness among such hashcodes (e.g., hashing collisions may cause two or more words108to map to the same hashcode). Thus, it may be advantageous to choose an identifier for the respective words108of a language that is not only compact and subject to efficient comparisons, but also reversible and/or unique.

FIG. 2presents an illustration of an exemplary scenario200featuring a set of language translation resources that may be usable to provide automated language translation on a device104with limited connectivity and/or computational resources, such as a mobile phone or tablet. In this exemplary scenario, in addition to a translation mapping218that enables translation from a word108in a source language110to a translation112in a target language114(such as a phrase table118or language model122), the device104may include at least one word index202storing a set of string representations210of the words108at respective index locations208within the word index202. Additionally, the word index202may include a word mappings table204comprising a set of word mappings206that enable an identification of the index location208of a string representation210of a word108in the word index202. For example, the device104may include a word mapping function for which a word mapping value may be identified for respective words108, such as a hash function212, which may be applied to respective words108to identify a hash value214for the string representation210of a word108. The source word index202may store a hashtable associating the hash value214for respective words108of the source language110with the index location208of the string representation210of the word108. Using the hash function212and the word mappings table204, the device104may identify the index location208for the word108, where the index location208is used to represent the word108in the translation mappings218. Additionally, a target word index228may encode string representations210of the words108of the target language114at particular index locations208within the target word index228, and these index locations208may be used as condensed identifiers of the words108. The translation mapping218may therefore specify the translation logic as a set of associations220between a word index sequence222of index locations208in the source word index202and at least one index location208respectively representing a word108of the translation112of the word index sequence222; i.e., the translated words224may be similarly identified in the translation mapping218as string representations210stored at target index locations208within the target word index228. Additionally, the target word index228may also provide a word mappings table204that may be used to convert words108of the target language114into a translation112in the source language.

A device104may utilize the resources illustrated in the exemplary scenario200ofFIG. 2in the following manner. A user102may provide a word sequence106in a source language110including at least one word108, and may request a translation112in a target language114. The device104may apply a word mapping function (such as a hash function212) to compute a word mapping value (such as a hash value214), which may be compared with the word mappings206of the word mappings table204to identify the index location208of a string representation210of the word108. The device104may access216the logic of the translation mapping218using the index locations208of the words108of the source language110, resulting in a set of translated words224in the target language114. The translated words224are also specified in the translation mapping218as target language indices208, which the device104may use to index into the target word index228to retrieve the string representations210of the words108in the target language114. In this manner, the device104may use the translation resources represented in the exemplary scenario200ofFIG. 2to generate an automated translation112of the word sequence106in the source language110to the target language114. Additionally, if translation from the target language114to the source language110is desired, the word mappings table204included in the target word index228may be used to perform this translation in the other direction.

Some embodiments utilizing the generation and use of the resources presented in this exemplary scenario200may provide one or more advantages as compared with other techniques. As a first example, the resources may present a smaller size than other techniques, due to the use of the index locations208to identify the words108of the languages in the translation mappings218rather than string representations210or other representations with a large size. For example, in scenarios featuring a comparatively small set of words108with comparatively short string representations210, respective words108may be identifiable with only a two-byte integer (optionally identifying a boundary on which the words108are aligned within the language translation resource, e.g., aligning the words108at four-byte address boundaries and dividing the address of a string representation210by four to generate the index location208representing the word108). Thus, the inclusion of the word index202may marginally increase the total data size of the language resource set, but generating the translation mappings218using the word index202may very significantly reduce the size of the language resource set. Although advantageous in many contexts, such significant reduction in data size may enable the inclusion of the language mapping resources on portable devices for offline language translation.

As a second exemplary advantage, the resources may be reusable. For example, a word mappings table204may be usable both to convert words108of a language to index locations208of string representations210within the word index202(usable for converting the words108from the language to a second language), and to convert index locations208into the string representations210of the words108of the language (usable for converting the words108from a second language to the language). If two word indices202are provided for two languages, each comprising a word mappings table204, along with a bidirectional translation mapping218, then translation may be provided from either language to the other language. Moreover, providing a word index202for each of several language may enable the reuse of the word index202both for converting from the language to any other language, and also for converting from any other language to the language.

As a third exemplary advantage, the use of the language translation resources may be efficiently accessed, which may be advantageous for devices with limited computational resources. As a first example, representing the words108in the translation mapping218by the index locations208of the string representations210in the word index enables a rapid lookup (i.e., simply seek to the specified address and read the string representation210at that address). Moreover, direct access into the binary representation of the word index202may be performed in storage, rather than having to load the word index202into active memory (which may be more limited) to access the word108. As a second example, specifying the logic of the translation mapping218may include comparisons among representations of words108, and using index locations208specified as integers may provide efficient logical evaluation as compared with comparisons of string representations210of the same words108. As a third example, using the index locations208avoids the complexities involved in collisions involving two or more words108having the same identifier. That is, while the hash function212may result in collisions between respective words108, these collisions may be resolved in the word mappings table204(e.g., as a bucket-based hashtable) to identify unique index locations208for respective words108, which may be more efficient than specifying the logic of the translation resources with representations of respective words108according to the hash value214of the word108, which may be susceptible to collisions. These and other advantages may be achievable through the generation and use of the mapping resources according to the techniques presented herein.

The techniques presented herein may be included in many types of embodiments.

FIG. 3presents a first exemplary embodiment of the techniques provided herein, illustrated as an exemplary method300of representing a language comprising at least two words108and at least one translation112of a word sequence. The exemplary method300may be implemented, e.g., as a set of instructions stored in a memory component of the device (e.g., a memory circuit, a platter of a hard disk drive, a solid-state storage device, or a magnetic or optical disc) that, when executed on a processor of the device, cause the device to represent the language in the memory according to the techniques presented herein. The exemplary method300begins at302and involves executing304the instructions on the processor. More particularly, the instructions are configured to store306in the memory a word index202comprising, for respective words108of the language, the word308stored at an index location208in the word index202, and a word mapping310that identifies the index location208of the word108in the word index202. The instructions are also configured to store312in the memory a translation mapping220identifying, for a word index sequence222comprising at least one index location208, the translation112of the words108located at the index locations208of the word index202. In this manner, the exemplary method300may generate the language resources as a representation of a language for use in automated language translation techniques, and so ends at314.

FIG. 4presents a second exemplary embodiment of the techniques provided herein, illustrated as an exemplary method400of translating a word sequence from a source language110to a target language114. The exemplary method400may be implemented, e.g., as a set of instructions stored in a memory component of a device (e.g., a memory circuit, a platter of a hard disk drive, a solid-state storage device, or a magnetic or optical disc) having a processor and a set of language translation resources such as illustrated in the exemplary scenario200ofFIG. 2(i.e., a source word index202for the source language110, a target word index228for the target language114, and a translation mapping218therebetween), optionally having been generated by the exemplary method300ofFIG. 3, where such instructions, when executed on the processor of the device, cause the device to represent the language in the memory according to the techniques presented herein. The exemplary method400begins at402and involves executing404the instructions on the processor. More particularly, the instructions are configured to, for respective words108of the word sequence106in the source language110, identify406the source index location208of the word108in the source word index202. The instructions are also configured to, using the translation mapping218, identify408a translation112of the source index locations208of the words18of the word sequence106, where the translation112comprises at least one target index location208in the target word index228. The instructions are also configured to, for respective target index locations208, retrieve410a string representation210of the translated word208in the target language114at the target index location208in the target word index228. The instructions are also configured to present412the translated words108in the target language114to the user102. In this manner, the device achieves an automated translation of the word sequence106from the source language110to a translation112in the target language114in accordance with the techniques presented herein, and so ends at414.

FIG. 5presents a third exemplary embodiment of the techniques presented herein, illustrated as an exemplary system506for automatically translating a word sequence106from a source language110into a translation112in a target language114. The exemplary system506may be implemented, e.g., as a set of instructions stored in a memory component of a device502(e.g., a memory circuit, a platter of a hard disk drive, a solid-state storage device, or a magnetic or optical disc) having a504processor and a set of language translation resources such as illustrated in the exemplary scenario200ofFIG. 2(i.e., a source word index202for the source language110, a target word index228for the target language114, and a translation mapping218therebetween), optionally having been generated by the exemplary method300ofFIG. 3, where such instructions, when executed on the processor504of the device502, serve as the components of an exemplary system506for performing automated translation. The exemplary system506comprises a word index identifying component508that is configured to, for respective words108of the word sequence106, identify the source index location208of the word in the source word index202. The exemplary system506also comprises a translation mapping component510that is configured to, using the translation mapping218, identify a translation112of the source index locations208of the words108of the word sequence106, where the translation112comprises at least one target index location208in the target word index228. The exemplary system506also comprises a translated word retrieving component512that is configured to, for respective target index locations208, retrieve a translated word108in the target language114at the target index location208in the target word index228, and to present the translated words108in the target language114. In this manner, the exemplary system506achieves the translation112of the word sequence106into the source language110.

Still another embodiment involves a computer-readable medium comprising processor-executable instructions configured to apply the techniques presented herein. Such computer-readable media may include, e.g., computer-readable storage media involving a tangible device, such as a memory semiconductor (e.g., a semiconductor utilizing static random access memory (SRAM), dynamic random access memory (DRAM), and/or synchronous dynamic random access memory (SDRAM) technologies), a platter of a hard disk drive, a flash memory device, or a magnetic or optical disc (such as a CD-R, DVD-R, or floppy disc), encoding a set of computer-readable instructions that, when executed by a processor of a device, cause the device to implement the techniques presented herein. Such computer-readable media may also include (as a class of technologies that are distinct from computer-readable storage media) various types of communications media, such as a signal that may be propagated through various physical phenomena (e.g., an electromagnetic signal, a sound wave signal, or an optical signal) and in various wired scenarios (e.g., via an Ethernet or fiber optic cable) and/or wireless scenarios (e.g., a wireless local area network (WLAN) such as WiFi, a personal area network (PAN) such as Bluetooth, or a cellular or radio network), and which encodes a set of computer-readable instructions that, when executed by a processor of a device, cause the device to implement the techniques presented herein.

An exemplary computer-readable medium that may be devised in these ways is illustrated inFIG. 6, wherein the implementation600comprises a computer-readable storage device602(e.g., a CD-R, DVD-R, or a platter of a hard disk drive), on which is encoded computer-readable data604. This computer-readable data604in turn comprises a set of computer instructions606configured to operate according to the principles set forth herein. Some embodiments of this computer-readable medium may comprise a nonvolatile computer-readable storage medium (e.g., a hard disk drive, an optical disc, or a flash memory device) that is configured to store processor-executable instructions configured in this manner. Many such computer-readable storage devices may be devised by those of ordinary skill in the art that are configured to operate in accordance with the techniques presented herein.

The techniques discussed herein may be devised with variations in many aspects, and some variations may present additional advantages and/or reduce disadvantages with respect to other variations of these and other techniques. Moreover, some variations may be implemented in combination, and some combinations may feature additional advantages and/or reduced disadvantages through synergistic cooperation. The variations may be incorporated in various embodiments (e.g., the exemplary methods ofFIGS. 3 and 4; the exemplary system506ofFIG. 5; and the exemplary computer-readable storage device502ofFIG. 2and the exemplary computing unit enclosure202ofFIG. 3) to confer individual and/or synergistic advantages upon such embodiments.

A first aspect that may vary among embodiments of these techniques relates to the scenarios wherein such techniques may be utilized.

As a first variation of this first aspect, these techniques may be implemented on many types of devices104, including workstations, servers, laptop and palmtop computers, phones, tablets, cameras, personal digital assistants (PDAs), and game consoles.

As a second variation of this first aspect, these techniques may be applied to translate among many types of languages, such as a first natural language and a second natural language; a first dialect of a language and a second dialect of the language; a colloquial version of a natural language and a standardized version of the natural language; and a translation between a technical language and a natural language. Some such translations may involve a transition among the domains of a language, e.g., a transition among a language specified for a first user102who is familiar with the specialized language of a particular technical area to the same language specified for a second user102who is not familiar with the technical area. Other translations may involve a translation from a first language modality of a natural language and a second language modality of the natural language (e.g., spoken language and written language, or a translation from a handwritten text to a printed text, such as optical character recognition (OCR) translation).

As a third variation of this first aspect, these techniques may involve many types of translation mappings218. As illustrated inFIG. 1, the translation mappings218may include a phrase table118and a language model122. However, many other types of translation mappings218are available in the field of automated language translation, and may provide translation logic referring to the words108of the respective languages according to the index locations208within the word indices202, and therefore may be compatible with the architectures and techniques presented herein. Many such variations may be devised by those of ordinary skill in the art and utilized in embodiments of the techniques presented herein.

D2. Word Index Layout

A second aspect that may vary among embodiments of these techniques relates to the layout of the word index202. It may be appreciated that many layouts may be selected to store the string representations210of the words108at particular index locations108and the word mappings table204associating such words108and the index locations108of the string representations210. Moreover, it may be appreciated that a particular layout may present various advantages with respect to other layouts, such as space efficiency, access efficiency, and/or flexibility (e.g., providing a partially loaded word mappings table204to allow the addition of entries for new words108).

As a first variation of this second aspect, the string representations210of the words108may be encoded according to various formats, such as American Standard Code for Information Interchange (ASCII), UCS Transformation Format-8-bit (UTF-8), or Unicode. Alternatively, the string representations210may be stored as graphic depictions of the words108, such as pixel-map representations of glyphs for pictogram languages. The string representations210may also be compressed, such as using the Standard Compression Scheme for Unicode (SCSU) technique for Unicode string encoding.

As a second variation of this second aspect, the index locations208of respective string representations210may be specified in various ways. As a first example, the index location208may be specified as a direct-access address within the binary representation of the word index202, such that seeking directly to the index location208yields the starting position of the string representation210of the word108. As a second example, the index location208may be specified as an offset, e.g., from the end of the end of the word mappings table204(such that the first stored string representation210may be stored at offset 0x0000), or a reverse offset from the end of the binary representation of the word index202. As a third example, the index location208may represent a multiple of an address or offset; e.g., the string representations210may be padded to start at four-byte boundaries within the word index202, and the index location208may be multiplied by four for use as an address or offset. This example may marginally increase the size of the word index202due to the padding, but may enable a larger number of words string representations210(and therefore words) to be encoded using index locations208of a particular size, such as two-byte index locations208, and may therefore provide significant space savings in the translation mapping218. As a fourth example, the word index202may be compressed in various ways, and the index locations208may be selected to identify the locations of the string representations210in either the compressed or the uncompressed version of the word index202.

As a third variation of this second aspect, the word mappings206comprising the word mappings table204may be specified in various ways, such as a sorted or unsorted array, a binary tree, or a table. Various representations may provide advantages in terms of speed of generation, space efficiency, and access efficiency. In some scenarios, it may be advantageous to provide a bucket-list hashtable representation, wherein respective words108may be indexed according to the hash value214of the string representation210of the word108computed using a hash function212, and where a collision among two or more words108may be resolved by storing all of the words108in an array that may be examined linearly to identify the entry for the selected word108, or in a second hashtable generated by indexing the words108according to a second hash function212. Additionally, the word mappings table204may include additional information about respective words108, such as the probability that a particular word108or word phrase in the source language110maps to a particular translation112in the target language114. Such mapping probabilities may be stored, e.g., in the word mappings206of the word mappings table204, and/or in the translation mappings218(e.g., in the target language model122).

As a fourth variation of this second aspect, the target word index228may include or omit a word mappings table204. It may be appreciated that if translation is only desired from the source language110to the target language114, then the target word index228may only be accessed in order to extract the string representations210of the target index locations224specified by the translation mapping218, and the word mappings table204of the word index228may be unused. Accordingly, the word mappings table204of the target word index228may be omitted in furtherance of space efficiency, and/or the translation mapping218may provide unidirectional associations220between the word index sequences222and the translated words224. Conversely, if bidirectional translation is desirable, the target word index228may also include a word mappings table204in order to provide translation from the target language114back into the source language110.

As a fifth variation of this second aspect, the string representations210of respective words108of the source word index202and/or the target word index208may include a word header that provides information about the string representation210of the word108. For example, respective word headers may specify the word size (e.g., string length) of the string representation210of the word108, which may facilitate access through a fixed-length read and/or reduce the size of the word index202by enabling a removal of string-terminating null characters.

As a sixth variation of this second aspect, the word mappings table204may also include a word index header702that provides various information about the word mappings table204and/or the word index202, such as a version indicator of the word index202; the number of words108represented in the word index202; the size of the word mappings table204; the identification of a hash function212used to index the words108in the word mappings206; and/or the identification of a compression algorithm used to compress the word index202.

FIG. 7presents an illustration of an exemplary scenario700featuring an exemplary layout of a word index202incorporating several such variations. In this exemplary scenario700, a word index202is provided that begins with a word index header702providing various information about the word index202, including the word index header size702of the word index header702(including the word mappings table204), which may be added to each index location208(specified as an offset from the end of the word index header702) to identify the direct-access address of respective words108in the word index202. Additionally, the words108stored in the word index202include a word header indicating the word size704(e.g., the string length) of the string representation210of the word108, and, directly following the word size704, the string representation210of the word108. For respective words108identified by the translation mappings218as an index location208, the device may retrieve the string representation210by reading the word size704from the word header at the index location208(optionally first adding the word index header size704to the index location208if such index locations208are specified as an offset from the end of the word index header702), and then, following the word size704, reading the string representation210stored following the word size704and of the length specified by the word size704. In this manner, the layout of the word index202may be selected in various ways by those of ordinary skill in the art while implementing the techniques presented herein.

A third aspect that may vary among embodiments of these techniques relates to computing and storing with the translation resources a set of mapping probabilities, each indicating the likelihood that a particular translation112in the target language114accurately and fluently represents the word sequence106in the source language110. This information may be stored, e.g., in the translation mappings218, and may be used by the language model122to choose translations112of word sequences106provided by the user102. Accordingly, the device104may, for respective translation mappings218, identify a mapping probability of the word sequence106to the translation112, and store the mapping probability of the word sequence106in the target language model122and/or the phrase table118. Also, when generating a translation112of a word sequence106, the device104may select one or more translations112having the highest mapping probability among the candidate translations120for the word sequence106.

As a further variation of this third aspect, it may be advantageous to store and use integers to identify the mapping probabilities, as integers may be compared faster and more efficiently than floating-point values. In particular, the mapping probability integers may be selected to evenly distribute the range of mapping probability floating-point values, thus enhancing the significance of the range of values in the floating-point integer. For example, a one-byte unsigned integer may represent 256 possible floating-point probabilities, and it may be desirable to associate respective integer values with a floating-point probability represented by a significant range of the candidate translations120.

Accordingly, while generating the translation resources, the device104may translate a mapping probability floating point for a translation120into a mapping probability integer, and include the mapping probability integer of the translation120in the language model122. In addition, the device104may include a mapping probability table that identifies the mapping probability floating point value for the respective mapping probability integers (e.g., an integer of “20” may be mapped to a floating-point value of 0.2496). In particular, this selection may cluster the mapping probability floating points into mapping probability clusters, and, for respective clusters, select the mapping probability integer for the word sequences106mapped into the target language model122. Conversely, while using the target language model122, the device104may use the mapping probability table to translating the mapping probability integer for the translation into a mapping probability floating point, which may be used by the target language model122to choose the translation112from the candidate translations120. Those of ordinary skill in the art may devise many techniques for storing, accessing, and applying mapping probabilities while implementing the techniques presented herein.

A fourth aspect that may vary among embodiments of these techniques relates to the provision of one or more caches to facilitate access to the language translation resources.

As a first variation of this fourth aspect, a word index cache may be provided in order to enable faster access to portions of the word index202. For example, the word index202may be conceptually divided into chunks, each comprising a section of the word index202that may be stored in the word index cache. The device104may generate the word index cache by reserving a memory region to store recently accessed chunks of the word index202. Upon accessing a word108at an index location208in the word index202, the device may determine whether the index location208is within a chunk stored in the word index cache. If so, the device104may access the index location208within the chunk in the word index cache; and if not, the device104may read the requested chunk of the word index202including the index location208and store the chunk in the word index cache (optionally replacing a previously stored chunk that has been least recently used).

FIG. 8presents an illustration of an exemplary scenario800featuring this access pattern, wherein a word index202stored on a storage device is divided into chunks802, each spanning a particular address range within the word index202. A word index cache804may be generated in memory that stores a small number of chunks802in a faster region of memory (e.g., a system memory circuit that provides higher throughput than a storage component of the device104). When the device104requests the third word108, the device104may determine that the index location208of the third word108is associated with the second chunk802, and may retrieve the string representation210of the word108from the chunk802stored in the word index cache804. However, when a request is received for the first word108, the device104may determine that the chunk802comprising the index location208of the first word108is not stored in the word index cache804. The device104may therefore retrieve the associated chunk802from the word index202and store it in the word index cache804, in addition to accessing the first word108from the chunk802. In this manner, the word index cache804may provide more rapid access to words108that have recently been used than uncached access techniques that retrieve each word108from the word index202.

As a second variation of this fourth aspect, the other language translation resources (e.g., the phrase table118and/or the target language model120) may also include a cache. Additionally, such caches may be configured, e.g., according to the access patterns of each language translation resource. As a first example, if one resource is frequently accessed in a linear manner, a predictive cache may be provided that is configured to retrieve and store chunks802that follow a recently accessed chunk802, thus buffering the next data in the linear access pattern. Alternatively, if the access pattern of the language translation resource is typically random, the cache may utilize a recently-used cache that stores the most recently accessed chunks802. Additionally, various properties of the cache may be selected in view of the properties of the device104(e.g., the size of the cache and the allocation of chunks802may be selected based on the available memory capacity of the device104). Conversely, the layout of the language translation resources may be selected in view of the presence and types of caching (e.g., a word index cache804may be generated such that words108that are often used together are stored within the same chunk802). These and other caching techniques may be utilized in embodiments of the techniques presented herein.

D5. Language Stores and Language Packs

A fifth aspect that may vary among embodiments of these techniques relates to the use of language stores to provide language translation resources to the device104in order to support translations among various languages. The language store may be accessible to the device104remotely (e.g., over a network) or locally (e.g., stored upon another computer or device of the user102), and may store a set of language packs that provide language translation resources (e.g., word indices202, phrase tables118, and/or target language models120) for various languages. The device104may connect to the language store and request a particular language pack, and, upon receiving such a language pack, may store it in the memory (optionally replacing another language pack that is no longer in use). As one such variation, this technique may be used to provide a modular approach to language translation, wherein a language may be partitioned into language domains for different subsets of the language (e.g., vocabulary and phrases for particular topics). Upon identifying an occasion to translate words108in a particular language domain that is not yet supported (e.g., for a present translation112, or for imminent future translations112), the device104may request the corresponding language pack from the language store, may store the language pack in the storage upon receipt, and may access the language pack to translate the words108associated with the language domain represented thereby.

FIG. 9presents an illustration of an exemplary scenario900featuring a device104having access to a language store902that stores a set of language packs904and featuring a few variations of the techniques provided herein. In this exemplary scenario900, respective language packs904are associated with a language domain906, e.g., specialized words108in the Spanish language for types of food or animals. The device104may comprise a memory component908storing a word index cache802and a phrase table cache910, and also a storage component912storing a set of language packs904for translating respective language domains904of a language. Upon determining an occasion to translate portions of the language that are not contained in any of the language packs904stored in the storage component912, the device104may contact the language store902with a request912to transmit the language pack904(e.g., requesting the language pack904by reference number, or simply presenting to the language store902the words108of the language that are not yet translatable). The language store902may identify the requested language pack904and may provide a response914including the language pack904, which the device104may store in the storage component912. In this manner, the device104and language store902may interoperate to provide an extensible language translation model. Those of ordinary skill in the art may devise many such features that may be implemented in embodiments of the techniques presented herein.

E. Computing Environment

FIG. 10illustrates an example of a system1000comprising a computing device1002configured to implement one or more embodiments provided herein. In one configuration, computing device1002includes at least one processing unit1006and memory1008. Depending on the exact configuration and type of computing device, memory1008may be volatile (such as RAM, for example), non-volatile (such as ROM, flash memory, etc., for example) or some combination of the two. This configuration is illustrated inFIG. 10by dashed line1004.

In other embodiments, device1002may include additional features and/or functionality. For example, device1002may also include additional storage (e.g., removable and/or non-removable) including, but not limited to, magnetic storage, optical storage, and the like. Such additional storage is illustrated inFIG. 10by storage1010. In one embodiment, computer readable instructions to implement one or more embodiments provided herein may be in storage1010. Storage1010may also store other computer readable instructions to implement an operating system, an application program, and the like. Computer readable instructions may be loaded in memory1008for execution by processing unit1006, for example.

Device1002may also include communication connection(s)1016that allows device1002to communicate with other devices. Communication connection(s)1016may include, but is not limited to, a modem, a Network Interface Card (NIC), an integrated network interface, a radio frequency transmitter/receiver, an infrared port, a USB connection, or other interfaces for connecting computing device1002to other computing devices. Communication connection(s)1016may include a wired connection or a wireless connection. Communication connection(s)1016may transmit and/or receive communication media.

Device1002may include input device(s)1014such as keyboard, mouse, pen, voice input device, touch input device, infrared cameras, video input devices, and/or any other input device. Output device(s)1012such as one or more displays, speakers, printers, and/or any other output device may also be included in device1002. Input device(s)1014and output device(s)1012may be connected to device1002via a wired connection, wireless connection, or any combination thereof. In one embodiment, an input device or an output device from another computing device may be used as input device(s)1014or output device(s)1012for computing device1002.

Components of computing device1002may be connected by various interconnects, such as a bus. Such interconnects may include a Peripheral Component Interconnect (PCI), such as PCI Express, a Universal Serial Bus (USB), Firewire (IEEE 1394), an optical bus structure, and the like. In another embodiment, components of computing device1002may be interconnected by a network. For example, memory1008may be comprised of multiple physical memory units located in different physical locations interconnected by a network.

Those skilled in the art will realize that storage devices utilized to store computer readable instructions may be distributed across a network. For example, a computing device1020accessible via network1018may store computer readable instructions to implement one or more embodiments provided herein. Computing device1002may access computing device1020and download a part or all of the computer readable instructions for execution. Alternatively, computing device1002may download pieces of the computer readable instructions, as needed, or some instructions may be executed at computing device1002and some at computing device1020.

F. Usage of Terms