Template generation using directed acyclic word graphs

1. A method comprising:

transforming, via a computing device, a plurality of titles into a trie data structure representing the plurality of titles, the transforming comprising separating words in the plurality of titles into a sequence of nodes of the trie data structure representing each word sequence of each title of the plurality of titles, each node of the trie data structure comprising one word;

transforming, by the computing device, the trie data structure into a directed acyclic word graph (DAWG) data structure representing each word sequence of each title of the plurality of titles, the DAWG data structure comprising one or more fixed nodes and one or more variable nodes, each fixed node comprising one fixed word, and each variable node comprising a plurality of alternative words representing multiple alternative words for the variable node, the DAWG data structure comprising a canonical form of each title of the plurality of titles; and

analyzing, by the computing device, a new title based on the DAWG data structure and extracting information from the new title based on the analysis.

2. The method of claim 1 , further comprising:

generating, by the computing device, one or more unique templates based on the DAWG data structure.

3. The method of claim 2 , further comprising:

identifying, by the computing device, at least one of the one or more unique templates matching the new title; and

associating, by the computing device, the at least one identified template with the new title.

4. The method of claim 2 , generating one or more unique templates based on the DAWG data structure further comprising:

generating, by the computing device, a unique template using two fixed words corresponding to two fixed nodes of the one or more fixed nodes and a number of wildcard parameters.

5. The method of claim 4 , the generated unique template comprising one wildcard parameter as the number of wildcard parameters, the generated unique template representing a trigram.

6. The method of claim 4 , the generated unique template comprising two wildcard parameter as the number of wildcard parameters, the generated unique template representing a 4-gram.

7. The method of claim 2 , wherein the plurality of titles belong to a category set of a plurality of category sets and the one or more unique templates are generated for the category set.

8. The method of claim 1 , further comprising:

removing, by the computing device, any duplicates from an initial set of titles to generate the plurality of titles.

9. The method of claim 1 , further comprising:

normalizing, by the computing device, the trie data structure by at least removing duplicates in the trie data structure prior to transforming the trie data structure into the DAWG data structure.

10. The method of claim 1 , further comprising:

determining, by the computing device, the canonical form of a title of the plurality of titles by traversing the DAWG data structure through a path of node having labels matching the title's contents.

11. A non-transitory computer-readable storage medium tangibly encoded with computer-executable instructions that when executed by a processor associated with a computing device perform a method comprising:

transforming a plurality of titles into a trie data structure representing the plurality of titles, the transforming comprising separating words in the plurality of titles into nodes of the trie data structure representing each word sequence of each title of the plurality of titles, each node of the trie data structure comprising one word;

transforming the trie data structure into a directed acyclic word graph (DAWG) data structure representing each word sequence of each title of the plurality of titles, the DAWG data structure comprising one or more fixed nodes and one or more variable nodes, each fixed node comprising one fixed word, and each variable node comprising a plurality of alternative words representing multiple alternative words for the variable node, the DAWG data structure comprising a canonical form of each title of the plurality of titles; and

analyzing a new title based on the DAWG data structure and extracting information from the new title based on the analysis.

12. The non-transitory computer-readable storage medium of claim 11 , the method further comprising:

generating one or more unique templates based on the DAWG data structure.

13. The non-transitory computer-readable storage medium of claim 12 , further comprising:

identifying at least one of the one or more unique templates matching the new title; and

associating the at least one identified template with the new title.

14. The non-transitory computer-readable storage medium of claim 12 , generating one or more unique templates based on the DAWG data structure further comprising:

generating a unique template using two fixed words corresponding to two fixed nodes of the one or more fixed nodes and a number of wildcard parameters.

15. The non-transitory computer-readable storage medium of claim 14 , the generated unique template comprising one wildcard parameter as the number of wildcard parameters, the generated unique template representing a trigram.

16. The non-transitory computer-readable storage medium of claim 14 , the generated unique template comprising two wildcard parameter as the number of wildcard parameters, the generated unique template representing a 4-gram.

17. The non-transitory computer-readable storage medium of claim 12 , wherein the plurality of titles belong to a category set of a plurality of category sets and the one or more unique templates are generated for the category set.

18. The non-transitory computer-readable storage medium of claim 11 , the method further comprising:

normalizing, by the computing device, the trie data structure by at least removing duplicates in the trie data structure prior to transforming the trie data structure into the DAWG data structure.

19. The non-transitory computer-readable storage medium of claim 11 , the method further comprising:

determining, by the computing device, the canonical form of a title of the plurality of titles by traversing the DAWG data structure through a path of node having labels matching the title's contents.

20. A computing device comprising:

a processor;

a non-transitory storage medium for tangibly storing thereon program logic for execution by the processor, the program logic comprising:

executable logic for transforming a plurality of titles into a trie data structure representing the plurality of titles, the transforming comprising separating words in the plurality of titles into nodes of the trie data structure representing each word sequence of each title of the plurality of titles, each node of the trie data structure comprising one word;

executable logic for transforming the trie data structure into a directed acyclic word graph (DAWG) data structure representing each word sequence of each title of the plurality of titles, the DAWG data structure comprising one or more fixed nodes and one or more variable nodes, each fixed node comprising one fixed word, and each variable node comprising a plurality of alternative words representing multiple alternative words for the variable node, the DAWG data structure comprising a canonical form of each title of the plurality of titles; and

analyzing logic for analyzing a new title based on the DAWG data structure and extracting information from the new title based on the analysis.