Mining new words from a query log for input method editors

Described is a technology in which new words (including a phrase or set of Chinese characters) are mined from a query log. The new words may be added to (or otherwise supplement) an IME dictionary. A set of candidate queries may be selected from the log based upon market (e.g., the Chinese market) and/or by language. From this set, various filtering steps are performed to locate only new words that are frequently in used. For example, only frequent queries are kept for further processing, which may include filtering out queries based on length (e.g., less than two or greater than eight Chinese characters), and/or filtering out queries based on too many stop-words in the query. Processing may also include filtering out a query that is a substring of a larger query, or vice-versa. Also described is Pinyin-based clustering and filtering, and filtering out queries already handled in the dictionary.

BACKGROUND

An Input Method Editor (IME) is a tool provided in many computers that helps users input data into the computer system. However, the various words and language model inside the IME is fixed and cannot be used to assist users in inputting new words (including terms such as names), which appear very often.

While it is straightforward to adapt an IME to use new words, automatically finding such new and effective words regularly (e.g., daily) is a difficult problem. Such a task needs to find relevant new words, yet at the same time be automated.

SUMMARY

Briefly, various aspects of the subject matter described herein are directed towards a technology by which new words (including a phrase or set of Chinese characters) are mined from a query log. The new words may be added to (or otherwise supplement) an IME dictionary.

In one aspect, the query log may be separated by market (e.g., the Chinese market) and/or by language. From this set of queries, only frequent queries are kept for further processing. Further processing may include filtering out queries based on length (e.g., less than two or greater than eight Chinese characters), and/or filtering out queries based on too many stop-words in the query. Processing may also include filtering out a query that is a substring of a larger query, e.g., unless the substring better represents the meaning of the query, (e.g., as judged by the process). Also described is Pinyin-based clustering and filtering, and filtering out queries already handled in the dictionary.

DETAILED DESCRIPTION

Various aspects of the technology described herein are generally directed towards a mechanism/method to obtain new phrases (or words) from a query log data source for use in an input method editor (IME). While some of the examples described herein are directed towards Chinese phrases/symbols (words and characters), it is understood that these are only useful examples. The mining techniques described herein may be used with other languages, and for other purposes. As such, the present invention is not limited to any particular embodiments, aspects, concepts, structures, functionalities or examples described herein. Rather, any of the embodiments, aspects, concepts, structures, functionalities or examples described herein are non-limiting, and the present invention may be used various ways that provide benefits and advantages in computing and data mining in general.

Turning toFIG. 1, there is shown a new word mining mechanism102that obtains new words (including phrases containing two or more Chinese characters) from a query log data source104. In one implementation, selected new words are placed into the IME dictionary106for use by the IME108. Note that it is feasible to have a fixed IME dictionary with new words added to a supplemental dictionary, however it is understood thatFIG. 1is only one possible implementation. As described below, the new word mining mechanism102employs various filtering algorithms to remove any “noise” that appears in queries, as well as to not add words or the like already properly handled by the dictionary106.

In general, one example implementation automatically generates new words for a Chinese IME via seven general steps represented inFIG. 2. One suitable data source104is query log data generated from live searching, such as the Windows® Live Search Log. The scale of the Live Search log is on the order of hundreds of millions of transactions each day. One implementation uses twelve months of the query log, and updates the new words daily, with ten months of aggregated data used as training data to generate the new words and the other two months aggregated data as an evaluation dataset to test the performance.

For the Chinese IME implementation, taking the raw query log as input, at step202(FIG. 2) the query set is separated by the various markets, (e.g., queries submitted in the Chinese search market), with only the relevant market kept. A charset-based algorithm is used to filter non-Chinese queries, keeping only the Chinese queries. These queries are processed by the remaining exemplified steps ofFIG. 2that extract the new words based upon training sets.

In a next step204, queries are sorted by frequency so as to only consider sufficiently frequent queries, that is, those having a frequency higher than a threshold. The total phrase set in the current IME dictionary is also obtained; the exemplified algorithm filters out any query that is already in the current IME dictionary.

Step206is directed to filtering and separating the queries by length. More particularly, in a Chinese query implementation, the queries are classified by length to filter out queries whose length is greater than eight Chinese characters or less than two Chinese characters. Note that the upper limit of eight is used because one current Chinese IME does not support phrases longer than eight; (however this length may be modified as appropriate based upon the IME in use). The lower limit is used because queries that have only one Chinese character are, in general, ambiguous. This step is also a pre-step for step210.

In step208, stop-word filtering is performed to account for the fact that there are often one or more various stop-words in a query set (e.g., articles such as “the” in English, pronouns and prepositions, likein Chinese, and so on). A stop word list is built for such words or characters. The percentage of stop-words may be calculated by:

A threshold percentage, which may be determined by tuning, may be used to filter out any query that is less than this threshold.

Step210refers to substring filtering, which deals with removing a short query that is a substring of another, longer query. In Chinese, examples includeandandSometimes a short query results from a user being unwilling to enter whole words into a query; other times this results from a typographical error, or some different expression of user intension.

As can be readily appreciated, adding both strings and substrings of those larger strings into the set of new words may result in duplicate entries in the IME dictionary. As described herein, a substring-based filtering algorithm detects such duplicates.

