Efficient string search
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. A method for filtering received content, the method comprising:
generating, by a hardware processor executing instructions out of a memory, a model that corresponds to a digital content file that is pre-classified under a first classification, the generated model including a number of conditions associated with the first classification that are related to statistical data regarding a set of keywords found in the digital content file;
storing the model in a model repository in the memory;
receiving a string of bytes over a data communication interface that is communicatively coupled to a communication network;
performing a string search on the received string of bytes, wherein the string search generates statistical information indicating whether the received string of bytes includes any keywords from the set of keywords associated with at least the model corresponding to the first classification;
comparing the generated statistical information with the model corresponding to the first classification;
identifying that at least a portion of the received string of bytes include a number of the keywords from the set of keywords associated with the model corresponding to the first classification;
identifying whether the number of conditions associated with the first classification are satisfied based on the number of keywords identified in the received string of bytes that are from the set of keywords associated with the model; and
processing the portion of the received string of bytes based on whether the number of conditions are identified as being satisfied, wherein the portion is allowed to be provided to a user device when the number of keywords does not satisfy the conditions associated with the first classification, and wherein the portion is not allowed to be provided to the user device when the number of keywords does satisfy the conditions associated with the first classification.
2. The method of claim 1 , wherein the portion of the received string of bytes includes text in a non-delimited language.
3. The method of claim 2 , wherein the non-delimited language is selected from the group consisting of Chinese, Japanese, and Thai.
4. The method of claim 1 , wherein each keyword corresponds to one or more N-grams.
5. The method of claim 4 , further comprising identifying a plurality of states associated with each of the one or more N-grams.
6. The method of claim 1 , wherein the number of keywords associated with the first classification are part of one or more other models for classifying the digital content.
7. The method of claim 1 , further comprising generating one or more other models for classifying the digital content.
8. A non-transitory computer-readable storage medium having embodied thereon a program executable by a hardware processor for performing a method for filtering received content, the method comprising:
generating, by the hardware processor, a model that corresponds to a digital content file that is pre-classified under a first classification, the generated model including a number of conditions associated with the first classification that are related to statistical data regarding a set of keywords found in the digital content file;
storing the model in a model repository in memory;
receiving a string of bytes over a data communication interface that is communicatively coupled to a communication network;
performing a string search on the received string of bytes, wherein the string search generates statistical information indicating whether the received string of bytes includes any keywords from the set of keywords associated with the model corresponding to the first classification;
comparing the generated statistical information with the model corresponding to the first classification;
identifying that at least a portion of the received string of bytes include a number of the keywords from the set of keywords associated with the model corresponding to the first classification;
identifying whether the number of conditions associated with the first classification are satisfied based on the number of keywords identified in the received string of bytes that are from the set of keywords associated with the model; and
processing the portion of the received string of bytes based on whether the number of conditions are identified as being satisfied, wherein the portion is allowed to be provided to a user device when the number of keywords does not satisfy the conditions associated with the first classification, and wherein the portion is not allowed to be provided to the user device when the number of keywords does satisfy the conditions associated with the first classification.
9. The non-transitory computer-readable storage medium of claim 8 , wherein the portion of the received string of bytes includes text in a non-delimited language.
10. The non-transitory computer-readable storage medium of claim 9 , wherein the non-delimited language is selected from the group consisting of Chinese, Japanese, and Thai.
11. The non-transitory computer-readable storage medium of claim 8 , wherein each keyword corresponds to one or more N-grams.
12. The non-transitory computer-readable storage medium of claim 11 , wherein the program further comprises instructions executable to identify a plurality of states associated with each of the one or more N-grams.
13. The non-transitory computer-readable storage medium of claim 8 , wherein the number of keywords associated with the first classification are part of one or more other models for classifying the digital content.
14. The non-transitory computer-readable storage medium of claim 8 , wherein the program further comprises instructions executable to generate one or more other models for classifying the digital content.
15. An apparatus for performing a method for filtering received content, the apparatus comprising:
a memory;
a model repository that stores a model that corresponds to a digital content file that is pre-classified under a first classification, the model including a number of conditions associated with the first classification that are related to statistical data regarding a set of keywords found in the digital content file;
a communication interface that receives a string of bytes, the communication interface communicatively coupled to a communication network; and
a hardware processor that executes instructions stored in the memory, wherein execution of the instructions by the processor:
performs a string search on the received string of bytes, wherein the string search generates statistical information indicating whether the received string of bytes includes any keywords from the set of keywords associated with the model corresponding to the first classification;
compares the generated statistical information with the model corresponding to the first classification;
identifies that at least a portion of the received string of bytes include a number of the keywords from the set of keywords associated with the model corresponding to the first classification;
identifies whether the number of conditions associated with the first classification are satisfied based on the number of keywords identified in the received string of bytes as being from the set of keywords associated with the model; and
identifies that the portion of the received string of bytes corresponds to content that is allowed to be provided to a user device based on identifying that the number of keywords does not satisfy the number of conditions associated with the first classification, wherein the portion of the received string of bytes is identified as content that is not allowed to be provided to the user device based on identifying that the number of keywords does satisfy the conditions associated with the first classification.
16. The apparatus of claim 15 , wherein the portion of the received string of bytes includes text in a non-delimited language.
17. The apparatus of claim 16 , wherein the non-delimited language is selected from the group consisting of Chinese, Japanese, and Thai.
18. The apparatus of claim 15 , wherein each keyword corresponds to one or more N-grams.
19. The apparatus of claim 15 , wherein the number of keywords associated with the first classification are part of one or more other models for classifying the digital content.
20. The apparatus of claim 15 , wherein the processor executes further instructions to generate one or more other models for classifying the digital content.