Efficient string search

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.

1 . (canceled) 
     
     
         2 . A method for string searches using finite state machines (FSMs), the method comprising:
 receiving a feature set inclusive of a number of N-grams, each N-gram corresponding to an undesirable keyword included in a set of characters in a non-delimited format;   assigning a state to each N-gram and to each prefix of the number of N-grams;   identifying a set of steps for implementing the FSM, the set of steps including state information identifying each of the assigned states;   comparing one or more characters of the set of characters with the state information to identify that the set of characters includes the undesirable keyword;   counting a number of undesirable keywords identified based on the comparison;   classifying the set of characters as undesirable when the count of the number of undesirable keywords at least meets a threshold level; and   preventing at least a portion of the received set of characters from being sent to a destination.   
     
     
         3 . The method of  claim 2 , wherein the set of characters include graphic data. 
     
     
         4 . The method of  claim 2 , wherein the set of characters include one or more symbolic representations. 
     
     
         5 . The method of  claim 4 , wherein the symbolic representations correspond to at least one of a Chinese, Japanese, or Thai language. 
     
     
         6 . The method of  claim 2 , further comprising:
 collecting statistical information regarding the number of N-grams; and   generating a model based on the statistical information.   
     
     
         7 . The method of  claim 6 , further comprising storing the model in a model repository. 
     
     
         8 . The method of  claim 2 , wherein the set of characters include one or more symbols. 
     
     
         9 . The method of  claim 2 , further comprising parsing the set of characters to identify at least one of a keyword or a token. 
     
     
         10 . The method of  claim 2 , further comprising receiving a policy that specifies how many undesirable keywords meet the threshold level, wherein classifying the set of characters as undesirable is based on the policy. 
     
     
         11 . An apparatus for string searches using finite state machines (FSMs), the apparatus comprising:
 a model repository that receives a feature set inclusive of a number of N-grams, each N-gram corresponding to an undesirable keyword included in a set of characters in a non-delimited format; and   a content filtering client that executes a finite state machine to:
 assign a state to each N-gram and to each prefix of the number of N-grams; 
 identify a set of steps for implementing the FSM, the set of steps including state information identifying each of the assigned states; 
 compare one or more characters of the set of characters with the state information to identify that the set of characters includes the undesirable keyword; 
 count via a counting module a number of undesirable keywords identified based on the comparison; and 
 classify via a classifying engine the set of characters as undesirable when the count of the number of undesirable keywords at least meets a threshold level; and 
 prevent at least a portion of the received set of characters from being sent to a destination. 
   
     
     
         12 . The apparatus of  claim 11 , wherein the set of characters include graphic data. 
     
     
         13 . The apparatus of  claim 11 , wherein the set of characters include one or more symbolic representations. 
     
     
         14 . The apparatus of  claim 13 , wherein the symbolic representations correspond to at least one of a Chinese, Japanese, or Thai language. 
     
     
         15 . The apparatus of  claim 11 , further comprising a model generator executable to:
 collect statistical information regarding the number of N-grams; and   generate a model based on the statistical information.   
     
     
         16 . The apparatus of  claim 15 , wherein the model repository further stores the generated model. 
     
     
         17 . The apparatus of  claim 11 , wherein the set of characters include one or more symbols. 
     
     
         18 . The apparatus of  claim 11 , wherein the content filter further parses the set of characters to identify at least one of a keyword or a token. 
     
     
         19 . The apparatus of  claim 11 , wherein the content filter further receives a policy that specifies how many undesirable keywords meet the threshold level, wherein the content filter classifies the set of characters as undesirable is based on the policy. 
     
     
         20 . A non-transitory computer-readable storage medium having embodied thereon a program executable by a processor for implementing a method for string searches using finite state machines (FSMs), the method comprising:
 receiving a feature set inclusive of a number of N-grams, each N-gram corresponding to an undesirable keyword included in a set of characters in a non-delimited format;   assigning a state to each N-gram and to each prefix of the number of N-grams;   identifying a set of steps for implementing the FSM, the set of steps including state information identifying each of the assigned states;   comparing one or more characters of the set of characters with the state information to identify that the set of characters includes the undesirable keyword;   counting a number of undesirable keywords identified based on the comparison;   classifying the set of characters as undesirable when the count of the number of undesirable keywords at least meets a threshold level; and   preventing at least a portion of the received set of characters from being sent to a destination.