Method and Apparatus for Generating and Managing a Language Model Data Structure

• US 20060184341A1
• Filed: 02/22/2006
• Published: 08/17/2006
• Est. Priority Date: 06/30/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Zheng, Chien, Lee-Feng, Gao, Jianfeng, Di, Shuo, Lee, Kai-Fu
• Granted Patent: US 7,216,066 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30
• CPC Class Codes: G10L 15/285 Memory allocation or algorithm optimisation to reduce hardware requirements

Abstract

A method is presented comprising assigning each of a plurality of segments comprising a received corpus to a node in a data structure denoting dependencies between nodes, and calculating a transitional probability between each of the nodes in the data structure.

Claims

1-29. -29. (canceled)

30. One or more computer readable media comprising computer executable instructions that, when executed, direct a computer to:

assign each of a plurality of segments comprising a received corpus to a node in a data structure denoting dependencies between nodes;

calculate a transitional probability between each of the nodes in the data structure; and

manage storage of the data structure across a system memory of a computer system and an extended memory of the computer system such that at least one said node is stored in the system memory and another said node is stored in the extended memory simultaneously.

31. One or more computer readable media according to claim 30, wherein the computer executable instructions further direct the computer to:

calculate a frequency of occurrence for each elemental item of the segment; and

removing nodes of the data structure associated with items which do not meet a minimum threshold for the frequency of occurrence.

32. One or more computer readable media according to claim 31, wherein the frequency of the item is calculated by counting item occurrences throughout the subset and/or corpus.

33. One or more computer readable media according to claim 31, wherein the minimum threshold is three (3).

34. One or more computer readable media according to claim 30, wherein managing storage of the data structure comprises:

identifying least recently used nodes of the data structure; and

storing the least recently used nodes of the data structure in the extended memory of the computer system when the data structure is too large to store completely within the system memory.

35. One or more computer readable media according to claim 34, wherein the extended memory of the computer system comprises one or more files on an accessible mass storage device.

36. One or more computer readable media according to claim 35, wherein the data structure represents a language model, spread across one or more elements of a computing system memory subsystem.

37. One or more computer readable media according to claim 30, wherein calculating a transition probability includes calculating a Markov transitional probability between nodes.

38. A computer system comprising:

a controller; and

a memory subsystem having a system memory, an extended memory and is configured to maintain instructions that are executable by the controller to;

assign each of a plurality of segments comprising a received corpus to a node in a data structure denoting dependencies between nodes;

calculate a transitional probability between each of the nodes in the data structure; and

manage storage of the data structure across a system memory of a computer system and an extended memory of the computer system such that at least one said node is stored in the system memory and another said node is stored in the extended memory simultaneously.

39. A computer system according to claim 38, wherein the instructions further direct the controller to:

calculate a frequency of occurrence for each elemental item of the segment; and

removing nodes of the data structure associated with items which do not meet a minimum threshold for the frequency of occurrence.

40. A computer system according to claim 39, wherein the frequency of the item is calculated by counting item occurrences throughout the subset and/or corpus.

41. A computer system according to claim 39, wherein the minimum threshold is three (3).

42. A computer system according to claim 38, wherein managing storage of the data structure comprises:

identifying least recently used nodes of the data structure; and

storing the least recently used nodes of the data structure in the extended memory of the computer system when the data structure is too large to store completely within the system memory.

43. A computer system according to claim 42, wherein the extended memory of the computer system comprises one or more files on an accessible mass storage device.

44. A computer system according to claim 43, wherein the data structure represents a language model, spread across one or more elements of a computing system memory subsystem.

45. A computer system according to claim 38, wherein calculation of a transition probability includes calculating a Markov transitional probability between nodes.

46. A system comprising:

means for assigning each of a plurality of segments comprising a received corpus to a node in a data structure denoting dependencies between nodes;

means for calculating a transitional probability between each of the nodes in the data structure; and

means for managing storage of the data structure across a system memory of a computer system and an extended memory of the computer system such that at least one said node is stored in the system memory and another said node is stored in the extended memory simultaneously.

47. A system according to claim 46, wherein the managing means manages storage of the data structure by:

identifying least recently used nodes of the data structure; and

storing the least recently used nodes of the data structure in the extended memory of the computer system when the data structure is too large to store completely within the system memory.

48. A system according to claim 46, wherein the extended memory of the computer system comprises one or more files on an accessible mass storage device.

49. A system according to claim 46, wherein the calculating means calculates a transition probability by calculating a Markov transitional probability between nodes.