System and methods for streaming string similarity and pattern matching

Abstract

Embodiments provide systems, methods, and computer storage media for determining string similarity and pattern matching in strings that arrive in a stream. A stream representing string of characters is received and used to compute mapping values that are compared to a mapping value of a query string to identify a match between strings in the stream of characters and the query string. The stream of characters is searched in a single sequential pass to detect a match or the longest matching substring with a query string. An identified match or absence of a match is provided.

What is claimed is: 
     
         1 . One or more computer storage media storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform operations comprising:
 receiving an asymmetric stream of data representing a plurality of characters of a text received in an arbitrary order;   determining a longest common substring between a substring of the text and a query string by at least:   storing the query string to a local memory;   applying a mapping function to the substring of the text and a postfix of the query string to compute a substring value and a query string value, the substring comprises one or more characters represented in the asymmetric stream, and a length of the substring corresponds to a postfix of a query string, wherein the mapping function is a rolling hash;   determining the substring of the text matches the query string by comparing the substring value to a query string value associated with the query string; and   as a result of determining that the substring of the text does not matches the query string, increasing a size of the postfix of the query string; and   based on determining the substring value matches the postfix query value, providing an indication of the substring.   
     
     
         2 . The one or more computer storage media of  claim 1 , wherein the operations limit processing of the one or more characters of the text to a single sequential pass of the one or more characters of the text. 
     
     
         3 . The one or more computer storage media of  claim 1 , wherein the query string value is calculated by applying the mapping function to the postfix of the query string. 
     
     
         4 . The one or more computer storage media of  claim 1 , wherein the indication of the substring comprises a location of the substring in the text. 
     
     
         5 . The one or more computer storage media of  claim 1 , the operations further comprising:
 based on determining that the substring of the text does not match the query string, generating an updated substring by removing a first character of the substring and including in the substring a next character from the characters represented in the stream; and   updating the substring value by applying the mapping function to the updated substring.   
     
     
         6 . The one or more computer storage media of  claim 1 , wherein determining whether the substring of the text matches the query string comprises finding a longest sequence of characters that occur in the substring of text and to the postfix of the query string. 
     
     
         7 . A computerized method comprising:
 receiving a stream representing one or more characters of a text;   identifying a substring match between the text and a postfix of a query string by, for each substring of characters in the text having a length equal to the postfix of the query string:   (i) computing a substring value by applying a mapping function to the substring of characters, wherein the mapping function is a rolling hash;   (ii) determining whether the substring value matches a query string value associated with postfix of the query string; and   (iii) in response to determining the substring value does not match the query string value associated with postfix of the query string, increasing a length of the postfix; and   based on determining whether the substring value matches the query string value, providing an indication of an occurrence of the query string associated with the text.   
     
     
         8 . The computerized method of  claim 7 , wherein computing the substring value comprises initializing a baseline substring value or updating a previous computed substring value by applying the mapping function to a previous substring of characters and one or more characters of the substring of characters. 
     
     
         9 . The computerized method of  claim 7 , wherein identifying a substring match between the text and the query string limit processing of the one or more characters of the text to a single sequential pass of the one or more characters of the text. 
     
     
         10 . The computerized method of  claim 7 , wherein the indication of the occurrence of the query string associated with the text comprises a numerical representation of a location of the query string in the text. 
     
     
         11 . The computerized method of  claim 7 , wherein the query string value is calculated by applying the mapping function to the postfix of the query string. 
     
     
         12 . The computerized method of  claim 7 , wherein the identifying a substring match between the text and the query string comprises finding a longest sequence of characters that occur in the text and the postfix of the query string. 
     
     
         13 . The one or more computer storage media of  claim 7 , the identifying the substring match between the text and a query string comprises storing the substring of characters to a local memory having a size less than a size of the text. 
     
     
         14 . A computerized system comprising:
 one or more hardware processors and memory configured to provide computer program instructions to the one or more hardware processors;   a substring processing engine configured to use the one or more hardware processors to detect, from a text obtained in a stream including a plurality of characters of a text received in an arbitrary order, a substring of characters of the text that matches at least a postfix of a query string, based at least on limiting processing of characters of the text to a single sequential pass of characters streamed from the text, wherein the substring processing engine, as a result of determining that the substring of characters does not matches the query string, uses a mapping function that applies a previously calculated hash values and at least one additional character from the substring of characters to determine a match with the postfix of the query string, where the query string is stored in the memory and the mapping function is a rolling hash; and   a recommendation component configured to use the one or more hardware processors to cause a user interface to present a representation of one or more substrings of characters of the text that match the query string.   
     
     
         15 . The computerized system of  claim 14 , wherein processing of characters of the text comprises:
 based on determining that the substring of the text does not match the query string, generating an updated substring by updating the substring by removing a first character of the substring and including a next character from the characters streamed from the text; and   updating a substring value computed for the substring by applying a mapping function to the updated substring.   
     
     
         16 . The computerized system of  claim 15 , wherein the mapping function is a rolling hash. 
     
     
         17 . The computerized system of  claim 14 , wherein the substring processing engine is further configured to use the one or more hardware processors to detect the substring of characters of the text that matches the query string substring comprises finding a longest sequence of characters that occur in the text and the postfix of the query string. 
     
     
         18 . The one or more computer storage media of  claim 1 , wherein the rolling hash function is a Rabin-Karp function. 
     
     
         19 . The computerized method of  claim 7 , wherein the computerized method further comprises:
 determining that the substring of the text does not match the query string;   generating an updated substring by removing a first character of the substring and including in the substring a next character from the characters represented in the stream; and   updating the substring value by applying the mapping function to the updated substring.   
     
     
         20 . The one or more computer storage media of  claim 1 , wherein the substring is obtained from the asymmetric stream and not stored in the local memory.