An Advanced Optimistic Approach for String Transformation
Kumar V Pujari, H R Shashidhar · 2014
-------------------------------------------------------------ABSTRACT--------------------------------------------------String transformation can be formalized as the part of coding bio-informatics, information retrieval, and in data mining. However, in part of our paper we focus generating the k most likely output strings corresponding to the input string. This concept proposes a novel and probabilistic approach to string transformation, which is both accurate and efficient. The approach mainly focuses on three methods dynamic programming, modeling and pruning. In the dynamic programming we use the concept of the edit distance which is dynamic programming tool that estimates the score to each transformation so that the probability in the linear model can be estimated well. In the linear model, a modeling method for training the model, and an algorithm for generating the top k candidates, whether there is or is not a predefined dictionary. The linear model is defined as a conditional probability distribution of an output string and a rule set for the transformation conditioned on an input string. The learning method employs maximum likelihood estimation for parameter estimation. The string generation algorithm based on pruning is guaranteed to generate the optimal top k candidates. The proposed method is applied to correction of spelling errors in queries as well as reformulation of queries on dataset. Experimental results on large scale data show that the proposed approach is good and efficient improving upon existing methods in terms of accuracy and efficiency in different settings