Hierarchical dictionary with statistical filtering based on word frequency
A hierarchical dictionary having methods of storing words based on frequency thereof in one or more documents that includes the steps of identifying a hash value corresponding to an inputted word; storing the word in a first hash map and in a second hash map having a substantially larger word storage capacity than the first hash map based on the identified hash value; clearing the first hash map at every predetermined period or triggering event; determining whether a frequency of the word as stored in the second hash map exceeds a predetermined value; and if so, promoting the word from the second hash map to a third hash map having a substantially larger word storage capacity than the second hash map for long-term storage and later retrieval.
1 . A method performed by a processor of a computing device for organizing a plurality of words associated with a document, the method comprising:
obtaining, by the processor, the plurality of words;
storing, by the processor, a word in the plurality of words in a first data structure stored in memory accessible to the processor, wherein the first data structure has a first word capacity;
updating, by the processor, a frequency of the word in the first data structure;
storing, by the processor, the word in a second data structure stored in the memory accessible to the processor, wherein the second data structure has a second word capacity that is greater than the first word capacity; and
ranking, by the processor and based upon the frequency, the word relative to each other of the plurality of words;
promoting, by the processor and based upon the ranking, the word to a third data structure at a longer period of time than when stored in second data structure after a predetermined period of time that initiates in response to the word reaching a predetermined frequency limit in the second data structure, wherein the third data structure has a third word capacity that is greater than the second word capacity of the second data structure;
gathering into the second data structure, by the processor based upon the ranking and instructions in the second data structure, statistics on each of the plurality of words in the document, wherein the second data structure comprises the instructions that operate to statistically filter the plurality of words being inputted for gathering the statistics on each of the plurality of words in the document and to filter the plurality of words stored in the first data structure and the third data structure; and
based on the instructions in the second data structure, filtering, by the processor, the plurality of words stored in the first data structure and the third data structure by transferring and removing between the first data structure and the third data structure each of the plurality of words based on the statistics that the second data structure gathered.
2 . The method of claim 1 , wherein the plurality of words are stored in a first hash map stored in the first data structure, wherein the second plurality of words are stored in a second hash map stored in the second data structure.
3 . The method of claim 1 , wherein the first data structure, the second data structure, and the third data structure form layers of a data structure, each of the layers comprising a fixed size hash map that is associated with a different capacity limit, a different frequency limit, and a different period of time from one another among the plurality of words.
4 . The method of claim 1 , wherein the document is a dictionary.
5 . The method of claim 1 , wherein the word includes phrases, images, and sounds.
6 . The method of claim 1 , wherein the plurality of word are input to a first hash map and a second hash map, wherein the first hash map has a first word capacity and the second hash map has a second word capacity, wherein the second word capacity is greater than the first word capacity.
7 . The method of claim 6 , wherein for each word of the plurality of words:
identifying a hash value corresponding to a word in the first hash map and the second hash map, determining whether a bucket associated with the hash value is empty;
upon a determination that the bucket is empty, setting a frequency of the word to a first value and storing the word and the frequency of the word in the bucket; and
upon a determination that the bucket is not empty, updating the frequency of the word in the bucket to a second value.
8 . The method of claim 7 , further comprising:
determining, in the second hash map and after a predetermined period of time has elapsed, whether the frequency of at least one of the plurality of words is equal to or greater than a predetermined limit; and
upon a positive determination that the frequency of the at least one of the plurality of words is equal to or greater than the predetermined limit, promoting each of the at least one of the plurality of words to a third hash map, wherein the third hash map has a third word capacity, wherein the third word capacity is greater than the second word capacity,
wherein a first word in the plurality of words has a frequency that is less than the predetermined limit stored in the second hash map and a second word in the plurality of words has a frequency that is equal to or greater than the predetermined limit stored in the third hash map, the second hash map keeping respective frequencies of the plurality of words and including program instructions for performing the promoting from the first hash map to the third hash map.
9 . A computing device, comprising:
a processor; and
memory storing instructions that, when executed by the processor, cause the processor to perform acts comprising:
obtaining, by the processor, a plurality of words associated with a document;
storing, by the processor, a word in the plurality of words in a first data structure stored in memory accessible to the processor, wherein the first data structure has a first word capacity;
updating, by the processor, a frequency of the word in the first data structure;
storing, by the processor, the word in a second data structure stored in the memory accessible to the processor, wherein the second data structure has a second word capacity that is greater than the first word capacity; and
ranking, by the processor and based upon the frequency, the word relative to each other of the plurality of words;
promoting, by the processor and based upon the ranking, the word to a third data structure at a longer period of time than when stored in second data structure after a predetermined period of time that initiates in response to the word reaching a predetermined frequency limit in the second data structure, wherein the third data structure has a third word capacity that is greater than the second word capacity and the second data structure;
gathering into the second data structure, by the processor based upon the ranking and instructions in the second data structure, statistics on each of the plurality of words in the document, wherein the second data structure comprises the instructions that operate to statistically filter the plurality of words being inputted for gathering the statistics on each of the plurality of words in the document and to filter the plurality of words stored in the first data structure and the third data structure; and
based on the instructions in the second data structure, filtering, by the processor, the plurality of words stored in the first data structure and the third data structure by transferring and removing between the first data structure and the third data structure each of the plurality of words based on the statistics that the second data structure gathered.
10 . The computing device of claim 9 , wherein the plurality of words are stored in a first hash map stored in the first data structure, wherein the second plurality of words are stored in a second hash map stored in the second data structure.
11 . The computing device of claim 9 , wherein the word is cleared from the third data structure periodically.
12 . The computing device of claim 9 , wherein the document is a dictionary.
13 . The computing device of claim 9 , wherein the word includes phrases, images, and sounds.
14 . The computing device of claim 9 , wherein the plurality of word are input to a first hash map and a second hash map, wherein the first hash map has a first word capacity and the second hash map has a second word capacity, wherein the second word capacity is greater than the first word capacity.
15 . A non-transitory computer-readable storage medium having stored therein a first data structure for storing a plurality of words associated with a document for a predetermined period of time, the first data structure having a first word capacity, a second data structure, wherein the second data structure has a second word capacity that is greater than the first word capacity; the medium further including instructions for performing acts comprising:
obtaining, by a processor, the plurality of words;
storing, by the processor, a word in the plurality of words in a first data structure stored in memory accessible to the processor;
updating, by the processor, a frequency of the word in the first data structure;
storing, by the processor, the word in a second data structure stored in the memory accessible to the processor; and
comparing by the processor and based upon the frequency, the word relative to each other of the plurality of words;
promoting, by the processor and based upon the comparing, the word to a third data structure at a longer period of time than when stored in second data structure after a predetermined period of time that initiates in response to the word reaching a predetermined frequency limit in the second data structure, wherein the third data structure has a third word capacity that is greater than the second word capacity and the second data structure;
gathering into the second data structure, by the processor based upon the comparing and instructions in the second data structure, statistics on each of the plurality of words in the document, wherein the second data structure comprises the instructions that operate to statistically filter the plurality of words being inputted for gathering the statistics on each of the plurality of words in the document and to filter the plurality of words stored in the first data structure and the third data structure; and
based on the instructions in the second data structure, filtering, by the processor, the plurality of words stored in the first data structure and the third data structure by transferring and removing between the first data structure and the third data structure each of the plurality of words based on the statistics that the second data structure gathered.
16 . The non-transitory computer-readable storage medium of claim 15 , wherein the plurality of words are stored in a first hash map stored in the first data structure, wherein the second plurality of words are stored in a second hash map stored in the second data structure.
17 . The non-transitory computer-readable storage medium of claim 15 , wherein the word is cleared from the third data structure periodically.
18 . The non-transitory computer-readable storage medium of claim 15 , wherein the document is a dictionary.
19 . The non-transitory computer-readable storage medium of claim 15 , wherein the word includes phrases, images, and sounds.
20 . The non-transitory computer-readable storage medium of claim 15 , wherein the plurality of word are input to a first hash map and a second hash map, wherein the first hash map has a first word capacity and the second hash map has a second word capacity, wherein the second word capacity is greater than the first word capacity.