An Effective Algorithm for Checking Subsumption Relation on String Data Containing Wildcard Characters
Dohan Kim, Heejin Park, Eunok Paek · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2005
String data containing wildcard characters may represent certain patterns in texts. A subsumption relation between two patterns can be defined by a subset relation between sets of strings that match those patterns. Thus, the subsumption relation check is important to determine whether each pattern represents a set of strings without any overlap with another pattern. In this paper, we propose an effective algorithm that can determine subsumption relation between strings with wildcard characters. First, we consider a simple extension of the suffix tree algorithm so that it nay include wildcard characters and then we propose another method that checks the subsumption relation by dividing a suffix tree structure at each location of string data.