Efficient string search
View Patent ↗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 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.
2. The method of claim 1 , further comprising generating the finite state machine, wherein generating the finite state machine comprises:
defining the plurality of states based on the plurality of N-grams;
constructing the finite state machine having the plurality of states, wherein the plurality of states are coupled to each other via one or more paths; and
mapping each of the plurality of states to the set of N-grams in an output table.
3. The method of claim 1 , further comprising collecting statistical information on occurrences of the plurality of N-grams in the string of bytes.
4. The method of claim 3 , wherein collecting the statistical information comprises counting a number of occurrences of each of the plurality of N-grams in the string of bytes.
5. The method of claim 3 , wherein simultaneously searching for the plurality of N-grams in the string of bytes comprises:
inputting the string of bytes into the finite state machine; and
tracing operations of the finite state machine over the string of bytes.
6. The method of claim 5 , wherein collecting the statistical information comprises counting a number of occurrences of each of the N-grams using the output table while tracing the operations of the finite state machine.
7. The method of claim 1 , wherein the non-delimited language is Chinese.
8. 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.
9. The non-transitory computer-readable storage medium of claim 8 , further comprising instructions executable by the processor to generate the finite state machine, wherein generating the finite state machine comprises:
defining the plurality of states based on the plurality of N-grams;
constructing the finite state machine having the plurality of states, wherein the plurality of states are coupled to each other via one or more paths; and
mapping each of the plurality of states to the set of N-grams in an output table.
10. The non-transitory computer-readable storage medium of claim 8 , further comprising collecting statistical information on occurrences of the plurality of N-grams in the string of bytes.
11. The non-transitory computer-readable storage medium of claim 10 , wherein collecting the statistical information comprises counting a number of occurrences of each of the plurality of N-grams in the string of bytes.
12. The non-transitory computer-readable storage medium of claim 10 , wherein simultaneously searching for the plurality of N-grams in the string of bytes further comprises:
inputting the string of bytes into the finite state machine; and
tracing operations of the finite state machine over the string of bytes.
13. The non-transitory computer-readable storage medium of claim 12 , wherein collecting the statistical information comprises counting a number of occurrences of each of the N-grams using the output table while tracing the operations of the finite state machine.
14. The non-transitory computer-readable storage medium of claim 8 , wherein the non-delimited language is Chinese.
15. 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.
16. The system of claim 15 , further comprising a counting module, coupled to the finite state machine, to collect statistical information on occurrences of the plurality of N-grams in the string of bytes.
17. The system of claim 16 , wherein the counting module is further executable by a processor to count a number of occurrences of each of the plurality of N-grams in the string of bytes.
18. The system of claim 16 , wherein the finite state machine simultaneously searches for the plurality of N-grams in the string of byte by inputting the string of bytes into the finite state machine and tracing operations of the finite state machine over the string of bytes.
19. The system of claim 18 , wherein the counting module is further configured to count a number of occurrences of each of the N-grams using the output table while tracing the operations of the finite state machine.
20. The system of claim 15 , wherein the non-delimited language is Chinese.