Building optimal rewriting rules. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T23:00:30Z http://mathoverflow.net/feeds/question/30543 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30543/building-optimal-rewriting-rules Building optimal rewriting rules. danatel 2010-07-04T19:33:21Z 2010-07-05T08:52:48Z <p>Please give me some pointers where I can learn more about the following problem:</p> <p>I have two alphabets A and B. A have a dictionary which contains words in A together with their translation in B (ie. the dictionary is a map from symbols [a1, a2, ..., an] to [b1, b2, ..., bm]). I need an algorithm that will construct an optimal rewriting system which will rewrite a-symbols into b-symbols. The rewriting system is optimal if it preservers maximal number of pairs. (Of course there must be limit to the number of rewriting rules).</p> <p>The motivations is in speech processing. I have a set of rules and a large directory for text-to-phoneme transformation and I want to build <em>rules</em> fro phoneme-to-text transformation.</p> http://mathoverflow.net/questions/30543/building-optimal-rewriting-rules/30596#30596 Answer by supercooldave for Building optimal rewriting rules. supercooldave 2010-07-05T08:20:02Z 2010-07-05T08:52:48Z <p>The <a href="http://en.wikipedia.org/wiki/Trie" rel="nofollow"><strong>trie</strong></a> data structure seems to be precisely the structure you are looking for. It is more efficient in terms of both space and time than providing a table of rewrite rules. There are quite a few references on the wiki page linked above, including volume 3 of Knuth's <em>The Art of Computer Programming</em>. More recent and more efficient variants may exist.</p> <p>Consider the following example trie. Rather than being a collection of key-value pairs, keys are made up of labels on the paths of the tree, and the corresponding values are associated with a leaf (the numbers in the example). For example, in the figure key <em>to</em> maps to value <em>7</em> and key <em>ted</em> maps to value <em>4</em>.</p> <p><img src="http://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg" alt="alt text"></p>