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 computer-implemented method comprising:
receiving, by a processor, a string of bytes representing non-segmented text written in a non-delimited language, wherein the non-segmented text has been classified into a predetermined category;
simultaneously searching, by the processor, for a plurality of N-grams in a single pass through the string of bytes;
collecting, by the processor, statistical information on occurrences of the plurality of N-grams in the string of bytes;
generating, by the processor, a model based on the statistical information, the model usable by a content filter to classify contents;
defining, by the processor, a plurality of states based on the plurality of N-grams;
constructing, by the processor, 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
mapping, by the processor, each of the plurality of states to a set of zero or more of the plurality of N-grams in an output table.
2. The method of claim 1 , wherein collecting the statistical information comprises:
counting, by the processor, a number of occurrences of each of the plurality of N-grams in the string of bytes.
3. The method of claim 1 , wherein simultaneously searching the plurality of N-grams in the string of bytes further comprises:
inputting, by the processor, the string of bytes into the finite state machine; and
tracing, by the processor, operations of the finite state machine over the string of bytes.
4. The method of claim 3 , wherein collecting the statistical information comprises:
counting, by the processor, a number of occurrences of each of the N-grams using the output table while tracing the operations of the finite state machine.
5. The method of claim 1 , wherein the non-delimited language is Chinese.
6. A computer-implemented method comprising:
receiving, by a processor, a string of bytes representing non-segmented text written in a non-delimited language;
simultaneously searching, by the processor, for a plurality of N-grams in a single pass through the string of bytes;
collecting, by the processor, statistical information on occurrences of the plurality of N-grams in the string of bytes;
classifying, by the processor, the non-segmented text based on the statistical information;
blocking, by the processor, the non-segmented text if the non-segmented text is classified to be in a prohibited category;
causing, by the processor, a network access application to render the non-segmented text if the non-segmented text is content to be in an allowable category;
defining, by the processor, a plurality of states based on the plurality of N-grams;
constructing, by the processor, 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
mapping, by the processor, each of the plurality of states to a set of zero or more of the plurality of N-grams in an output table.
7. The method of claim 6 , wherein classifying the non-segmented text based on the statistical information comprises:
comparing, by the processor, the statistical information against a model generated from a previously classified document.
8. The method of claim 6 , wherein simultaneously searching for the plurality of N-grams in the string of bytes further comprises:
inputting, by the processor, the string of bytes into the finite state machine; and
tracing, by the processor, operations of the finite state machine over the string of bytes.
9. The method of claim 8 , wherein collecting the statistical information comprises:
counting, by the processor, a number of occurrences of each of the N-grams using the output table while tracing the operations of the finite state machine.
10. The method of claim 6 , wherein the non-delimited language is Japanese.
11. A non-transitory machine-accessible medium that provides instructions that, if executed by a processor, will cause the processor to perform operations comprising:
receiving a string of bytes representing non-segmented text written in a non-delimited language, wherein the non-segmented text has been classified into a predetermined category;
simultaneously searching for a plurality of N-grams in a single pass through the string of bytes;
collecting statistical information on occurrences of the plurality of N-grams in the string of bytes;
generating a model based on the statistical information, the model usable by a content filter to classify contents,
defining a plurality of states based on the plurality of N-grams;
constructing 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
mapping each of the plurality of states to a set of zero or more of the plurality of N-grams in an output table.
12. The non-transitory machine-accessible medium of claim 11 , wherein collecting the statistical information comprises:
counting a number of occurrences of each of the plurality of N-grams in the string of bytes.
13. The non-transitory machine-accessible medium of claim 11 , 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.
14. The non-transitory machine-accessible medium of claim 13 , 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.
15. A non-transitory machine-accessible medium that provides instructions that, if executed by a processor, will cause the processor to perform operations comprising:
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 incoming string of bytes;
collecting statistical information on occurrences of the plurality of N-grams in the string of bytes;
classifying the non-segmented text based on the statistical information;
blocking the non-segmented text if the non-segmented text is classified to be in a prohibited category;
causing a network access application to render the non-segmented text if the non-segmented text is classified to be in an allowable category;
defining a plurality of states based on the plurality of N-grams
constructing 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
mapping each of the plurality of states to a set of zero or more of the plurality of N-grams in an output table.
16. The non-transitory machine-accessible medium of claim 15 , wherein classifying the non-segmented text based on the statistical information comprises:
comparing the statistical information against a model generated from a previously classified document.
17. The non-transitory machine-accessible medium of claim 15 , 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.
18. The non-transitory machine-accessible medium of claim 17 , 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.
19. An apparatus comprising:
a finite state machine having a plurality of states logically coupled to each other via one or more paths, the plurality of states being mapped to a plurality of N-grams in an output table, wherein the finite state machine is operable to simultaneously search for the plurality of N-grams through a string of bytes in a single pass, wherein the string of bytes represents non-segmented text written in a non-delimited language;
a counting module coupled to the finite state machine to count a number of occurrences of each of the plurality of N-grams in the string of bytes while tracing operations of the finite state machine over the string of bytes; and
a model generator coupled to the counting module to generate a model based on the number of occurrences of each of the plurality of N-grams, the model usable by a content filter to classify contents.
20. The apparatus of claim 19 , further comprising:
a repository coupled to the model generator to store the model.
21. An apparatus comprising:
a finite state machine having a plurality of states logically coupled to each other via one or more paths, the plurality of states being mapped to a plurality of N-grams in an output table, wherein the finite state machine is operable to simultaneously search for the plurality of N-grams through a string of bytes in a single pass, wherein the string of bytes represents non-segmented text written in a non-delimited language;
a counting module coupled to the finite state machine to count a number of occurrences of each of the plurality of N-grams in the string of bytes while tracing operations of the finite state machine over the string of bytes; and
a classifying engine coupled to the counting module to classify the non-segmented text based on the number of occurrences of each of the plurality of N-grams, to block the string of bytes and to generate an error message if the non-segmented text is classified to be in a prohibited category, and to cause a display device to render the non-segmented text if the non-segmented text is classified to be in an allowable category.
22. The apparatus of claim 21 , wherein the classifying engine is operable to compare the number of occurrences of each of the plurality of N-grams against corresponding information in a first model to determine if the non-segmented text is likely to be within the prohibited category.
23. The apparatus of claim 21 , wherein the classifying engine is operable to compare the number of occurrences of each of the plurality of N-grams against corresponding information in a second model to determine if the non-segmented text is likely to be within the allowable category.
24. A system comprising the apparatus of claim 21 , further comprising:
a client machine coupled to the apparatus, wherein the client machine comprises the display device.
25. The system of claim 24 , further comprising:
a repository coupled to the apparatus, to store one or more models for classifying contents.