0
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Somehow I suspect that StackOverflow maybe a better place to post this question. Unless you are looking for a provably optimal system... $\endgroup$
    – Willie Wong
    Commented Jul 4, 2010 at 19:39
  • $\begingroup$ Could you clarify what you mean by optimal? And precisely what your rewrite system should do? Undecidability abounds with rewrite systems, such as the Post systems and others. $\endgroup$
    – Joel David Hamkins
    Commented Jul 4, 2010 at 19:45
  • $\begingroup$ @Joel David Hamkins: My rewrite system should be a set of rewrite rules that applied recursively on an a-word replace all a-symbols with b-symbols. Optimality: my dictionary has, say 10000 word pairs (a_i,b_i). The system S1 is better than S2 if S1 creates more matches (ie. S1(a_i) = b_i) than S2 on the particular dictionary. $\endgroup$
    – danatel
    Commented Jul 4, 2010 at 20:22
  • $\begingroup$ But I could design a rewrite system that consults the dictionary and does it perfectly, right? So it seems that you are likely asking actually about the best possible system with respect to some resource limitation? And does the system have to recognize the domain language? That is, your criterion doesn't seem to punish it for providing translations of words not in the first language. And must it be determinisitic (that is, always give the same translation for a given word)? $\endgroup$
    – Joel David Hamkins
    Commented Jul 4, 2010 at 21:24
  • 1
    $\begingroup$ it sounds like the OP's question can be reformulated this way: given a limit K on the number of rules, maximize the number of pairs a_i, b_i mapped correctly by the rule system, where the rules can apply recursive, so if 11 <-> aa and 1123 <-> aabc, then the rule S(11)=aa captures the first map and the first part of the second map. Obviously K < min(n,m). $\endgroup$
    – Suresh Venkat
    Commented Jul 5, 2010 at 8:06

1 Answer 1

Reset to default
2
$\begingroup$

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.

alt text

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .