Patent ID: 6311183
Filing Date: 2001-10-30
Classification: G06F,Y10S

Abstract:
A method for locating all matches of a keyword dictionary in a sample stream using n-grams of length n, comprising the steps of:(a) building tables from the keyword dictionary, including the steps of:(i) constructing a skip table, indexed by all possible digrams, such that for each digram d, the entry indexed by said digram d is the minimum number of bytes in any sample that could separate said digram d and the next feasible termination of a keyword in the keyword dictionary; and(ii) constructing a subset table, addressed by the space of hash values of n-grams, such that each entry addressed by the hash value of the terminal n-gram of at least one keyword in the keyword dictionary contains a search structure, said search structure representing all keywords in the keyword dictionary whose terminal n-grams have hash values addressing the entry holding said search structure; and(b) thereafter, examining the sample stream using successive values of a sample position, serving as a pointer in the sample stream, and reporting any matches terminating at each of said sample position values, including the steps of:(i) initializing said sample position to n;(ii) terminating the process if the sample position is greater than the length of the sample stream;(iii) extracting a sample digram equal to the digram in the sample stream terminating at said sample position;(iv) extracting a sample skip value from said skip table by using said sample digram as an index;(v) for the case of said sample skip value not being zero, skipping said sample position by incrementing said sample position by said sample skip value and returning to step (b)(ii);(vi) for the case of said sample skip value being zero, computing a sample n-gram hash value from the n-gram terminating at said sample position in the sample stream;(vii) thereafter, for the case of the entry in said subset table at the location indexed by said sample n-gram hash value being empty, incrementing said sample position by 1 and returning to step (b)(ii);(viii) for the case of the entry in said subset table at the location indexed by said sample n-gram hash value containing one of said search structures, producing match reports for matches of keywords terminating at said sample position, using said one of said search structures;(ix) thereafter, incrementing said sample position by 1; and(x) returning to step (b)(ii).