System and method for statistics-based pattern searching of compressed data and encrypted data

Abstract

A method for searching compressed, encrypted data includes receiving uncompressed data and identifying patterns thereof. Each pattern includes a predetermined number of bytes. Each pattern is hashed into a hash value, producing a set of hash values that is stored in a hash table. Each record of the hash table includes a hash value from the set of hash values and an associated position value. A Boolean filter is generated based on the hash table, each bit of the Boolean filter associated with a different hash value. A search string hash value is calculated based on a received search request. A location in the Boolean filter, having an address equal to the search string hash value, is inspected to determine whether a position stored at the location is true or false. If the position is true, at least a portion of the compressed data is flagged as relevant.

1 . A method, comprising:
 receiving, at a processor, a search request including a search string;   computing a search string hash value based on the search string;   when a position stored at a location within a Boolean filter, the location having an address equal to the search string hash value, is true:
 flagging, via the processor, that at least a portion of a data file is relevant to the search request. 
   
     
     
         2 . The method of  claim 1 , wherein computing the search string hash value includes computing overlapping hashes based on a minimum match size value. 
     
     
         3 . The method of  claim 1 , wherein each bit from a plurality of bits of the Boolean filter is associated with a different hash value from a plurality of hash values, and each hash value from the plurality of hash values is a hash of a different pattern from a plurality of patterns of the data file. 
     
     
         4 . A method, comprising:
 receiving, at a processor, a search request including a search string;   generating, via the processor, a search string hash value based on the search string;   detecting, via the processor and based on the search string hash value, a hash table position of a hash table;   when a position of a bit of an Nth output data file, the bit having a value corresponding to the hash table position, is true:
 flagging the Nth output data file as relevant to the search request, and 
 transmitting a signal representing the Nth output data file to a compute device of a requestor associated with the search request; 
   determining whether at least one additional output data file exists; and   when at least one additional output data file exists, inspecting the at least one additional output data file to determine whether the at least one additional output data file is relevant to the search request.   
     
     
         5 . The method of  claim 4 , further comprising, in response to determining that the value of the bit is true, reading the Nth output data file to confirm that the Nth output data file is relevant to the search request. 
     
     
         6 . The method of  claim 4 , further comprising:
 reading the flagged Nth output data file into memory; and   performing a search for the search string in the output data file.   
     
     
         7 . The method of  claim 4 , further comprising:
 reading the flagged Nth output data file into memory;   detecting a match between the search string and the output data file based on a search for the search string in the output data file; and   in response to detecting the match, outputting the file to the compute device of the requestor associated with the search request.   
     
     
         8 . The method of  claim 4 , further comprising generating the hash table based on input data. 
     
     
         9 . The method of  claim 4 , further comprising generating the hash table by:
 identifying, via the processor, a plurality of patterns of input data;   hashing, via the processor, each pattern from the plurality of patterns into a hash value, to produce a plurality of hash values; and   storing the plurality of hash values in the hash table.   
     
     
         10 . The method of  claim 4 , further comprising generating the hash table by:
 identifying, via the processor, a plurality of patterns of input data, each pattern from the plurality of patterns including a predetermined number of bits;   hashing, via the processor, each pattern from the plurality of patterns into a hash value, to produce a plurality of hash values; and   storing the plurality of hash values in the hash table, each record of a plurality of records of the hash table including a hash value from the plurality of hash values and an associated position value, to produce a plurality of output data files including the Nth output data file.   
     
     
         11 . A system, comprising:
 a processor; and   a processor-readable memory storing instructions that, when executed by the processor, cause the processor to:
 receive a search request including a search string; 
 compute a search string hash value based on the search string; 
 when a position stored at a location within a Boolean filter, the location having an address equal to the search string hash value, is true:
 flag that at least a portion of a data file is relevant to the search request. 
 
   
     
     
         12 . The system of  claim 11 , wherein the instructions to cause the processor to compute the search string hash value include instructions to compute overlapping hashes based on a minimum match size value. 
     
     
         13 . The system of  claim 11 , wherein each bit from a plurality of bits of the Boolean filter is associated with a different hash value from a plurality of hash values, and each hash value from the plurality of hash values is a hash of a different pattern from a plurality of patterns of the data file. 
     
     
         14 . A method, comprising:
 receiving, at a processor, an input data file;   identifying, via the processor, a plurality of patterns of the input data file, each pattern from the plurality of patterns including a predetermined number of bits;   hashing, via the processor, each pattern from the plurality of patterns into a hash value, to produce a plurality of hash values;   storing the plurality of hash values in a hash table, each record of a plurality of records of the hash table including a hash value from the plurality of hash values and an associated position value, to produce a output data file associated with the input data file; and   generating, via the processor, a Boolean filter based on the hash table, each bit from a plurality of bits of the Boolean filter associated with a different hash value from the plurality of hash values.   
     
     
         15 . The method of  claim 14 , wherein the predetermined number of bits is 32 bits. 
     
     
         16 . The method of  claim 14 , wherein each hash value from the plurality hash values is a two-byte hash value from a plurality of two-byte hash values. 
     
     
         17 . The method of  claim 14 , wherein the plurality of bits of the Boolean filter includes 65,536 bits. 
     
     
         18 . The method of  claim 14 , further comprising receiving, at the processor and from a compute device of a user, a signal representing the predetermined number of bits prior to identifying the plurality of patterns. 
     
     
         19 . The method of  claim 14 , wherein the predetermined number of bits is based on a minimum match size value. 
     
     
         20 . The method of  claim 14 , wherein the identifying the plurality of patterns of the input data file includes identifying overlapping patterns of the input data file. 
     
     
         21 . A system, comprising:
 a processor; and   a processor-readable memory storing instructions that, when executed by the processor, cause the processor to:
 receive an input data file; 
 identify a plurality of patterns of the input data file, each pattern from the plurality of patterns including a predetermined number of bits; 
 hash each pattern from the plurality of patterns into a hash value, to produce a plurality of hash values; 
 store the plurality of hash values in a hash table, each record of a plurality of records of the hash table including a hash value from the plurality of hash values and an associated position value, to produce an output data file associated with the input data file; and 
 generate a Boolean filter based on the hash table, each bit from a plurality of bits of the Boolean filter associated with a different hash value from the plurality of hash values. 
   
     
     
         22 . The system of  claim 21 , wherein the identifying the plurality of patterns of the input data file includes identifying overlapping patterns of the input data file. 
     
     
         23 . The system of  claim 21 , wherein each hash value from the plurality of hash values is a two-byte hash value from a plurality of two-byte hash values. 
     
     
         24 . The system of  claim 21 , wherein the predetermined number of bits is 32 bits. 
     
     
         25 . The system of  claim 21 , the memory further storing instructions that, when executed by the processor, cause the processor to receive, from a compute device of a user, a signal representing the predetermined number of bits prior to identifying the plurality of patterns.