Patent ID: 9715525
Date: 2017-07-25
CPC Classifications: G06F

Claim:
1. A method of determining whether a search string is contained in stored data which stores a plurality of data strings each in a structured form, the structured form including the storage of subsets of each data string of predetermined length stored in as the edges of a tree structure along with prefix data including all possible prefixes for each such edge which have length less than said predetermined length, the method including the steps of: dividing the search string into a plurality of sub-searches, the number of sub-searches being equal to the predetermined length of the subsets and each sub-search containing a prefix, a main and a postfix, by the steps of: setting the prefix of the first sub-search to be null, setting the prefix of the second sub-search to be the first item in the search string, and setting the prefix of the ith sub-search to be the first (i−1) items in the search string for all remaining sub-searches; setting the main of each sub-search to be those items in the search string immediately following the prefix which make up complete subsets of the search string, the subsets being of said predetermined length; setting the postfix of each sub-search to be those items at the end of the search string which are not included in the prefix or main or, if there are no such items, to be null, comparing each of the sub-searches to the stored data to determine if a match exists by, for each sub-search, until all sub-searches have been considered: determining if the main of the sub-search is contained in the subsets of any of the stored data strings, if it is not then moving to the next sub-search; if it is, determining if the prefix of the sub-search is contained in the prefix data stored for that subset, if it is not then moving to the next sub-search; if it is, determining if the postfix of the sub-search is contained in the stored data strings by: