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 which 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.

REFERENCE TO SEQUENTIAL LISTING, ETC

BACKGROUND

1. Technical Field

The present disclosure pertains to a dictionary having methods for storing words, and more particularly to, a hierarchical dictionary generally having short, medium, and long-term storage layers as filtered based on frequency.

2. Description of the Related Art

Humans have an implicit ability to spot errors i.e., misspellings, within text despite the fact that they do not explicitly know all words possible within specific documents or might read a word or a phrase for the first time. For example, within the phrase “PHYSICS EDU POLE VLT” a human reader can spot the mixture of two words: “Physics Education” and “Pole Vault”. A well-grounded understanding of words is typically formed by learning and exposure.

In creating dictionaries, words are often assigned to a particular unique identifier. These types of dictionaries, however, not only take up a substantial amount of memory as more words are added overtime but also lack meaning, as they are incapable of giving users a view of how words are used in processed documents. Accordingly, there is a need for a system and methods of storing words into a dictionary which mimics a human brain's capability of storing words at a short or long term basis depending on a number of times a word has been used.

SUMMARY

A system and methods for organizing a set of words associated with one or more documents based on frequency are disclosed.

A hierarchical dictionary stored in a memory and communicatively coupled to one or more applications in a computing device may include a first layer of data structure for storing a first set words associated with a portion of a document, a second layer of data structure for storing a second set of words including the first set of words and corresponding frequencies thereof in the document, and a third layer of data structure for storing a third set of words from the second set of words exceeding a predetermined frequency limit. All of the first, second, and third layer of data structures may be implemented as hash maps and may be treated as independent dictionaries.

The first set of words stored in the first data structure may be swiped clean following a predetermined period or a triggering event. The second data structure acts as a filter for promoting a set of words from the first data structure exceeding a predetermined frequency limit to the third data structure or for retaining the set of words therein. The third data structure, when receiving words from the second data structure, may store words at a substantially longer period of time in the memory coupled to or integral with the computing device relative to being stored in the first and second data structures.

In one example embodiment, a method for storing words associated with a document includes: identifying a hash value associated with each word; storing in the first and second hash maps the word to a bucket position associated with the identified hash value; following a predetermined period of time, determining whether a frequency of the word exceeded a predetermined frequency limit; and promoting the word to a next layer of data structure upon a positive determination that the predetermined frequency limit for the word has been exceeded.

Other embodiments, objects, features and advantages of the disclosure will become apparent to those skilled in the art from the detailed description, the accompanying drawings and the appended claims.

DETAILED DESCRIPTION OF THE DRAWINGS

It is to be understood that the disclosure is not limited to the details of construction and the arrangement of components set forth in the following description or illustrated in the drawings. The disclosure is capable of other example embodiments and of being practiced or of being carried out in various ways. For example, other example embodiments may incorporate structural, chronological, process, and other changes. Examples merely typify possible variations. Individual components and functions are optional unless explicitly required, and the sequence of operations may vary. Portions and features of some example embodiments may be included in or substituted for those of others. The scope of the disclosure encompasses the appended claims and all available equivalents. The following description is therefore, not to be taken in a limited sense, and the scope of the present disclosure is defined by the appended claims.

Also, it is to be understood that the phraseology and terminology used herein is for the purpose of description and should not be regarded as limiting. The use herein of “including”, “comprising”, or “having” and variations thereof is meant to encompass the items listed thereafter and equivalents thereof as well as additional items. Further, the use of the terms “a” and “an” herein do not denote a limitation of quantity but rather denote the presence of at least one of the referenced item.

In addition, it should be understood that example embodiments of the disclosure include both hardware and electronic components or modules that, for purposes of discussion, may be illustrated and described as if the majority of the components were implemented solely in hardware.

It will be further understood that each block of the diagrams, and combinations of blocks in the diagrams, respectively, may be implemented by computer program instructions. These computer program instructions may be loaded onto a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions which execute on the computer or other data processing apparatus may create means for implementing the functionality of each block or combinations of blocks in the diagrams discussed in detail in the description below.

