Building optimal rewriting rules. - MathOverflow

Building optimal rewriting rules.

2010-07-04T19:33:21Z

Please give me some pointers where I can learn more about the following problem:

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).

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 rules fro phoneme-to-text transformation.

Answer by supercooldave for Building optimal rewriting rules.

2010-07-05T08:20:02Z

The trie 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 The Art of Computer Programming. More recent and more efficient variants may exist.

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 to maps to value 7 and key ted maps to value 4.