System, method and apparatus for prediction using minimal affix patterns

• US 8,024,176 B2
• Filed: 02/27/2004
• Issued: 09/20/2011
• Est. Priority Date: 09/30/2003
• Status: Expired due to Fees

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Dictaphone Corporation (Microsoft Corporation)
• Inventors: Deplonty, Thomas J. III, Carus, Alwin B.
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): Spooner; Lamont
• Application Number:
  US10/787,889
• Publication Number:
  US 20050120020A1
• Time in Patent Office: 2,762 Days
• Field of Search: 704/1, 704/9, 704/10, 707/711, 707706-708, 715/256, 715/259
• US Class Current: 704/9
• 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. A method of prediction, the method comprising acts, performed via at least one processor, of:

determining from a selected input sequence a set of potential affixes, wherein the set of potential affixes comprises one or more potential affixes each being contained within the selected input sequence;

generating a predicted set of affixes by processing a master data set, wherein the processing of the master data set comprises removing entries in the master data set based on an excluded data set;

comparing the set of potential affixes with the predicted set of affixes comprising a set of predicted affixes;

determining that a group of one or more potential affixes from the set of potential affixes is in the predicted set of affixes; and

selecting a matching affix from the group, wherein the matching affix is the potential affix within the group that has the greatest number of characters.

2. The method according to claim 1, further comprising an act of:

providing a pattern associated with the matching affix.

3. The method according to claim 1, further comprising an act of:

associating an action with the matching affix.

4. The method according to claim 3, further comprising an act of:

performing the action associated with the matching affix in response to selecting the matching affix from the group.

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

6. The method according to claim 1, further comprising acts of:

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

7. The method according to claim 6, further comprising an act of:

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

8. The method according to claim 6, wherein said act of generating affixes comprises acts of:

determining a length of longest affix; and

determining a lowest frequency affix-pattern combination.

9. The method according to claim 8, wherein said act of generating affixes further comprises acts of:

pre-pending a peripheral symbol to each affix in the excluded master data set; and

post-pending the peripheral symbol to each affix in the excluded master data set.

10. The method according to claim 9, wherein generating a predicted set of affixes further comprises:

generating triplets, wherein each triplet comprising of comprises an affix, an associated pattern, and a frequency of occurrence of an affix-pattern combination, wherein the affix and associated pattern determine the affix-pattern combination.

11. The method according to claim 10, further comprising an act of:

determining a cumulative frequency of each affix-pattern combination.

12. The method according to claim 11, further comprising acts of:

sorting the generated triplets based on length and frequency of the affix in each triplet; and

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

13. A method for generating a data set, the method comprising acts, performed via at least one processor, of:

receiving a corpus comprising 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 an affix-pattern combination, wherein the affix and associated pattern in the triplet determine the affix-pattern combination of the triplet, and wherein the frequency of occurrence for an affix-pattern combination of each triplet is accumulated while processing each of the plurality of sequences of the corpus; and

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

14. The method according to claim 13, wherein the act of generating the set of triplets comprises acts of:

setting a first parameter establishing a longest acceptable length for an affix in the subset of triplets; and

setting a second parameter establishing a lowest acceptable frequency of occurrence for an affix-pattern pair in the subset of triplets.

15. The method according to claim 14, further comprising acts of:

marking a beginning of each sequence in the corpus; and

marking an end of each sequence in the corpus.

16. The method according to claim 14, further comprising an act of:

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

17. The method according to claim 14, further comprising an act of:

eliminating a selected triplet based on the associated frequency of occurrence of the affix-pattern combination not exceeding the second parameter.

18. The method according to claim 14, further comprising acts of:

sorting said set of triplets based on the length of the affix in each triplet in the set of triplets and frequency of occurrence of the affix-pattern combination in each triplet in the set of triplets;

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.

19. The method according to claim 14, further comprising an act of:

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

20. The method of claim 13, wherein the associated pattern of each triplet is associated with an action.

21. The method of claim 20, wherein the action is loading an email client.

22. A system for predicting a pattern associated with an input sequence, said system comprising:

an affix generation module for;

receiving a corpus comprising a plurality of sequences;

generating an affix prediction data set, the affix prediction data set comprising a set of triplets based on the corpus, each triplet having an affix, an associated pattern, and a frequency of occurrence for an affix-pattern combination, wherein the affix and associated pattern determine the affix-pattern combination, and wherein the frequency of occurrence for each affix-pattern combination is accumulated while processing each of the plurality of sequences of the corpus; and

an affix prediction module for;

determining from the input sequence a set of affixes, wherein the set of affixes comprises one or more affixes each contained within the input sequence; and

predicting a pattern by

comparing the set of affixes with entries in the affix prediction data set

determining that a group of one or more affixes from the set of affixes is in the prediction data set;

selecting a matching affix from the group of one or more affixes, wherein the matching affix is the potential affix within the group that has the greatest number of characters; and

selecting a pattern associated with the matching affix as the predicted pattern.

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

24. The system according to claim 22, wherein the affix generation module is further configured to:

receive a set of affixes to be excluded; and

remove triplets from the set of triplets with affixes matching entries in the set of affixes to be excluded.

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

26. The system according to claim 22, wherein the affix generation module is further configured to sort the set of triplets based on the length of each of the affixes and the frequency of occurrence of each of the affix-pattern combinations.

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

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

29. The system according to claim 28, wherein the affix generation module is further configured to add the entries of an add-in data set to the set of triplets to generate the affix prediction data set.

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

at least one processor programmed to;

receive a corpus, the corpus comprising a plurality of sequences;

generate a set of triplets based on the corpus, each triplet having an affix, an associated pattern, and a frequency of occurrence for an affix-pattern combination, wherein the affix and associated pattern determine the affix-pattern combination and wherein the frequency of occurrence for an affix-pattern combination of each triplet is accumulated while processing each of the plurality of sequences of the corpus; and

select a subset of triplets as the data set using a selection criteria based on the length of each affix in the set of triplets and the frequency of occurrence of each affix-pattern combination in the set of triplets.

31. The apparatus according to claim 30, wherein the at least one processor is programmed to generate the set of triplets by:

setting a first parameter establishing a longest acceptable length for an affix in the subset of triplets; and

setting a second parameter establishing a lowest acceptable frequency of occurrence for an affix-pattern pair in the subset of triplets.

32. The apparatus according to claim 31, wherein the at least one processor is further programmed to:

mark a beginning of each sequence in the corpus; and

mark an end of each sequence in the corpus.

33. The apparatus according to claim 31, wherein the at least one processor is further programmed to:

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

34. The apparatus according to claim 31, wherein the at least one processor is further programmed to:

remove a selected triplet based on the associated frequency of occurrence of the affix-pattern combination not exceeding the second parameter.

35. The apparatus according to claim 31, wherein the at least one processor is further programmed to:

sort the set of triplets based on the length of the affix in each triplet in the set of triplets and frequency of occurrence of the affix-pattern combination in each triplet in the set of triplets;

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

provide said set of selected affixes as the data set.

36. The apparatus according to claim 31, wherein the at least one processor is further programmed to:

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