Accordingly, blocks of the diagrams support combinations of means for performing the specified functions, combinations of steps for performing the specified functions and program instruction means for performing the specified functions. It will also be understood that each block of the diagrams, and combinations of blocks in the diagrams, can be implemented by special purpose hardware-based computer systems that perform the specified functions or steps, or combinations of special purpose hardware and computer instructions.

Disclosed are a hierarchical dictionary and methods for organizing a set of words based upon a frequency thereof in a document. The hierarchical dictionary includes short term, medium term, and long term dictionaries and includes instructions for performing methods where the propagation of words as inputted from the short term dictionary towards the long term dictionary via the medium term dictionary is controlled by word frequency and insertion over time, as will be discussed in greater detail below.

It is to be noted that the term “dictionary” and “word” does not limit the content that can be inserted and searched for to text content. The “dictionary” referred to herein includes functions that are the same as that of normal dictionaries, such as, for example, insertion and removal of words, getting the relative frequencies of stored words, word lookup, and the like. Also, a “word” may refer to other forms of data, such as, but not limited to phrases, images, sounds, and other forms which can be represented in a data type that is implemented within the dictionary. Other types of data format in a document besides text which can be stored and searched for in a dictionary may be apparent in the art.

FIG. 1shows one example embodiment of a system100including a hierarchical dictionary105for storing a word110from one or more documents115. System100further includes a computing device120including at least one processor125and a program interface130. While shown as a separate entity, hierarchical dictionary105may be stored in a computer-readable storage medium135remotely located from computing device120, in a memory of computing device120(not shown), or a combination of both, provided that it is communicatively coupled to processor125. Hierarchical dictionary105includes a short term layer142, a medium term layer144, and a long term layer146. Respective word storage capacities of short term, medium term, long term layers142,144,146varies based upon a size of data to be processed, i.e., one or more documents115. InFIG. 1, when any word110is entered by a user via program interface130for storage or lookup, program interface130communicates with processor125for the processor to communicate with hierarchical dictionary105. A number of layers in hierarchical dictionary105may not be limited to 3, as shown. In other example embodiments, additional intermediate filtering layers with different sizes and parameters besides medium term layer144may be desired. Also, while word110is shown as being tied up to one or more documents115, it will be apparent in the art that word110may be standalone and need not necessarily be related to any document115. Combinations and permutations for the elements in system100and other components of computing device120may be apparent in the art.

Connections between the aforementioned elements inFIG. 1depicted by the arrows may be performed in a shared data bus of computing device120. Alternatively, the connections may be through a network that is capable of allowing communications between two or more remote computing systems, as discussed herein, and/or available or known at the time of the filing, and/or as developed after the time of filing. The network may be, for example, a communications network or network/communications network system such as, but not limited to, a peer-to-peer network, a Local Area Network (LAN), a Wide Area Network (WAN), a public network such as the Internet, a private network, a cellular network, and/or a combination of the foregoing. The network may further be a wireless, a wired, and/or a wireless and wired combination network.

InFIG. 1, hierarchical dictionary105may be stored on computer-readable storage medium135and include a set of instructions from processor125for receiving and performing methods using word110. In particular, hierarchical dictionary105includes program instructions for performing a method for organizing a set of words110based upon relative frequencies thereof (insert method,FIG. 3) and a method for searching words (lookup method,FIG. 4). While independent in structure and operation, short term, medium term, and long term layers142,144, and146(collectively referred to as SML layers herein) of hierarchical dictionary105, are communicatively connected to the other via medium term layer144. Specifically, short term layer142is communicatively connected to long term layer146and vice-versa via medium term layer144. In this manner, medium term layer144acts as a filter.

Hierarchical dictionary105may be a module or a functional unit for installation onto a computing device and/or for integration to an application such as program interface130. Each of short term layer142, medium term layer144, and long term layer146, which are also referred to herein as S-layer142, M-layer144, and L-layer146, respectively, may each be implemented as a fixed size hash map, with L-layer146having a substantially largest word storage capacity, as will be detailed below with respect toFIG. 2. Other types of data structures besides hash maps may be apparent in the art.

