FAST SIGNATURE SCAN
First Claim
1. A method for string signature scanning, comprising:
- processing one or more signatures into one or more formats that include one or more fingerprints and one or more follow-on search data structures for each fixed-size signature or each fixed-size signature substring of a variable-size signature, the one or more fingerprints including a Jth fingerprint for a particular fixed-size signature or signature substring having a first basic unit in a scanning direction at a location within the particular fixed-size signature or signature substring that has a remainder equaling J when divided by a step size for a signature scanning operation such that the number of fingerprints is equal to the step size for signature scanning and the particular fixed-size signature or signature substring is identifiable at any location within any string fields to be scanned, where each fingerprint includes one or more fragments of a particular fixed-size signature or signature substring, the one or more fragments having particular locations anywhere within the particular fixed-size signature or signature substring;
receiving a particular string field comprising a string of data values;
identifying any signatures included in the particular string field including scanning the particular string field for the one or more fingerprints associated with the one or more signatures for each scan step size and searching the particular string field for the one or more follow-on search data structures at the locations where one or more fingerprints are found; and
outputting any identified signatures in the particular string field.
1 Assignment
0 Petitions
Accused Products
Abstract
Systems and methods for scanning signatures in a string field. In one implementation, the invention provides a method for signature scanning. The method includes processing one or more signatures into one or more formats that include one or more fingerprints and one or more follow-on search data structures for each fixed-size signature or signature substring such that the number of fingerprints for each fixed-size signature or signature substring is equal to a step size for a signature scanning operation and the particular fixed-size signature or signature substring is identifiable at any location within any string fields to be scanned, receiving a particular string field, identifying any signatures included in the particular string field including scanning for the fingerprints for each scan step size and searching for the follow-on search data structures at the locations where one or more fingerprints are found, and outputting any identified signatures.
-
Citations
20 Claims
-
1. A method for string signature scanning, comprising:
-
processing one or more signatures into one or more formats that include one or more fingerprints and one or more follow-on search data structures for each fixed-size signature or each fixed-size signature substring of a variable-size signature, the one or more fingerprints including a Jth fingerprint for a particular fixed-size signature or signature substring having a first basic unit in a scanning direction at a location within the particular fixed-size signature or signature substring that has a remainder equaling J when divided by a step size for a signature scanning operation such that the number of fingerprints is equal to the step size for signature scanning and the particular fixed-size signature or signature substring is identifiable at any location within any string fields to be scanned, where each fingerprint includes one or more fragments of a particular fixed-size signature or signature substring, the one or more fragments having particular locations anywhere within the particular fixed-size signature or signature substring; receiving a particular string field comprising a string of data values; identifying any signatures included in the particular string field including scanning the particular string field for the one or more fingerprints associated with the one or more signatures for each scan step size and searching the particular string field for the one or more follow-on search data structures at the locations where one or more fingerprints are found; and outputting any identified signatures in the particular string field. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for string signature scanning, comprising:
-
selecting one or more fixed-size signatures for each of one or more string objects; receiving a particular string field comprising a string of data values; identifying any string objects included the particular string field including scanning the particular string field for the one or more fixed-size signatures associated with the one or more string objects for each step size for a signature scanning operation where the scan step size is equal to the number of the one or more fixed-size signatures for each string object; and outputting any identified string objects in the particular string field. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A string signature scanning system, the system comprising:
-
a machine-readable storage device including a computer program product; and one or more processors operable to execute the computer program product, and perform operations including providing one or more modules including; a signature pre-processing module operable to process one or more signatures into one or more formats that include one or more fingerprints and one or more follow-on search data structures for each fixed-size signature or each fixed-size signature substring of a variable-size signature, the one or more fingerprints including a Jth fingerprint for a particular fixed-size signature or signature substring having a first basic unit in a scanning direction at a location within the particular fixed-size signature or signature substring that has a remainder equaling J when divided by a step size for a signature scanning operation such that the number of fingerprints is equal to the step size for signature scanning and the particular fixed-size signature or signature substring is identifiable at any location within any string fields to be scanned, where each fingerprint includes one or more fragments of a particular fixed-size signature or signature substring, the one or more fragments having particular locations anywhere within the particular fixed-size signature or signature substring; a scan pre-processing engine operable to process an input string field comprising a string of data values into one or more formats for scanning; a fingerprint scan engine operable to identify one or more fingerprints associated with one or more signatures on the input string field, the identifying including scanning the input string field for the one or more fingerprints associated with the one or more signatures for each scan step size; a fixed-size signature search engine operable to identify fixed-size signatures or fixed-size substrings of variable-size signatures for the identified fingerprints; and a variable-size signature search engine operable to identify variable-size signatures including synthesizing identified fixed-size substrings of variable-size signatures into any variable-size signatures. - View Dependent Claims (17, 18, 19, 20)
-
Specification