Template generation using directed acyclic word graphs

A non-transitory computer-readable storage medium tangibly encoded with computer-executable instructions, that when executed by a processor of computing device, performs a method, the method comprising:

• receiving a first plurality of titles from a first plurality of title feeds;
• sorting the first plurality of titles into a plurality of category sets;
• and
• for each category set of the plurality of category sets:
• transforming the respective titles belonging to the category set into a trie data structure by separating words in the respective titles into nodes of the trie data structure, each node of the trie data structure comprising one word;
• normalizing the trie data structure by at least removing duplicates in the trie data structure;
• and
• transforming the normalized trie data structure into a directed acyclic word graph (DAWG) data structure, the DAWG data structure comprising a plurality of fixed nodes and a plurality of variable nodes, each fixed node of the plurality of fixed nodes comprising one fixed word, and each variable node of the plurality of variable nodes comprising a plurality of alternative words representing multiple alternative words for the variable node.

A computing device, comprising:

• a processor;
• and
• a non-transitory computer-readable storage medium for tangibly storing thereon program logic for execution by the processor, the program logic comprising:
• executable logic for receiving a first plurality of titles from a first plurality of title feeds;
• executable logic for sorting the first plurality of titles into a plurality of category sets;
• and
• for each category set of the plurality of category sets:
• executable logic for transforming the respective titles belonging to the category set into a trie data structure by separating words in the respective titles into nodes of the trie data structure, 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, the DAWG data structure comprising a plurality of fixed nodes and a plurality of variable nodes, each fixed node of the plurality of fixed nodes comprising one fixed word, and each variable node of the plurality of variable nodes comprising a plurality of alternative words representing multiple alternative words for the variable node;
• and
• executable logic for generating one or more unique templates based on the DAWG data structure.