S-layer142includes instructions for storing relatively smaller chunk of data within and/or relating to document115(e.g., order of the number of words in text of one page, words in a paragraph or document). M-layer144, also referred to herein as M-layer144, includes instructions for storing a set of words that are relatively more frequent. In the present disclosure, M-layer144further includes instructions for gathering statistics which may be associated, for example, to the usage frequency of word110in document115. Being a statistical filter, M-layer144further includes instructions for propagating or transferring word110from being stored in S-layer142to L-layer146and for removing stored words therein, as will be discussed in greater detail below. L-layer146includes instructions for receiving words from M-layer144for storing word110at a relatively longer period of time.

In S-layer142, word110and/or other data relating to document115may be stored temporarily. In one aspect, word110that are stored in S-layer142may be swiped clean by a triggering event, such as, for example, when a new document, paragraph, or page is being processed. A hash map for M-layer144may be augmented with a predecessor and a successor in the sense of a doubly linked list for keeping track of the youngest and oldest words that it stores. The data structure in L-layer may include a tree. For purposes of illustration and not by limitation, the general steps for the insertion and lookup method are shown inFIG. 2.

FIG. 2is a schematic diagram showing a generic set of steps for inserting or searching one of word110in hierarchical dictionary105. As shown inFIG. 2, a capacity of S-layer142may be set to about a single document115. To this end, S-layer142may be cleared every time a single document115is being processed. A capacity of M-layer144may be set to about 10 to 100 documents115whereas a capacity limit may not be defined for L-layer146.

InFIG. 2, when inserting a word110for storage to hierarchical dictionary105and as represented by step1, a single word110is first inserted or stored in S-layer142. Frequency limits may be predefined within hierarchical dictionary115for every one of S-layer142, M-layer144, and L-layer146. In one example embodiment, hierarchical dictionary105may include instructions to determine whether a frequency of word110has exceeded a first predetermined limit and a second predetermined limit for word110to be promoted to M-layer144and L-layer146, respectively. Thus, word110may be promoted from S-layer142to M-layer144when the first predetermined limit has been exceeded (step2). Following a period of time that the same word110has been repeatedly inserted or stored to hierarchical dictionary105and when a frequency of word110has exceeded the second predetermined limit, word110may then be promoted from M-layer144to L-layer146for relatively longer term storage. In setting frequency limits prior promoting word110to the higher layers within hierarchical dictionary105, an input and recall ability of humans may be mimicked.

Alternatively, hierarchical dictionary105may include instructions for M-layer144to copy word110stored in S-layer1, to track a frequency of each word110inserted, and to only promote word110towards L-layer146once a predetermined frequency limit has been exceeded, making transfer of word110from relatively short to long term storage at one-time.

With reference still inFIG. 2and in one example embodiment, when searching for a word110within hierarchical dictionary105, L-layer146may be initially searched (step A). When the same word110has not been found in L-layer146, consequently, S-layer142may be searched (step B). Alternatively, word110may be simultaneously searched on both S- and L-layers142,146.

FIG. 3is a flowchart detailing the steps of inserting word110to hierarchical dictionary105. Program interface130may include program instructions to receive a request from a user of computing device120indicating word110to be inserted onto hierarchical dictionary105. At block305, each word110may either be retrieved from document115or received from processor125. In one example embodiment, word110may be a portion of the content extracted from document115. In another example embodiment, word110may be part of an input received from a user of program interface130not necessarily in relation to any document115. In yet another example embodiment, word110may be automatically received or retrieved for insertion to hierarchical dictionary105when a controller of computing device120(not shown) has determined that word110is not included in hierarchical dictionary, as a result of a lookup process detailed in the steps ofFIG. 4.

