关键词: 通配符, 字符串匹配, q-gram索引

Abstract: This paper focuses on the problem of strings matching with wildcards “*” and “?” in the query, where “*” matches any sequence and “?” matches any character. Since gram based index structure has advantages in both space and searching time, it proposes an algorithm to solve the problem of strings matching with wildcards based on gram index structure. The query string with wildcards is divided into several query segments without any wildcards. So the algorithm successfully changes this complex problem to a simple exact substring matching problem. The algo-rithm takes advantage of length filter, position filter, and count filter to speed up the query process

Key words: wildcard, matching strings, q-gram index