One such algorithm operates by extracting the query pair (q1, q2), where q1is a substring of q2and the length of q2is equal to the length of q1plus 1. Then a scale ratio is defined as:

Two thresholds α and β are used, which may be used via tuning. For R1<α, the algorithm filters q1because q1is expected to be a substring of q2and most users are interested in q2. For R1>β, the algorithm regards q1as being a much popular query than q2, whereby it is expected to cover the main meaning of q2.

As represented by step212, further filtering is performed based upon the same pinyin (in which the pinyin results from known mechanisms for converting Chinese symbols into the Roman alphabet). More particularly, there are some queries with the same pinyin in the log; examples of which includeandThe Chinese IME attempts to extract new words for the same pinyin. To this end, one exemplified algorithm uses a query-to-pinyin model to first translate a query to pinyin, and cluster the queries with the Same pinyin together. In each cluster, the algorithm sorts the query by frequency, and keeps those with a sufficiently high frequency. In one current implementation, only up to the top two queries in each cluster are kept; in the event that the second largest frequency is relatively small, only the top one query in this cluster is kept.

Step214is performed to detect an already-correct case. More particularly, some queries may be translated correctly in the current IME engine by typing its pinyin. In step214, one algorithm implementation uses a word-to-pinyin model to first translate the query to pinyin, and then translate the pinyin to a word using a pinyin-to-word model. If the query is the same (e.g., exactly the same) as the translated word, this query is not considered for new word analysis because the current IME engine already handles it correctly.

In this manner, new words (which in Chinese correspond to two or more characters) are mined from queries submitted by users. Via various filtering, only new words that are frequently queried are mined, thereby automatically updating an IME dictionary with relevant words that are not already in the dictionary.

EXEMPLARY OPERATING ENVIRONMENT

FIG. 3illustrates an example of a suitable computing and networking environment300on which the examples ofFIGS. 1 and 2may be implemented. The computing system environment300is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment300be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment300.

With reference toFIG. 3, an exemplary system for implementing various aspects of the invention may include a general purpose computing device in the form of a computer310. Components of the computer310may include, but are not limited to, a processing unit320, a system memory330, and a system bus321that couples various system components including the system memory to the processing unit320. The system bus321may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

The system memory330includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM)331and random access memory (RAM)332. A basic input/output system333(BIOS), containing the basic routines that help to transfer information between elements within computer310, such as during start-up, is typically stored in ROM331. RAM332typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit320. By way of example, and not limitation,FIG. 3illustrates operating system334, application programs335, other program modules336and program data337.

The computer310may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only,FIG. 3illustrates a hard disk drive341that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive351that reads from or writes to a removable, nonvolatile magnetic disk352, and an optical disk drive355that reads from or writes to a removable, nonvolatile optical disk356such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive341is typically connected to the system bus321through a non-removable memory interface such as interface340, and magnetic disk drive351and optical disk drive355are typically connected to the system bus321by a removable memory interface, such as interface350.

The drives and their associated computer storage media, described above and illustrated inFIG. 3, provide storage of computer-readable instructions, data structures, program modules and other data for the computer310. InFIG. 3, for example, hard disk drive341is illustrated as storing operating system344, application programs345, other program modules346and program data347. Note that these components can either be the same as or different from operating system334, application programs335, other program modules336, and program data337. Operating system344, application programs345, other program modules346, and program data347are given different numbers herein to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer310through input devices such as a tablet, or electronic digitizer,364, a microphone363, a keyboard362and pointing device361, commonly referred to as mouse, trackball or touch pad. Other input devices not shown inFIG. 3may include a joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit320through a user input interface360that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor391or other type of display device is also connected to the system bus321via an interface, such as a video interface390. The monitor391may also be integrated with a touch-screen panel or the like. Note that the monitor and/or touch screen panel can be physically coupled to a housing in which the computing device310is incorporated, such as in a tablet-type personal computer. In addition, computers such as the computing device310may also include other peripheral output devices such as speakers395and printer396, which may be connected through an output peripheral interface394or the like.

The computer310may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer380. The remote computer380may be a personal computer a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer310, although only a memory storage device381has been illustrated inFIG. 3. The logical connections depicted inFIG. 3include one or more local area networks (LAN)371and one or more wide area networks (WAN)373, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

When used in a LAN networking environment, the computer310is connected to the LAN371through a network interface or adapter370. When used in a WAN networking environment, the computer310typically includes a modem372or other means for establishing communications over the WAN373, such as the Internet. The modem372, which may be internal or external, may be connected to the system bus321via the user input interface360or other appropriate mechanism. A wireless networking component374such as comprising an interface and antenna may be coupled through a suitable device such as an access point or peer computer to a WAN or LAN. In a networked environment, program modules depicted relative to the computer310, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation,FIG. 3illustrates remote application programs385as residing on memory device381. It may be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

An auxiliary subsystem399(e.g., for auxiliary display of content) may be connected via the user interface360to allow data such as program content, system status and event notifications to be provided to the user, even if the main portions of the computer system are in a low power state. The auxiliary subsystem399may be connected to the modem372and/or network interface370to allow communication between these systems while the main processing unit320is in a low power state.

CONCLUSION