Assaf Solomovitch Tsahi Talmor

For a complete description, see appendix B – Phoneme class documentaion

Data structure

We had to choose an adequate data structure for our application. Its use is to store the Hebrew wordlist. We had several major considerations when choosing the data structure:

1. 
   We are doing at runtime multiple searches for words (items) in the database – hence it’s find() functionality must be computationally efficient – O(1)
   
2. 
   our Hebrew wordlist contains about 500,000 Hebrew words – storing it in memory must be as sparse as possible.
   

The trie data structure is built similarly to a k-ary tree, where k is the number of letters in the alphabet. Each node has k children, and node has a boolean variable to indicate if there is a word which ends at this node (see example in figure).

Finding a word in a trie takes a complexity of O(L), L being the length of the word we are looking for – which renders it practically O(1).
Trie Data Structure: exhibiting valid words: ace, aces

Hebrew translation heuristics

Translation from phonetix Hebrew in Latin characters into “real” Hebrew in Hebrew characters was also a major part in our Phoneme system design and implementation issue.

Among the various translation heuristics we note here two major ones, which are both feasible solutions to this problem.

• 
  One possible solution is to come up with writing rules, meaning the user will have to learn these new rules in order that the system will understand him fully. For example, if we wish to distinguish between TAF & TET letters, we enforce the user to write one “t” as a sign of TAF, and two t’s, “tt”, to signal TET.
  

You can find an example to such heurustics in Appendix A.

• 
  One of our major design backbones was easy-to-use system, so our solution was chosen a bit differently. We did not force the user to learn any rules, but rather we have tried to make the translation as intuitive as possible. First we made a few reasonable assumptions:
  

h	ה
ch	ח
t	ט,ת
tz	צ
sh	ש
c	ק
k	כ
v	ו,ב רפה
a	א,ע

These are reasonable assumptions, which can be eliminated in the future versions.

Nevertheless, a few basic ambiguities still pertain. For example, one canot intuitively know if translation of “DAVAR” is דבר or דוור. Another ambiguity is translation of ‘t’ to “tet” or “taf”, and translation of ‘a’ to “alef” or “ayin”.

In order to solve these ambiguities, we resorted to a second heuristics: searching the possible permutations of the translation in a Hebrew complete wordlist. For example, we will translate “TAMID” to both תמיד and טמיד, than we will search both translations in the worslist, and determine that the second option is not a valid word, and automatically choose the first translation as the correct one.

A more complex scenario is when both are valid words, as in the translation of DAVAR. In this case we have no alternative but to request the user to properly choose what he meant. We present the user with a GUI, which lists for him all translation options, and prompt him to choose the appropriate one.

In future versions we will implement a “learning” mechanism, which registers the user’s choices and tries to guess the correct translation. We will need a scoring mechanism to help us achieve that, aggregating several properties into it (such as frequency of word in the Hebrew language and so on).