System and methods for streaming string similarity and pattern matching
AssigneeAdobe Inc.
InventorsTung Mai, Ryan A. Rossi, Anup Rao
Life of this patent
Estimating the term…
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.
Claims20
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 a stream representing one or more characters of a text;
- applying a mapping function to a substring of the text to compute a substring value, wherein the sub string comprises one or more characters represented in the stream, and a length of the substring corresponds to a length of a query string;
- determining whether the sub string of the text matches the query string by comparing the substring value to a query string value associated with the query string;
- and
- based on determining whether the substring of the text matches the query string, providing an indication of the substring.
A computerized method comprising:
- receiving a stream representing one or more characters of a text;
- identifying a substring match between the text and a query string by, for each sub string of characters in the text having a length equal to the query string:
- (i) computing a substring value by applying a mapping function to the sub string of characters;
- and
- (ii) determining whether the sub string value matches a query string value associated with the query string;
- 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.
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, a substring of characters of the text that matches 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;
- 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.
Dependencies are inferred from the claim text.