An Approximate String Matching System Using Local Filtering

With the development of computer technology,Internet has become an indispensable part of people's life.Search engines,information search and social networks play a more and more important role in people's life.String matching is widely used in these fields.Therefore,the research on the string matching algorithm has some theoretical significance and practical value.In recent years,along with the wide application of approximate string matching technique,more and more scholars participate in the studies of approximate string matching problem.The approximate string matching problem,which is different from the exact string matching,is permitted the presence of certain errors in matching.The matching result set is larger.The time complexity and the space complexity of the search algorithm is higher.At present,the main solution is to use the partial same between the strings.However,the method is very inefficient when the difference between the query string and the data string is large.The thesis proposes a new algorithm which uses the difference between the query string and data string to achieve approximate string matching.A concept called local distance is proposed.It can quantify the difference between a query string and a data string.The local distance of the query string is the lower bound of the edit distance between the query string and the data string.The thesis designed a new index which stores all the query strings' local distance to support local filtering.The thesis also designed an index which has less space usage by using the difference of the local distance of the strings.An algorithm which uses bit parallel is proposed to search more quickly.The algorithm is improved to reply uncertain threshold and uncertain length of the query strings.The experimental results show that this algorithm's filtering effect is stronger,the time of search is less and the index size is smaller in comparison with other algorithms.