System, method and apparatus for prediction using minimal affix patterns

• US 20050120020A1
• Filed: 02/27/2004
• Published: 06/02/2005
• Est. Priority Date: 09/30/2003
• Status: Active Grant

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Dictaphone Corporation (Microsoft Corporation)
• Inventors: Deplonty, Thomas J. III, Carus, Alwin B.
• Granted Patent: US 8,024,176 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]

Abstract

One embodiment generally pertains to a method of prediction. The method includes generating a set of affixes from a selected input sequence and comparing the set of affixes with a predictive set of affixes. The method also includes selecting an affix from the predictive set of affixes. The invention uses various input data sets and allows the ability to perfectly render the original data set and the minimal size of the predictive set of affixes.

Claims

1-42. -42. (canceled)

43. A method of prediction, the method comprising:

generating a set of affixes from a selected input sequence;

comparing the set of affixes with a predicted set of affixes; and

selecting an affix from the predicted set of affixes.

44. The method according to claim 43, further comprising:

providing a pattern associated with the selected predicted affix.

45. The method according to claim 43, further comprising:

associating an action with each entry in the predicted set of affixes.

46. The method according to claim 45, further comprising:

providing an associated action of the affix in response to a match between an entry in the set of affixes and an entry in the predicted set of affixes.

47. The method according to claim 43, wherein the action is providing an electronic mail address to an email client.

48. The method according to claim 43, further comprising:

processing a master data set to generate the predicted set of affixes.

49. The method according to claim 48, wherein said processing of the master data set further comprises:

removing entries in the master data set based on an excluded data set.

50. The method according to claim 49, further comprising:

generating affix patterns for entries in the excluded master data set; and

selecting affix patterns based on a shortest length and a highest frequency criteria to create the predicted set of affixes.

51. The method according to claim 50, further comprising:

adding entries from an add-in data set to the predicted set of affixes.

52. The method according to claim 50, wherein said generation of the affix patterns further comprises:

determining a length of longest affix pattern; and

determining a lowest frequency affix-pattern combination.

53. The method according to claim 52, further comprising:

pre-pending a peripheral symbol for each sequence in the excluded master data set; and

post-pending the peripheral symbol for each sequence in the excluded master data set.

54. The method according to claim 53, further comprising:

generating triplets based on the excluded master data set, each triplet comprising of an affix, an associated pattern, and a frequency of occurrence of the affix and pattern.

55. The method according to claim 54, further comprising:

determining a cumulative frequency of each affix-pattern combination.

56. The method according to claim 55, further comprising:

sorting generated triplets based on length and frequency of affix; and

determining a highest frequency for a selected affix-pattern that becomes entered into the affix prediction data set.

57. A method for generating a data set, the method comprising:

receiving a corpus comprising of a plurality of sequences;

generating a set of triplets based on the corpus, each triplet having an affix, an associated pattern, and a frequency of occurrence for the affix and associated pattern; and

selecting a subset of triplets as the data set, wherein a selection criteria is based on length and frequency of occurrence.

58. The method according to claim 57, wherein the generation of the set of triplets is further comprises:

setting a first parameter of a longest acceptable affix; and

setting a second parameter of a lowest frequency for combination of a selected affix and the associated pattern.

59. The method according to claim 58, further comprising:

marking a beginning of each sequence in the corpus; and

marking an end of each sequence in the corpus.

60. The method according to claim 58, further comprising:

constructing a plurality of triplets based on said corpus; and

accumulating frequency of occurrence for each combination.

61. The method according to claim 58, further comprising:

eliminating a selected triplet based on associated affix of the selected affix exceeding the first parameter.

62. The method according to claim 60, further comprising:

eliminating a selected triplet based the associated frequency of occurrence does not exceed the second parameter.

63. The method according to claim 60, further comprising:

sorting said plurality of triplets based on length of the associated affix and frequency of occurrence;

determining a set of selected affixes based on highest frequency of occurrence and shortest length; and

providing said set of selected affixes as the data set.

64. The method according to claim 60, further comprising:

