Efficient string search
AssigneeSonicWALL, Inc.
InventorsThomas E. Raffill, Shunhui Zhu, Roman Yanovsky, Boris Yanovsky, John Gmuender
Life of this patent
Estimating the term…
Abstract
Some embodiments of an efficient string search have been presented. In one embodiment, a string of bytes representing content written in a non-delimited language is received, wherein the content has been classified into a predetermined category. In a single pass through the string of bytes, a set of N-grams is searched for simultaneously. Statistical information on occurrences of the N-grams, if any, in the string of bytes is collected. In some embodiments, a model is generated based on the statistical information, where the model is usable by a content filter to classify content.
Claims20
A method for searching a string of bytes, the method comprising:
- receiving a set of a plurality of N-grams in memory, wherein each N-gram corresponds to a pre-selected keyword for identifying content of a type in a non-delimited language;
- receiving a string of bytes representing non-segmented text written in the non-delimited language;
- and
- executing instructions stored in memory, wherein execution of the instructions by a processor:
- simultaneously searches for the plurality of N-grams in a single pass through the string of bytes using a finite state machine having a plurality of states, wherein the plurality of states are coupled to each other via one or more paths and the plurality of states are based on the plurality of N-grams;
- and
- classifies the string of bytes as the type based on the search results for the plurality of N-grams meeting a predetermined number of conditions.
A non-transitory computer-readable storage medium having embodied thereon instructions executable by a processor to perform a method for searching a string of bytes, the method comprising:
- receiving a set of a plurality of N-grams in memory, wherein each N-gram corresponds to a pre-selected keyword for identifying content of a type in a non-delimited language;
- receiving a string of bytes representing non-segmented text written in a non-delimited language;
- simultaneously searching for a plurality of N-grams in a single pass through the string of bytes using a finite state machine having the plurality of states, wherein the plurality of states are coupled to each other via one or more paths and the plurality of states are based on the plurality of N-grams;
- and
- classifying the string of bytes as the type based on the search results for the plurality of N-grams meeting a predetermined number of conditions.
A system comprising:
- a device for receiving:
- a set of a plurality of N-grams in memory, wherein each N-gram corresponds to a pre-selected keyword for identifying content of a type in a non-delimited language, and
- a string of bytes representing non-segmented text written in a non-delimited language;
- and
- a finite state machine, coupled to the device, for:
- simultaneously searching for the plurality of N-grams in a single pass through the string of bytes having the plurality of states, wherein the plurality of states are coupled to each other via one or more paths and the plurality of states are based on the plurality of N-grams, and
- classifying the string of bytes as the type based on the search results for the plurality of N-grams meeting a predetermined number of conditions.
Dependencies are inferred from the claim text.