Abstract: Approximate string matching is a basic problem in computational biology,text retrieval and signal proces-sing,etc.,and how to improve the matching speed is a key issue up to now．Here,a new lossless q-gram filter was proposed to enhance the performance of finding true matches in a large text database for a given query．Q-gram index is employed as the index structure of large text database for its fast searching speed．To improve new filter’s performance by enhancing its filtration efficiency,some new features based on tail matched q-gram were extracted from text that includes true matches．In new filter,more irrelevant text is eliminated in filtration phase by using a filtration criterion which is enhanced by new extracted features,and the unfiltered text is verified by smith-waterman algorithm to locate the positions of all true matches．The experimental results demonstrate that the proposed filter’s filtration efficiency and performance are both enhanced．As a result,new filter algorithm has strong commonality and is suitable for approxi-mate string matching on condition of various matching error ratio.

Key words: Approximate string matching,Filter algorithm,q-gram filter,q-gram