System and method for performing longest common prefix strings searches

Patent metadata

Field	Value
Publication number	US-9558241-B2
Application number	US-201514881328-A
Country	US
Kind code	B2
Filing date	Oct 13, 2015
Priority date	Apr 22, 2009
Publication date	Jan 31, 2017
Grant date	Jan 31, 2017

Abstract

A method and system a method for compressing and searching a plurality of strings. The method includes inputting a plurality of strings into a compression engine. The method also includes converting each of the plurality of strings into a new, prefix-preserving compressed string, using the compression engine. For every string P that is a strict prefix of a string S, P's resulting compressed string is a strict prefix of S's resulting compressed string.

First claim

We claim as our invention:

1. A system for searching for a particular string among a plurality of prefix preserving compressed strings, the system comprising:
at least one processor; and
memory encoding computer executable instructions that, when executed by the at least one processor, perform a method comprising:
identifying a plurality of strings, wherein a subject of the plurality of strings have a strict prefix;
compressing the plurality of strings into a plurality of prefix-preserving compressed strings, wherein the plurality of prefix-preserving compressed strings comprises a compressed subset of strings corresponding to the subset of the plurality of strings such that each string in the compressed subset of strings has a matching compressed strict prefix; and

storing the plurality of prefix-preserving compressed strings.

2. The system according to claim 1 , wherein each of the plurality of strings represents at least one of a group comprising a uniform resource locator, name, a number, a street address, an IP address and strings of code.

3. The system according to claim 1 , further comprising instructions for storing the plurality of prefix-preserving compressed strings in an ordered list data structure, a database, a tree data structure, a graph data structure, a trie data structure or a client library.

4. The system according to claim 1 , wherein compression of the plurality of strings is performed by a compression engine, and wherein the compression engine represents at least one of a group comprising a dictionary based compression engine, an entropy based compression engine, a run-length compression engine, an LZ77 compression engine, an LZ78 compression engine, an LZW compression engine, a Huffman compression engine, a Golomb compression engine, a universal code compression engine, an Elias gamma compression engine, a dynamic markov compression engine, and an arithmetic compression engine.

5. The system according to claim 1 , further comprising instructions for applying a search algorithm to find the resulting compressed string among the plurality of compressed strings, wherein the search algorithm represents at least one of a group comprising a linear search, a binary search, an interpolation search, a select query, a full text search, a search or find database operation, a breadth-first search algorithm, a depth-first search algorithm, an A* search algorithm, a breadth-first trie search algorithm, a depth-first trie search algorithm, and an A* trie search algorithm.

6. A system for arithmetic coding of uniform resource locator strings, the system comprising:
at least one processor; and
memory encoding computer executable instructions that, when executed by the at least one processor, perform a method comprising:
receiving a plurality of uniform resource, each of the plurality of uniform resource locators having a string value;
analyzing the string value of each of the plurality of uniform resource locators;
generating an arithmetic coded hash for each of the plurality of uniform resource locators according to the string value of each of the plurality of uniform resource locators to create a plurality of hashed uniform resource locators; and
grouping each of the plurality of hashed uniform resource locators according to a hashed string value of each of the plurality of uniform resource locators to create a subset of the plurality of hashed uniform resource locators;
wherein a hashed uniform resource locator of the plurality of hashed uniform resource locators has a string value within a predetermined string range and has a numeric hash value that is in character proximity to a numeric hash value of a second hashed uniform resource locator of the plurality of hashed uniform resource locators having a string value within the predetermined string range.

7. The system according to claim 6 , wherein each of the plurality of uniform resource locators represents a Web site.

8. The system according to claim 6 , the uniform resource locator has a hash value of 32 characters.

9. The system according to claim 6 , further comprising instruction for storing the plurality of hashed uniform resource locators in a database.

10. The system according to claim 6 , further comprising instructions for storing the plurality of hashed uniform resource locators in a client library.

11. The system according to claim 6 , further comprising instructions for transmitting the plurality of hashed uniform resource locators over a network to a local area network to be stored in a database of the local area network.

12. The system according to claim 11 , further comprising instructions for:
receiving a request for an Internet service at a security appliance of the local area network from at least one of a plurality of client-side devices;
controlling access to the Internet service by the at least one of the plurality of client-side devices through the security appliance;
analyzing a hashed uniform resource locator for the Internet service, the hashed uniform resource locator having a string value within a predetermined string range and a hash value that is in character proximity to a hash value of another hashed uniform resource locator of the plurality of hashed uniform resource locators that has a string value within the predetermined string range; and
determining access to the Internet service based on the hash value of the hashed uniform resource locator being within a range established for the local area network.

13. The system according to claim 12 wherein the at least one client-side device of the plurality of client-side devices is a personal computer.

14. The system according to claim 12 wherein the at least one client-side device of the plurality of client-side device is a PDA.

15. The system according to claim 6 , wherein the generating the arithmetic coded hash for each of the plurality of uniform resource locators is performed at a data collection site.

16. The system according to claim 6 , wherein an Internet service is a Web site.

17. A storage device encoding computer executable instructions that, when executed by at least one processor, perform a method comprising:
identifying a plurality of strings, wherein a subset of the plurality of strings have a strict prefix,
compressing the plurality of strings into a plurality of prefix-preserving compressed strings, wherein the plurality of prefix-preserving compressed strings comprises a compressed subset of strings corresponding to the subset of the plurality of strings such that each string in the compressed subset of strings has a matching compressed strict prefix; and
storing the plurality of prefix-preserving compressed strings.

18. The storage device according to claim 17 , further comprising instructions for storing the plurality of prefix-preserving compressed strings in an ordered list data structure, a database, a tree data structure, a graph data structure, a trie data structure or a client library.

19. The storage device according to claim 17 , wherein compression of the plurality of strings is performed by a compression engine, and wherein the compression engine represents at least one of a group comprising a dictionary based compression engine, an entropy based compression engine, a run-length compression engine, an LZ77 compression engine, and LZ78 compression engine, an LZW compression engine, a Huffman compression engine, a Golomb compression engine, a universal code compression engine, an Elias gamma compression engine, a dynamic markov compression engine, and an

Assignees

• Webroot Inc

Inventors

• Harris Christopher
• Lonas Hal

Classifications

• G06F16/258

  Data format conversion from or to a database · CPC title

• G06F16/24561 Primary

  Intermediate data storage techniques for performance improvement · CPC title

• G06F16/116

  Details of conversion of file system types or formats · CPC title

• H04L61/301 Primary

  Name conversion · CPC title

• H04L63/168

  above the transport layer · CPC title