eliminating a selected triplet based on the associated affix of the selected triplet being predicted by a previously determined triplet, wherein the associated affix of the previously determined triplet is shorter in length than the associated affix of the selected triplet.

65. A system for predicting a patter using affixes, said system comprising:

an affix prediction module;

an affix prediction data set; and

an affix generation module, wherein said affix prediction module is configured to predict a sequence based on matching affixes generated from an input sequence with entries in the affix prediction data set generated by the affix generation module.

66. The system according to claim 65, wherein the affix prediction module is further configured to compare the affixes generated from the input sequence with the entries in the affix prediction data set and to select a matching affix from the affix prediction data set in response to an affix from the affixes generated from the input sequence matches an entry in the entries in the affix prediction data set.

67. The system according to claim 66, wherein the affix prediction module is further configured to provide an action associated with the matching affix.

68. The system according to claim 65, wherein the affix generation module is further configured to receive a corpus a corpus comprising of a plurality of sequences and generate a set of triplets based on the corpus, each triplet having an affix, an associated pattern, and a frequency of occurrence for the affix and associated pattern.

69. The system according to claim 68, wherein the affix generation module is further configured to receive a set of excluded triplets and remove triplets from the set of triplets matching entries in the set of excluded triplets.

70. The system according to claim 68, wherein the affix generation module is further configured to remove a selected triplet from the set of affixes based on the associated affix of the selected triplet being predicted by a second triplet, wherein the associated affix of the second triplet is shorter in length than the associated affix of the selected triplet.

71. The system according to claim 68, wherein the affix generation module is configured to determine a cumulative frequency for the affix and associated pattern for each triplet in the set of triplets based on the corpus.

72. The system according to claim 71, wherein the affix generation module is configured to sort the set of triplets based on length of the affix and the frequency of occurrence for the affix and associated pattern.

73. The system according to claim 72, wherein the affix generation module is further configured to remove a selected triplet from the set of affixes based on the associated affix of the selected triplet being predicted by a second triplet, wherein the associated affix of the second triplet is shorter in length than the associated affix of the selected triplet to generate the affix prediction data set.

74. The system according to claim 72, wherein the affix generation module is further configured to remove a selected triplet from the set of affixes based on the associated affix of the selected triplet being predicted by a second triplet, wherein the associated affix of the second triplet is shorter in length than the associated affix of the selected triplet.

75. The system according to claim 74, wherein the affix generation module is further configured to add the entries of a add-in data set to generate the affix prediction data set.

76. An apparatus for generating a data set, the apparatus comprising:

means for receiving a corpus comprising of a plurality of sequences;

means for generating a set of triplets based on the corpus, each triplet having an affix, an associated pattern, and a frequency of occurrence for the affix and associated pattern; and

means for selecting a subset of triplets as the data set, wherein a selection criteria is based on length and frequency of occurrence.

77. The apparatus according to claim 76, wherein the generation of the set of triplets is further comprises:

means for setting a first parameter of a longest acceptable affix; and

means for setting a second parameter of a lowest frequency for combination of a selected affix and the associated pattern.

78. The apparatus according to claim 77, further comprising:

means for marking a beginning of each sequence in the corpus; and

means for marking an end of each sequence in the corpus.

79. The apparatus according to claim 77, further comprising:

means for constructing a plurality of triplets based on said corpus; and

means for accumulating frequency of occurrence for each combination.

80. The apparatus according to claim 77, further comprising:

means for removing a selected triplet based on associated affix of the selected affix exceeding the first parameter.

81. The apparatus according to claim 79, further comprising:

means for removing a selected triplet based the associated frequency of occurrence does not exceed the second parameter.

82. The apparatus according to claim 79, further comprising:

means for sorting said plurality of triplets based on length of the associated affix and frequency of occurrence;

means for determining a set of selected affixes based on highest frequency of occurrence and shortest length; and

means for providing said set of selected affixes as the data set.

83. The apparatus according to claim 79, further comprising:

means for removing a selected triplet based on the associated affix of the selected triplet being predicted by a previously determined triplet, wherein the associated affix of the previously determined triplet is shorter in length than the associated affix of the selected triplet.