关键词: 子串查询, 模糊查询, gram索引, 编辑距离

Abstract: The algorithms of approximate string query based on edit distance have usually a given threshold k, and report those strings whose edit distances with the query are not bigger than k. However, when talking about approximate substring query, many answers got in this way have overlap, thus meaningless. So this paper proposes a concept of local optimal matching only computing those answers which are both not higher than k and local optimal, thus eliminating the overlapped answers and cutting the time cost. It also presents a definition of approximate substring query supporting local optimal matching along with a query algorithm based on gram index. Moreover, it analyzes the generality of the matching process, and studies the methods of filtering and limiting the boundary based on local optimal matching. Finally, it proposes an algorithm of local optimal approximate substring query with filtering, so that the efficiency of matching is promoted.

Key words: substring query, fuzzy query, gram index, edit distance