US 6,311,183 B1Granted

Method for finding large numbers of keywords in continuous text streams

AssigneeThe United States of America as represented by the Director, National Security Agency

InventorJonathan Drew Cohen

Life of this patent

Estimating the term…

Abstract

A method of full-text scanning for matches in a large dictionary of keywords is described, suitable for SDI (selective dissemination of information). The method is applicable to large dictionaries (hundreds of thousands of entries) and to arbitrary byte sequences for both patterns and sample streams. The approach employs Boyer-Moore-Horspool skipping, extended to pattern collections and digrams, followed by an n-gram hash test, which also identifies a subset of feasible keywords for conventional pattern matching at each location of a putative match.

Claims3

Dependent claims

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).

14 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

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).

14 more elements