Blocks310to325recites steps typically performed for inserting a value into a hash map, as will be known in the art. For example, at block310, a hash value corresponding to word110in block305may be identified. Identifying the hash value corresponding to word110may include determining, using a hash function with word110as the input value, a unique integer corresponding to word110. The determined hash value is indicative of a unique index identifier for a position in a bucket of the hash map to which a pair of values is operative to be stored. In the present disclosure, each pair of values in the bucket comprises word110as well as a frequency thereof. At block315, it is then determined whether the bucket position associated with the identified hash value contains an entry for checking whether word110is already within hierarchical dictionary105. At block320, upon a determination that the bucket position associated with the determined hash value is empty or that hierarchical dictionary105does not contain word110, word110is stored into said bucket position. In storing word110into the bucket, a frequency thereof may be initialized. At block325, upon a determination the bucket position associated with the determined hash value contains a pair of values, such that word110is already stored in the hierarchical dictionary, a frequency thereof also stored in the bucket is updated. Updating a frequency may include incrementing a frequency of word110stored in the bucket position.

In one example embodiment, steps in blocks315to325may be performed at both hash maps associated with S-layer142and M-layer144. In another example embodiment, steps in blocks315to325may be initially performed in S-layer142and words110may be promoted or transferred to M-layer144following a predetermined period (e.g., when a new document115is being processed) or when a word110has reached a predetermined frequency limit for it to be promoted to M-layer144for storage at a longer period of time than when stored in S-layer142.

At block330, following updating of word frequency, the controller then determines whether the frequency of word110stored therein exceeds a predetermined limit, particularly, a limit for promotion to the next layer in hierarchical dictionary105, and if so, at block335, promotes word110to the next layer. Promoting word110to another layer includes transferring word110to a hash map associated with the next layer in the hierarchy and removing entries in the current layer associated with word110. In the context for example where a word110is stored in S-layer142and the controller has determined that the frequency of word110has exceeded a predetermined frequency limit for words stored in the S-layer, word110is promoted to next layer M-layer144. Similar steps will be apparent for promoting words from M-layer144to L-layer146; however, word110has to exceed a second predetermined frequency limit substantially greater than the predetermined frequency limit in S-layer142for promotion from M-layer144to L-layer146. Otherwise, at block340, word110is retained in the current layer to which it is stored.

FIG. 4is a flowchart detailing the steps of searching words110within hierarchical dictionary105. Program interface130may include program instructions to receive a request from a user of computing device120indicating word110to be searched. At blocks405and410, respectively, word110is received and a hash value corresponding to word110is determined, similar to blocks305and310inFIG. 3.

At block415, since the hash value is a unique identifier to a bucket position associated to a hash map in any of SML layers142,144,146, the hash value determined at block410is used to determine whether the hash map in L-layer146associated with the hash value includes word110.

At block420, upon a determination that word110is stored at the specific bucket position in L-layer146corresponding to the hash value, one or more program instructions in hierarchical dictionary105may send a notification to computing device120indicating presence of word110in L-layer146. In one example embodiment, hierarchical dictionary105may send word110and a frequency thereof indicated in the corresponding bucket to program interface130based upon a search request received therefrom. Otherwise, upon a determination that the bucket position in L-layer146corresponding to the hash value determined at block410does not include word110, then at block425, the controller may determine whether the hash map in S-layer142associated with the hash value includes word110.

At block425, upon a determination that word110is stored at the specific bucket position in S-layer142corresponding to the hash value determined at block410, then, similar to block415, hierarchical dictionary105may send word110and a frequency thereof to program interface130based upon a search request received therefrom. However, upon a determination that the bucket position in S-layer142corresponding to the hash value determined at block410does not include word110, then at block430, the controller may send a notification to computing device120indicating absence of word110in hierarchical dictionary105. In addition, word110, when found neither in S-layer142nor L-layer146, may be inserted into hierarchical dictionary105. Steps for inserting words to hierarchical dictionary105, as detailed inFIG. 3, may be automatically performed for word110following determination of an absence thereof in the hierarchical dictionary of the present disclosure.

It will be appreciated that the actions described and shown in the example flowcharts may be carried out or performed in any suitable order. It will also be appreciated that not all of the actions described inFIGS. 3 and 4need to be performed in accordance with the example embodiments and/or additional actions may be performed in accordance with other example embodiments of the disclosure.