Hybrid model to improve time complexity of words search in POS Tagging

摘要

POS Tagging is the tagging of each word with the most appropriate category listed in the lexicon which indicates its syntactic role in the sentence. POS Tagging enables tracking of user reviews and can even be used for Human-Robot-Interaction in future. In this paper, we are presenting a model which deals with the limitations of previously existing POS Tagging algorithm, namely, Memory Based Learning Algorithm and Multi-Domain Web Based Algorithm. In Multi-Domain Web Based Algorithm, the unknown word is searched over the web for its possible tags which creates a runtime overhead (increases execution time), the tag with highest probability of occurrence is assigned to the word. The process repeats itself every time the algorithm runs, even for the words previously been searched. Whereas, Memory Based Learning Algorithm is a lazy learning algorithm. In this algorithm, the word is first searched in the lexicon, if the word is found, its lexical representation is retrieved, but, if it is not found, its lexical representation is computed with the help of similarity metrics. The computed tag may not be accurate. Therefore, Adding results of Multi-domain Web Based POS tagging to the lexicon, will improve efficiency of the lexicon as well as the overall time complexity of the algorithm whenever the same word appears next. Thus, we can calculate the time complexity of the model and devise a generalized formula for efficiency and performance of the model.