Term consolidation for indices

A computer-implemented method, carried out by one or more processors, for consolidating an index entry of a dictionary. In an embodiment, the method comprises the steps of receiving, by one or more processors, a set of parameters, wherein the set of parameters indicates at least a length of prefix and a length of hash value; receiving, by one or more processors, a first term for entry into an index; converting, by one or more processors, the first term for entry into the index according to the set of parameters; and responsive to determining the converted first term is not present in the index, storing, by one or more processors, the first converted term into the index.

BACKGROUND

In the present day, implemented full text search and indexing mechanisms contribute to creating dictionaries that utilize a large amount of storage space. A typical dictionary contains term entries which are stored in a dictionary portion of an index. The larger the number of term entries, the slower the response when handling queries for search terms. When receiving a document, the document is processed for terms which are then added to the index of the dictionary. Typically, a term is added once to the dictionary and the term is referenced to all occurrences of the word in the documents the dictionary has received. The term is searchable, such that all occurrences of the word can be identified utilizing the index entry for the term.

Existing mechanisms for index entries reduce the size of the entries but also reduce recall for the entries. The reduction in recall is due to word filters removing a number of words or terms from a term being entered into the index. For example, existing mechanism can remove filler words, such as “a” or “the”, which the mechanism can deem unnecessary. While this reduces the size of the entry, it also reduces the accuracy of recall when receiving a search term.

SUMMARY

Embodiments of the present invention disclose a method, computer program product and computer system for consolidating an index entry of a dictionary. A computer-implemented method, carried out by one or more processors, for consolidating an index entry of a dictionary comprises the steps of receiving, by one or more processors, a set of parameters, wherein the set of parameters indicates at least a length of prefix and a length of hash value; receiving, by one or more processors, a first term for entry into an index; converting, by one or more processors, the first term for entry into the index according to the set of parameters; and responsive to determining the converted first term is not present in the index, storing, by one or more processors, the converted first term into the index.

DETAILED DESCRIPTION

Embodiments in accordance with the present invention consolidate an index entry of a dictionary by receiving a set of parameters, where the set of parameters indicates a length of prefix and a length of hash value. The length of prefix and the length of hash value may be explicitly included in the set of parameters, or they may be inferred from the set of parameters. For example, the set of parameters may indicate that a specific hash function is to be used, and the hash values generated by that hash function have a predetermined length. Similarly, the length of the prefix may be explicitly included as a parameter or it may be inferred from other information in the set of parameters. The prefix represents a portion of a term and the hash value represents another portion of the term. Embodiments, in accordance with the present invention, can receive a term for entry into an index and convert the term for entry into the index according to the set of parameters (i.e., the length of prefix and the length of hash value). Upon determining the converted term is not present in the index, embodiments, in accordance with the present invention store the converted term into the dictionary portion of the index.

FIG. 1is a functional block diagram illustrating a distributed data processing environment, in accordance with one embodiment of the present invention. The distributed data processing environment includes server computer102and client device104all interconnected over network106.

Server computer102may be a desktop computer, a laptop computer, a tablet computer, a specialized computer server, a smartphone, or any other computer system known in the art. In certain embodiments, server computer102represents a computer system utilizing clustered computers and components that act as a single pool of seamless resources when accessed through network106, as is common in data centers and with cloud computing applications. In general, server computer102is representative of any programmable electronic device or combination of programmable electronic devices capable of executing machine readable program instructions and communicating with other computer devices via a network. In this embodiment, server computer102has the ability to communicate with other computer devices to query the computer devices for information.

Index consolidation program110residing in server computer102has the ability to consolidate dictionary108portion of index112. Index consolidation program110can receive parameters, such as a length of prefix and a length of hash value and can receive a term for entry into index112. Utilizing the prefix and the hash value information, index consolidation program110can convert the received term by calculating the prefix and the hash value for the received term and e.g. concatenating the prefix and the hash value with a separator character in between them into a converted term, and determine if the converted term exists in index112. If index consolidation program110determines the converted term does not exist in index112, index consolidation program110stores the converted term in index112. In this embodiment, index112includes dictionary108and posting lists, not illustrated inFIG. 1. A text search engine can utilize dictionary108, where terms that index consolidation program110stores in index112are searchable through the text search engine.

In general, network106can be any combination of connections and protocols that will support communications between server computer102and client device104. Network106can include, for example, a local area network (LAN), a wide area network (WAN), such as the internet, a cellular network, or any combination of the preceding, and can further include wired, wireless, and/or fiber optic connections.

