DESIGN AND IMPLEMENTATION OF EFFICIENT SCHEMES FOR VOCABULARY REPRESENTATION

Abstract

An important design issue in the development of spelling checkers and advisors, is the representation scheme of the reference vocabulary. The' essential feature of a vocabulary representation scheme is that, it should not only minimize memory usage, but also permit rapid retrieval of a whole keyword or it's valid abbreviation. In this dissertation, new dynamic data structure has been designed and implemented, which permits rapid search of vocabulary for keyword or it's valid abbreviation. The insertion algorithm, automatically determines disambiguation points, wherever possible, for each keyword. Search operation classifies symbol as one of the following classes: unknown (invalid symbol'), known, or ambiguous ( that is, prefix of more than one valid symbol). The search algorithm is performed in linear time proportional to the length of the input symbol, rather than on the complexity of the dynamic data structure. The external path length and the depth of insertion was found to be less in the case of dynamic data structure as compared to the digital search tries . The total number of nodes formed in the new data structure was also found to be less. An efficient technique for vocabulary compression has been designed and implemented and was found better than the standard compression-utilities like compress and pack of UNIX.