Nada

Laboration 3 - Word tree

The theme of this lab is binary search trees and the first exercise involves building a search tree from a file of Swedish words and spitting out doublets. The next exercise is searching an English text for words in the Swedish search tree. Any seemingly Swedish words are to be printed, but only the first occurence of each Swedish word. In order to recognize words already found, you should save them in another search tree.

A search tree with a dictionary

In the file bintree.py you are to write a class Bintree: with three method calls, as indicated in the following excerpt from the main program lab3.py.
   from bintree import Bintree  # All else in the file is hidden
   svenska=Bintree()
   svenska.put("gurka")
   - - -
   if svenska.exists("gurka"):
      - - -
   svenska.write()              # Prints all words in alphabetic order
When the tree object receives the call put("gurka"), the object sends its root pointer and the word gurka to a recursive function putta, responsible for creating a new tree node in the right position. The other method calls work in analogy.
class Bintree:
    root=None

    def put(self,newvalue):
        self.root=putta(self.root,newvalue)

    def exists(self,value):
        return finns(self.root,value)

    def write(self):
        skriv(self.root)
        print
Here the class definition ends, but the code continues with definitions of putta, finns and skriv . If you try to add a doublet, putta just prints it on the screen.

Of course there must also be a class Node: in the bintree file, containing a value and two pointers.

In lab3.py you start by reading the file /info/grudat06/word3.txt into your tree, for example like this.

   svenskfil=open("word3.txt")        # Opens the file for reading
   for rad in svenskfil.readlines():
       ord=rad[0:3]                   # One three letter word per line
       svenska.put(ord)               # into the search tree
If you are successful, the doublets that are spit out will convey an important message.

Two binary search trees with dictionaries

Now that you have a search tree with all Swedish three letter words, you can easily and rapidly check whether a given word is in there. You are now to read the file /info/grudat06/engelska.txt word by word and put these words into another search tree. You dont want to print any doublets, so check before you put with if engelska.exists(...). If the word was already there, you do nothing, but if it is new you should also check if it happens to exist as a Swedish word. If that is the case, it gets printed on the screen.

When you have done this correctly, the printed words will convey another secret message. Having received this message, you may try to get a teacher signature below.

Extra tasks for higher marks (choose one)

Söt tös: Investigate which three letter words become other words read backwards. Every such word couple shall be printed once only. No symmetric words, please!

Alpin pinal: Investigate which five letter words become other words when the first two letters are moved to the end. You may use the file /info/grudat06/word5.txt.





Genialt programmerat av ..................................... anser.............................. den .................