In one embodiment, dictionary108and index consolidation program110can be a web service accessible via network106to a user of a separate device, such as client device104. In another embodiment, dictionary108and index consolidation program110may be operated directly by a user of server computer102.

In various embodiments of the present invention, client device104can be a laptop computer, a tablet computer, a netbook computer, a personal computer (PC), a desktop computer, a personal digital assistant (PDA), a smartphone, or any programmable electronic device capable of communicating with server computer102via network106. A user of client device104can send a term to dictionary108for entry into index112via user interface114.

User interface (UI)114on client device104displays information that any one of the processes of index consolidation program110may display to a user. User interface114can be, for example, a graphical user interface (GUI) or a web user interface (WUI) that displays text, documents, web browser windows, user options, application interfaces and instructions for operation. User interface114also has the ability to receive user inputs for index consolidation program110.

FIG. 2is a flowchart depicting operational steps of an index consolidation program for consolidating an index of a dictionary, in accordance with an embodiment of the present invention.

Index consolidation program110receives a length of prefix and a length of hash value for index entries (step202). For discussion purposes, an index entry is referred to as a term, where the term includes a set of characters. In this embodiment, the length of prefix and the length of hash value both represent character length values for two portions of an index entry (namely for the prefix and the hash portions), for a term that index consolidation program110receives. An example of a character can include a letter, a number, a character from a particular alphabetical language, or any other computer recognizable symbol. In this embodiment, a length of prefix is a predetermined number of characters of a term being entered into index112of dictionary108, where the predetermined number of characters corresponds to the initial characters of the term. The predetermined number of character of the term are a portion of the complete term being entered into index112. In another embodiment, the predetermined number of characters represent the final characters of the term being entered into index112.

In this embodiment, a length of hash value is a predetermined number of hash characters which represent the other portion of the term. Utilizing a predetermined hash function, index consolidation program110can convert the other portion of the term into the predetermined number of hash characters (that is, convert the other portion of the term into a hash value). Index consolidation program110can receive the hash function via a user input through user interface114and the hash function can be tailored to one or more indices. In this embodiment, index consolidation program110receives a length of prefix of 8 and a length of hash value of 4 for index112entries into dictionary108. Index consolidation program110can represent the length of prefix of 8 and the length of hash value of 4 by “P=8|H=4”.

Index consolidation program110receives a term for entry into the index (step204). In this embodiment, index consolidation program110receives the term for entry into index112via a user input through user interface114on client device104. Dictionary108can receive the term from client device104and send the term to index consolidation program110. In another embodiment, index consolidation program110can receive a list of terms being entered into index112. Index consolidation program110can select the first term from the list of terms to convert according to the received lengths of prefix and hash value from step202.

Index consolidation program110converts the term according to the length of prefix and the length of hash value (step206). In this embodiment, the received length of prefix is 8, the received length of hash value is 4, and the term received is 20 characters long. Index consolidation program110can convert the 20 character term, “A1B2C3D4E5F6G7H8I9J1” into an index entry such as “A1B2C3D4|E7H3” where “A1B2C3D4” represents the portion of the term (namely, the prefix of the term) associated with the received length of prefix of P=8 and index consolidation program110keeps the initial 8 characters of the term. “E7H3” represents the portion of the term where a hash function was used to convert the other portion of the term into 4 hash characters. Index consolidation program110determines that the 4 hash characters are unique to the remaining portion of the received 20 character term. A separator character, such as “|” can separate the two portions of the converted index entry. In another embodiment, the received length of prefix is 6, the received length of hash value is 6, and term is 25 characters long. Index consolidation program110can convert the 25 character term, “s234ba135nv234mj469ma889n” into an index entry such as “s234ba|h469ms” where “s234ba” represents the portion of the term associated with the received length of prefix of P=6 and “h469ms” represents the portion of the term associated with the received length of hash value of H=6.

In another embodiment, index consolidation program110can determine whether to convert the term based on the number of characters included in the term. For example, index consolidation program110can receive a predefined threshold value of 10 characters (i.e., T=10), where, if a term includes 10 or more characters, index consolidation program110converts the term. If the term includes less than 10 characters, index consolidation program110does not convert the term and stores the received term in the index. In another example, the threshold value (T) is also based on the length of prefix (P) and the length of hash value (H). The sum of the length of prefix, the length of hash value, and the threshold value (i.e., P+H+T) are equal to a minimum number of characters a term can contain in order for index consolidation program110to convert the term. If the term includes fewer characters than the sum of P+H+T, index consolidation program110determines to not convert the term.

