Generation and exploitation of an approximate language model

• US 8,615,389 B1
• Filed: 03/14/2008
• Issued: 12/24/2013
• Est. Priority Date: 03/16/2007
• Status: Active Grant

• Current Assignee: SDL PLC (RWS Holdings Plc)
• Original Assignee: Language Weaver, Inc. (RWS Holdings Plc)
• Inventors: Marcu, Daniel
• Primary Examiner(s): SPOONER, LAMONT M
• Application Number:
  US12/077,005
• Time in Patent Office: 2,111 Days
• Field of Search: 704 1- 10, 707/698, 707/747
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

A system, method, and computer program for generating and exploiting an approximate language model are provided. The method comprises generating a language model according to an approximate hashing technique. The language model comprises a plurality of event sequences in a target language, and each member of the plurality of the event sequences is associated with at least one count. The language model is queried for a member of the plurality of event sequences. A probability associated with the member of the plurality of event sequences is determined based on results of the query.

Claims

1. A method comprising:

executing instructions via a processor of a computing system for;

generating a language model according to an approximate hashing technique, the language model comprising a plurality of event sequences in a target language, each member of the plurality of the event sequences associated with at least one count, the language model comprising a set of data structures organized in a hierarchy with lower levels corresponding to event sequences occurring less frequently being stored using fewer bits, the hierarchy having three or more levels;

querying the language model for a member of the plurality of event sequences; and

determining a probability associated with the member of the plurality of event sequences based on results of the query.

2. The method of claim 1, wherein the approximate hashing technique uses a plurality of hash functions.

3. The method of claim 1, wherein the approximate hashing technique comprises generating a Stratified Spectral Bloom filter comprising a plurality of levels, each of the levels including a Spectral Bloom filter.

4. The method of claim 3, wherein the at least one count is indicated within each of the levels based on a minimal counter.

5. The method of claim 3, wherein an approximation of the at least one count is indicated within each of the levels using one bit.

6. The method of claim 1, wherein the language model includes a number of Stratified Spectral Bloom filters, the number based on a length of the event sequences.

7. The method of claim 1, wherein the event sequence comprises history information and event information.

8. The method of claim 1, wherein determining the probability is based on a first value associated with event information and a second value associated with history information.

9. The method of claim 1, wherein the approximate hashing technique comprises a filter selected from a group consisting of:

Bloom filter replacements, dynamic Bloom filters, weighted Bloom filters, d-left counting Bloom filters, parallel Bloom filters, hierarchical Bloom filter arrays, stable Bloom filters, dynamic count filters, Bloomier filters, compact approximators, generalized Bloom filters, attenuated Bloom filters, perfect hash keys, and compressed Bloom filters.

10. A system comprising:

a processor configured to generate a language model based on a training corpus using an approximate hashing technique, the language model comprising a set of data structures organized in a hierarchy with lower levels corresponding to event sequences occurring less frequently being stored using fewer bits, the hierarchy having three or more levels; and

a memory configured to store the language model.

11. The system of claim 10, wherein the language model comprises a plurality of Stratified Spectral Bloom filters.

12. The system of claim 11, wherein the approximate hashing technique includes a plurality of hash functions.

13. The system of claim 10, wherein the memory comprises a random access memory.

14. The system of claim 10, wherein the size of the language model is less than six hundred fifty megabytes for a portion of a training corpus comprising ten million sentences.

15. The system of claim 10, wherein the processor is further configured to query the language model based on an initial sequence.

16. The system of claim 10, wherein the approximate hashing technique comprises generating a Stratified Spectral Bloom filter comprising a plurality of levels, each of the levels including a Spectral Bloom filter.

17. The system of claim 16, wherein a count corresponding to an event sequence within the language model is indicated within each of the levels based on a minimal counter.

18. The system of claim 16, wherein the count is indicated within each of the levels using one bit.

19. The system of claim 18, wherein the size of the language model is less than one hundred megabytes for a portion of a training corpus comprising ten million sentences.

20. A non-transitory computer readable storage medium having embodied thereon a program, the program being executable by a processor for performing a method for determining a translation, the method comprising:

generating a language model according to an approximate hashing technique, the language model comprising a plurality of event sequences in a target language, each member of the plurality of the event sequences associated with at least one count, the language model comprising a set of data structures organized in a hierarchy with lower levels corresponding to event sequences occurring less frequently being stored using fewer bits, the hierarchy having three or more levels;

querying the language model for a member of the plurality of event sequences; and

determining a probability associated with the member of the plurality of event sequences based on results of the query.