Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby

Applications

There are many applications for search trees. The principal characteristic of such applications is that a database of keyed information needs to be frequently accessed and the access pattern is either unknown or known to be random. For example, dictionaries are often implemented using search trees. A dictionary is essentially a container that contains ordered key/value pairs. The keys are words is a source language and, depending on the application, the values may be the definitions of the words or the translation of the word in a target language.

This section presents a simple application of search trees. Suppose we are required to translate the words in an input file one-by-one from some source language to another target language. In this example, the translation is done one word at a time. That is, no natural language syntactic or semantic processing is done.

In order to implement the translator we assume that there exists a text file, which contains pairs of words. The first element of the pair is a word in the source language and the second element is a word in the target language. To translate a text, we first read the words and the associated translations and build a search tree. The translation is created one word at a time by looking up each word in the text.

Program gives an implementation of the translator. The translate method uses a search tree to hold the pairs of words. In this case, an AVL tree is used. However, this implementation works with all the search tree types described in this chapter (e.g., BinarySearchTree, AVLTree, MWayTree, and BTree).

program22592
Program: Application of search trees--word translation.

The translate method read each line from the dictonary stream (line 5). Each line is asssumed to contain a pair of words, i.e., a word and its translation (lines 6-7). The Association class defined in Section is used to contain the key/value pairs. A new instance is created for each key/value pair which is then inserted into the search tree (line 8). The process of building the search tree terminates when all the lines in the dictonary stream have been processed.

During the translation phase, the translate method reads the lines from the input stream and splits each line into a sequence of words (lines 10-11). Each word is looked up in the search tree (line 12). If no key matches the given word, the word is printed followed by a question mark (lines 13-14). Otherwise, the value associated with the matching key is printed (line 16).