Index consolidation program110determines if the converted term exists in the index (decision step208). In the event index consolidation program110determines the converted term exists in the index (“yes” branch, step208), index consolidation program110determines if there is another term for entry into the index (decision step212). In the event index consolidation program110determines the converted term does not exist in the index (“no” branch, step208) Index consolidation program110determines to store the converted term in the index (step210).

Index consolidation program110stores the converted term in the index (step210). In this embodiment, index consolidation program110stores the converted term in index112of dictionary108. In an example, index consolidation program110stores an index entry, “s234ba|h469ms” for “s234ba135nv234mj469ma889n”, and index consolidation program110can direct any reference to “s234ba135nv234mj469ma889n” to the converted index entry. Similarly, index consolidation program110can utilize the length of prefix and the length of hash value to convert a search term received by dictionary108and match it to the converted index entry. For example, if index consolidation program110receives “s234ba135nv234mj469ma889n” as a search term, index consolidation program110can utilizes the same steps to convert the search term using the received lengths of prefix and hash values to determine if an index entry exists for the search term. If the search terms exists, index consolidation program110can identify the document associated with the search term and can send the search term to dictionary108.

Index consolidation program110determines if there is another term for entry into the index (decision step212). In the event index consolidation program110determines there is another term for entry into the index (“yes” branch, step212), index consolidation program110reverts back to step204and receives a term for entry into the index. In the event index consolidation program110determines there is no other term for entry into the index (“no” branch, step212), index consolidation program110ceases operations for consolidating entries into index112of dictionary108.

By converting terms for entry into index112, the storage size of dictionary108is reduced with the consolidated terms. With the reduced storage size of dictionary108, there is minimal impact on quality and the term search capabilities of the search engine utilizing dictionary108. As previously discussed, index consolidation program110can utilize the known lengths of prefix and hash value to convert the search term, and match the search term to any of the stored terms in dictionary108of index112. In an example, index consolidation program110can receive just a prefix as a search term and perform a wildcard search for converted terms in dictionary108containing the received prefix. There can be an instance where the length of prefix equals 0, where, as a result, the converted term is shorter but the wildcard search capability is no longer available. There can also be an instance where the length of hash value is 0, where as a result the converted term is shorter and precision is lost in the search capabilities of the search engine. Selecting the appropriate lengths of prefix and hash value provides a balance for reducing storage size of dictionary108and reducing the impact on search capabilities of the search engine utilizing dictionary108.

FIG. 3illustrates an example of an index consolidation program consolidating an entry into an index of a dictionary, in accordance with one embodiment of the present invention.

In this example, index consolidation program110receives term302to convert and store into an index of a dictionary. The term302includes over 45 characters, where the included characters are letters. Utilizing previously received lengths of prefix and hash values304, index consolidation program110converts term302to consolidated term306. The lengths of prefix and hash value304are represented by “P=8” and “H=6”. For term302, “DONAUDAM” represents the portion of the term associated with the received length of prefix of P=8, where index consolidation program110keeps the initial 8 characters of the term. “E39AC4” represents the portion of the term where a hash function was used to convert the other portion of the term into 6 hash characters. The 6 hash characters that index consolidation program110determines are unique to the remaining portion of the received term302include over 45 characters. Consolidated term302includes the “DONAUDAM” portion and the “E39AC4” portion, which index consolidation program110combines with a separator character “|”.

Term302can have a document associated with it, where index consolidation program110can index term302in the form of consolidated term306and associate the document with the index entry. In the event index consolidation program110receives term302to search in the index, index consolidation program110can determine the index entry (i.e., consolidated term306) for term302based on the lengths of prefix and hash value304and can identify the document associated with term302.

FIG. 4is a flowchart depicting operational steps of an index consolidation program for managing search terms, in accordance with an embodiment of the present invention.

Index consolidation program110receives a search term (step402). In this embodiment, a user of client device104utilizing user interface114inputs a search term which index consolidation program110receives. Index consolidation program110manages the received search term according to a type of search being performed for the received search term. In one example, a type of search is a regular search, where index consolidation program110can convert the received search term according to a length of prefix (P) and a length of hash value (H). In another example, another type of search is a wildcard search, where index consolidation program110can utilize a prefix portion of the received term, where the prefix portion of the received term is equal to a character length represented by the length of prefix (P), for the wildcard search.

