Tochenized cache
Methods of and systems for searching a catalog include parsing the items of the catalog into tokens, determining the frequency with which each token appears in the catalog, and storing the frequencies in a cache. Queries to the catalog are likewise parsed into tokens, and the tokens of the query string are compared to frequency values in the cache to identify a smaller search space within the catalog.
1. A computer-implemented method of searching a catalog of textual items, comprising:
parsing each textual item of the catalog to determine a set of tokens, wherein each token is a consecutive set of characters having the same predetermined length;
storing the each of the tokens in a memory cache;
for each token, storing a frequency value indicative of the frequency with which that token appears in the catalog;
receiving a textual search query;
parsing the textual query into tokens;
selecting an optimal search token from the textual query based on the frequency value of that token in the memory cache;
searching a subset of the catalog for contents of the textual search query, wherein the subset of the catalog is a set of items that include the optimal search token; and
providing a result of the search.
2. The method of claim 1 , wherein the predetermined length is two characters.
3. The method of claim 1 , wherein the predetermined length is three characters.
4. The method of claim 1 , wherein selecting an optimal search token comprises selecting the token having the lowest frequency value in the memory cache.
5. The method of claim 1 , wherein selecting an optimal search token comprises:
determining whether the length of the search query exceeds a predetermined length;
calculating a probability that a first token of the search query appears adjacent to a second token of the search query; and
selecting a first-parsed first token having a combined frequency value in the memory cache and calculated probability that is below a predetermined threshold.
6. The method of claim 1 , wherein selecting an optimal search token comprises:
calculating a probability that a first token of the search query appears adjacent to a second token of the search query; and
selecting a first-parsed first token having a combined frequency value in the memory cache and calculated probability that is below a predetermined threshold.
7. The method of claim 1 , further comprising:
storing in the memory cache a list of words that commonly appear in the catalog;
storing, for each word, an associated optimal search token;
parsing the textual query to determine if any word of the query is stored in the list of words and, if so, searching a subset of the catalog for contents of the textual search query, wherein the subset of the catalog is a set of items that include the optimal search token associated with the word of the query.
8. The method of claim 1 , further comprising:
storing the textual search query as a first textual search query in the memory cache;
storing the result of the first textual search query search in the memory cache;
receiving a second textual search query; and
determining if the second textual search query matches the first textual search query and, if so, returning the result of the first textual search query.
9. A system for searching a catalog of data items stored on a non-transitory computer readable medium, wherein the data items each comprise a set of text characters divisible into a plurality of tokens, each token being a set of consecutive characters of the same predetermined length within the data item, the system comprising:
a memory cache having a matrix storing each of the plurality of tokens of the catalog and a frequency value indicative of the frequency with which each token appears in the catalog,
wherein searches of the catalog are limited to a subset of the data items based on the frequency values stored in the memory cache.
10. The system of claim 9 , wherein the predetermined length is three characters.
11. The system of claim 9 , wherein the predetermined length is two characters.
12. The system of claim 9 , wherein the subset of the data items is a set of data items having a token of a textual search query with a lowest frequency value in the memory cache among other tokens of the textual search query.
13. The system of claim 9 , wherein the subset of the data items is a set of data items having an optimal token of a textual search query, wherein the optimal token is selected by:
calculating a probability that a first token of the search query appears adjacent to a second token of the search query; and
selecting a first-parsed first token of the search query having a combined frequency value in the memory cache and calculated probability that is below a predetermined threshold.
14. The system of claim 9 , wherein the memory cache further includes a list of words that frequently appear in catalog and an optimal search token for each word of the list.
15. The system of claim 9 , wherein the memory cache further includes a list of prior textual search queries and a search result associated with each prior textual search query of the list.
16. The system of claim 9 , wherein the subset of the data items is a set of data items having an optimal token of a textual search query, wherein the optimal token is selected by:
determining whether the length of the search query exceeds a predetermined length;
calculating a probability that a first token of the search query appears adjacent to a second token of the search query; and
selecting a first-parsed first token of the search query having a combined frequency value in the memory cache and calculated probability that is below a predetermined threshold.
17. A method of searching a catalog of textual items for an item provided by a search query, the method comprising:
dividing the catalog into a plurality of search spaces, wherein each search space corresponds to the set of all items in the catalog containing a specific token of a plurality of tokens, wherein each token of the plurality of tokens has the same predetermined length;
selecting a search space based on a frequency with which a token of item provided by the search query appears in items of the catalog; and
searching the selected search space for the item provided by the search query.
18. The method of claim 17 , wherein the step of selecting a search space further comprises selecting the search space corresponding to the lowest-frequency token in the item provided by the search.
19. The method of claim 17 , wherein the step of selecting a search space further comprises:
calculating a probability that a first token of the item provided by the search query appears adjacent to a second token of the item provided by the search query; and
selecting the search space corresponding to a first-parsed first token of the item provided by the search query that has a combined frequency and calculated probability below a predetermined threshold.
20. The method of claim 17 , wherein the step of selecting a search space further comprises:
determining whether the length of the item provided by a search query exceeds a predetermined length;
calculating a probability that a first token of the item provided by the search query appears adjacent to a second token of the item provided by the search query; and
selecting the search space corresponding to a first-parsed first token of the item provided by the search query that has a combined frequency and calculated probability below a predetermined threshold.