Background
I am designing an application which will convert text from one language to other. For example, input text hello will be converted to specified language text. This is done by having a lookup table for each language. Conversion algorithm has the following steps.
- Looks for exact match. The whole word
hellowill be the pattern. If any matches found, stop processing and return the match. - Else start from left-right and lookup for each character until all the combinations are done. Ex: Iteration1 : pattern =
h, 2nd -he, 3rd -heland so on. Matched token will be kept in a temporary buffer and returned when there are no more matches. This works like maximal munch rule. - If match found, the matched text will be removed from original text and continue processing with the remaining text.
This algorithm will have to iterate over the input text multiple times and leads into quadratic complexity. I am trying to optimize this by arranging the lookup table in a tree structure (very similar to suffix tree). If there are lookup text for h, hel, lo, it will be organized like
root
--h
----hel
--lo
This will help me to avoid unnecessary lookups. After matching h, I need to goto next character only if h node has got children. This reduces the number of iterations drastically.
Questions
- What is the name of this kind of data structure? Is there a ready-made implementation available for C or C++?
- Do you see any possible improvements on the above algorithm or data structure?
Any thoughts...?