Index consolidation program110determines whether to perform a wildcard search (decision step404). In the event index consolidation program110determines to perform the wildcard search (“yes” branch, step404), index consolidation program110determines if the search term contains more characters than P (decision step406). In the event index consolidation program110determines not to perform a wildcard search (“no” branch, step404), index consolidation program110determines if the search term contains more characters than P+H+T (decision step412).

Index consolidation program110determines if the search term contains more characters than P (decision step406). In the event index consolidation program110determines the search does not contain more characters than P, index consolidation program110utilizes the search term in the wildcard search (step410). Index consolidation program110utilizes the search term as received in step402, without altering the search term. In the event index consolidation program110determines the search term contains more characters than P (“yes” branch, step406), index consolidation program110determines to truncate the search term at P (step408).

Index consolidation program110truncates the search term at P (step408). In this embodiment, index consolidation program110utilizes the length of prefix (P) to truncate the search term. In one example, index consolidation program110utilizes a length of prefix, P=6 and the search term contains 10 characters, such as “DAGMNBTIOM”. Index consolidation program110can truncate the 10 character search term to 6 characters (i.e., P=6), where the search term becomes “DAGMNB”. Index consolidation program110can truncate the search term to keep the initial characters (P=6) of the search term or to keep the final characters (P=6) of the search term.

Index consolidation program110utilizes the search in the wildcard search (step410). In one embodiment, index consolidation program110can utilize the search term which contains a number of characters less than P to perform the wildcard search. In another embodiment, index consolidation program110can utilize the search term truncated at P to perform the wildcard search. The wildcard search can provide results for any entries in index112containing a portion of the search term, as dictated by the length of prefix (P).

Index consolidation program110determines if the search term contains more characters than P+H+T (decision step412). In the event index consolidation program110determines the search term contains more (i.e., exceeds) characters than P+H+T, index consolidation program110converts the search term (step414). In the event index consolidation program110determines the search term does not contain more characters than P+H+T, index consolidation program110utilizes the search term in the regular search (step416).

Index consolidation program110converts the search term (step414). In this embodiment, index consolidation program110converts the search term according to a length of prefix (P) and a length of hash value (H) that index consolidation program110utilizes to consolidate index112. In one example, index consolidation program110receives a search term containing 20 characters, such as “DOMGNIKTGBMFSDSSV8S9”. Index consolidation program110utilizes a predetermined P=5 and H=3 to convert the 20 character search term to “DOMGN|T4S”.

Index consolidation program110then utilizes the search term in the regular search (step416). The regular search identifies an index entry in index112which matches either the received search term or the converted search term according to the lengths of prefix and hash value for index112. In one embodiment, index consolidation program110can utilize the search term which contains a number of characters less than P+H+T to perform the regular search. In another embodiment, index consolidation program110can utilize the search term, converted according to the lengths of prefix and hash value, to perform the regular search.

Memory506and persistent storage508are examples of computer readable tangible storage devices. A storage device is any piece of hardware that is capable of storing information, such as, data, program code in functional form, and/or other suitable information on a temporary basis and/or permanent basis. In this embodiment, memory506includes random access memory (RAM)514and cache memory516. In general, memory506can include any suitable volatile or non-volatile computer readable storage device.

Index consolidation program110is stored in persistent storage508for execution by one or more of computer processors504via one or more memories of memory506. In this embodiment, persistent storage508includes a magnetic hard disk drive. Alternatively, or in addition to a magnetic hard disk drive, persistent storage508can include a solid state hard drive, a semiconductor storage device, read-only memory (ROM), erasable programmable read-only memory (EPROM), flash memory, or any other computer-readable storage medium that is capable of storing program instructions or digital information.

Communications unit510, in these examples, provides for communications with other data processing systems or devices, including systems and devices within or controlled by server computer102. In these examples, communications unit510includes one or more wireless network interface cards. Communications unit510may provide communications through the use of either or both physical and wireless communications links. Computer programs and processes, such as index consolidation program110, may be downloaded to persistent storage508through communications unit510, or uploaded to another system through communications unit510.

I/O interface(s)512allows for input and output of data with other devices that may be connected to server computer102. For example, I/O interface512may provide a connection to external devices518such as a keyboard, keypad, a touch screen, and/or some other suitable input device. External devices518can also include portable computer readable storage media such as, for example, thumb drives, portable optical or magnetic disks, and memory cards. Software and data used to practice embodiments of the present invention can be stored on such portable computer readable storage media and can be loaded onto persistent storage508via I/O interface(s)512. I/O interface(s)512may also connect to a display520. Display520provides a mechanism to display data to a user and may be, for example, a touch screen or a computer monitor.