Systems and methods for searching using queries written in a different character-set and/or language from the target pages

DESCRIPTION

All references are to the details of the embodiments of the present invention as set forth in the accompanying drawings. The same reference numbers are used in the drawings and descriptions below for the same or similar parts. The following description is provided to enable any person skilled in the art to make and use the content of the present invention. The descriptions of specific examples and uses are provided as examples only, and various modifications will be apparent to those skilled in the art. For example, although many examples have been described in the context of web pages, it should be remembered that the given examples of the present invention may be used to search for other types of documents and / or information such as books, newspapers, monthly magazines or the like. Likewise, while many examples relate to the translation of Japanese text from romaji to katakana, hiragana and / or kanji for purposes of illustration, it will be apparent to those skilled in the art that the systems and methods of the present invention can be used in any suitable translation. For example, without limitation, the examples of the present invention can be used to search for written text e.g. traditional Chinese or Korean hangul or hanja characters, based on queries received in certain other formats (e.g. pinyin or romaja). The general principles described herein can be applied to other examples and applications without departing from the scope of the present invention. Thus, the present invention is intended to be its broadest, having many alternatives, modifications, and their equivalents in accordance with the principles and features contained herein. For the sake of clarity of the description, detailed information on technical material which is known in the technical fields related to the invention has not been unnecessarily described in detail so as not to unnecessarily obscure the present invention.

A. Overview

The methods and equipment in accordance with the present invention enable the user to attach an ambiguous search query and obtain potentially unambiguous search results. In one example, the sequence of numbers received from the user of the standard telephone keypad is translated into a set of potentially corresponding alphanumeric sequences. Such potentially corresponding alphanumeric sequences are provided as input to a conventional search engine using the boolean expression "OR. In this way, the search engine is used to help limit the search results to those that are likely to be of interest to the user.

B. Architecture

Fig. 1 shows a system 100 in which the methods and apparatus of the present invention will be implemented. System 100 may include multiple client devices 110 connected to multiple servers 120 and 130 through a network 140. Network 140 may include a local area network (LAN), a wide area network (WAN), a telephone network such as a public switched telephone network (PSTN), an intranet, etc. the internet or a combination of the networks mentioned. For simplicity, two client devices 110 and three servers 120 and 130 are shown connected to the network 140. In practice, there may be more or fewer client devices and servers. As well as in some cases, client devices may perform server functions and the server may perform client functions.

- 4 ΕΡ 2,388709

Client devices 110 may include devices such as mainframes, minicomputers, personal computers, laptops, personal digital assistant (PDA) computers, or the like, that can be connected to the network 140. Client devices 110 may transmit data over the network 140 or receive data. from network 140 via cable, wireless, or optical connection.

FIG. 2 shows an exemplary client device 110 in accordance with the present invention. Client devices 110 may include a bus 210, a processor 220, main memory 230 and a read-only ROM 240, a memory device 250, an input device 260, an output device 270, and a communication interface 280.

The bus 210 may include one or more conventional rails to allow communication between parts of the client device 110. Processor 220 may include any type of conventional processor or microprocessor that interprets and executes instructions. Main memory 230 may include random access memory (RAM) or other type of dynamic memory device storing information and instructions for execution by processor 220. The ROM 240 may include a conventional ROM or other type of static storage device storing static usage information by processor 220. Storage device 250 may include a magnetic and / or optical data recording medium and a corresponding drive.

Input device 260 may include one or more conventional mechanisms for allowing a user to input data into a client device 110, such as a keyboard, mouse, stylus, voice and / or biometric recognition mechanism, etc. Output device 270 may include one or more conventional mechanisms for providing information to the user. output such as screen, printer, speaker, etc. The communication interface 280 may include a mechanism, such as a transceiver, that allows the client device 110 to communicate with other devices and / or systems. For example, communication interface 280 may include mechanisms to communicate with other devices or system over a network, such as network 140.

As will be described in detail below, the client device 110 in accordance with the present invention performs certain discovery operations. Client devices 110 may perform such operations in response to processor software execution instructions 220 contained in a computer-readable medium device such as memory 230. A computer-readable medium may be defined as one or more storage devices and / or carrier waves. Software instructions into memory 230 may be loaded from another computer readable medium, such as data storage device 250 or other devices via a communication interface 280. Software instructions in memory 230 cause processor 220 to perform the search operations described below. Alternatively, a hardware circuit may be used in place of or in conjunction with software instructions to implement the processes of the present invention. The present invention is not limited to any specific combination of hardware and software circuit.

Servers 120 and 130 can include one or more computer systems, such as mainframes, minicomputers, or personal computers that can be connected to the network 140 to allow servers 120 and 130 to communicate with client devices 110. In alternative implementations, servers 120 and 130 they may include mechanisms to connect directly to one or more client devices 110. The servers 120 and 130 may transmit data over the network 140 or receive data from the network 140 over a wired, wireless, or optical connection.

The servers may be configured similar to the configuration described above with reference to FIG. 2 of the client device 110. When implemented in accordance with the present invention, server 120 may include a search engine 125 used by devices

EP 2388709 client devices 110. The servers 130 may also store documents (or web pages) available to client devices 110.

C. Architecture operations

FIG. 3 shows a diagram with three documents that may be stored on one of the servers 130, for example.

The first document (Document 1) has two introductions - car repair and car rental - and has number 3 at the bottom. The second document (Document 2) introduces video rental. The third document (Document 3) contains three introductions - wine, champagne and bar items - and includes a link (or reference) to Document 2.

For illustrative simplicity, the documents shown in FIG. 3 contain only alphanumeric strings of information (e.g. car, repair, fault, etc.). However, it is obvious to those skilled in the art that in other situations the documents may contain other types of information, such as aural or audiovisual information.

FIG. 4a shows a conventional alphanumeric index, based on the documents shown in FIG. 3. In the first column, the index lists alphanumeric terms, and the second column lists the documents corresponding to these terms. Some terms, such as the alphanumeric term "3," refer to (e.g., appear in) only one document - in this case Document 1. Other terms, such as rental, refer to multiple documents - in this case Document 1 and 2.

In FIG. 4b shows how a conventional search engine, such as engine 125, would use the index shown in FIG. 4a to provide alphanumeric query search results. The alphanumeric query may be generated using a conventional technique. For purposes of illustration, FIG. 4b, two alphanumeric queries were given: car and blame. During conventional search, search engine 125 receives an alphanumeric query, such as car (step 410), and uses the alphanumeric index to determine which documents correspond to that query (step 420). In the example provided, the conventional search engine 125 should use the index shown in FIG. 4a to specify that “the car corresponds to Document 1 and should present to the user Document 1 (or a reference to it) as a search result. Likewise, the conventional search engine should determine that "the fault corresponds to Document 3, and should present Document 3 (or a reference to it) to the user (step 430).

In FIG. 5a is a flowchart in accordance with the present invention for a preferred technique for providing results in response to a numerical search query based on the documents and index shown in FIG. 3 and FIG. 4a respectively. For ease of display, in FIG. 5a shows a particular numerical query processing technique based on standard telephone set mapping, but it will be apparent to those skilled in the art that other techniques in accordance with the present invention may be used.

In step 510, the sequence 227 (corresponding to the numeric components 2, 2, and "7) was obtained from the user. In step 520, information is obtained as to how the numerical components map letters. Assuming the user has entered information from the standard telephone keypad, this mapping information is shown in FIG. 5b. As shown in FIG. 5b, each letter a, b and c is mapped to 1, each letter p, q, r and s is mapped to number 7 and so on.

In step 530, using the mapping information, translation of the sequence 227 into potential alphanumeric counterparts is performed. Based on the information shown in FIG. 5b, there are 36 possible letter combinations corresponding to the sequence 227

- 6ΕΡ 2,388709 including the following: aap, bap, cap, abp, bbp, ... bar ... car ... ccs. If numbers are included in the possible combinations (e.g., aa7) then there will be 80 possible combinations. Rather than generating all possible alphanumeric matches, you may want to restrict the matches generated based on some lexicon. For example, it may be required to generate only the alphanumeric matches that appear in a dictionary, search engine book from previous search queries, etc; or otherwise reduce the alphanumeric equivalents by using known statistical techniques (e.g. the probability of certain words occurring together).

In step 540, such alphanumeric equivalents are provided as entered into the conventional search engine, such as described with reference to FIG. 4a and 4b with the logical command "OR. For example, the search query supplied to the search engine might be aap OR bap OR cap OR abp ... OR bar ... OR car. While all possible alphanumeric matches can be entered into the search engine, a subset may instead be used using conventional techniques to eliminate possibly unintended matches. For example, you can generate a narrower list of possible combinations by using techniques that retrieve probability information about the use of letters or words: you can ignore combinations starting with qt, but include (and favor) combinations that start with qu.

In step 550, search results are obtained from the search engine. Since terms such as aap and abp do not appear in the search engine index, they are effectively ignored. In fact, the only terms found in the index shown in FIG. 4b are car and bar, and therefore they will be sent as the only search results with Reference Documents 1 and 3. In step 560 such search results are presented to the user. The search results may be presented in the same order as provided by the search engine, or may be rearranged according to the situation such as the user's language. Assuming that the user is only interested in documents containing the term 'bar, he should receive the required result (Document 3) in addition to the required result (Document 1). You can accept this price, however, to the benefit of the user who only needs to press three buttons to form a search query.

In FIG. 6 shows another flowchart of the preferred technique in accordance with the present invention to provide results in response to a numerical search query based on the documents and index shown in FIG. 3 and FIG. 4a respectively. The diagram below shows how increasing the size of the sequence obtained can help to limit the search results to what the user expects. For ease of description, in FIG. 6 again a particular numerical query processing technique based on standard telephone set mapping is presented, but it will be apparent to those skilled in the art that other techniques in accordance with the present invention may be used.

In step 610, the sequence 227 48367 (corresponding to the numeric components 2, 2, 7, 4, 8, 3, 6, 7) was obtained from the user. For clarity, sequence 227 will be referred to as "digital word, and entire sequence 227 48367 will be referred to as" digital phrase. Possible alphanumeric equivalents of a digital word will be called "letter word" and possible equivalents of a digital phrase will be called "letter phrases."

In step 620, information is obtained on how the numerical components map letters. Assuming that the same mapping information is used as shown in FIG. 5b, in step 630 the numerical phrase 227 48367 is translated into potentially corresponding letter phrases. Based on the information shown in FIG. 5b, there are 11664 possible letter phrases corresponding to the sequence 227 48367.

In step 640, letter phrases are provided as inputs to the conventional search engine as described with reference to FIG. 4a and 4b with a logical command

- 7 - EP 2388709 "OR (or). For example, the search query supplied to the search engine might be 'aap gtdmp' OR 'aap htdmp' ... OR 'bar items' ... OR 'car items'. While all possible letter phrases can be entered into the search engine, a subset may be used instead using conventional techniques for eliminating letter phrases that are not likely to be intentional.

In step 650, search results are obtained from the search engine. Since many search engines are designed to rank high in those documents that contain the exact phrases you searched for, Document 3 should be the highest-ranked search result (i.e. because it contains the exact phrase bar items). No other document in this example contains one or the other letter phrases generated in step 620. In addition, many search engines limit (or eliminate) search results that contain individual parts of the phrase, rather than the entire phrase. For example, Document 1 should be restricted or eliminated because it contains the letters of the word car that match the first part of the letter phrase, but does not contain any letter from the word corresponding to the second part of the letter phrase. Ultimately, letter phrases such as aap htdmp are effectively ignored because they do not contain the letters of words that are in the search engine index.

In step 660, the search results are presented to the user. This example shows that the first result shown to the user should be Document 3 that most closely matches the user's query (query). The entire Document 1 can be eliminated as it does not contain any of the possible letter phrases. In this way, the user obtains the most relevant search results.

Although the descriptions given above with reference to FIG. 5 and 6 relate to obtaining numerical information and mapping it to alphanumeric information, it will be apparent to those skilled in the art that other applications are possible in accordance with the present invention. For example, instead of receiving a sequence of numbers corresponding to the pressed buttons by the user, the resulting sequences may contain the first letters corresponding to the buttons pressed by the user. In other words, instead of getting 227, the resulting sequence may be aap. In accordance with the present invention, the corresponding letter sequences generated in steps 530 or 630 should be different letter sequences (e.g., bar) that correspond to aap. In fact, the sequence may contain aural, audiovisual, or any other type of information component.

Regardless of the form of the obtained sequence, it is generally preferable to obtain the sequence to be translated in order to obtain the sequence corresponding to the format in which the information is stored in the index of the search engine. For example, if the search engine index has been stored in an alphanumeric format, the resulting sequence should be translated into an alphanumeric sequence.

Moreover, it is generally preferred that the mapping technique used to translate the obtained sequence of information components is the same technique as is used in the user equipment to map user input to device generated information. However, there may be cases where it is preferable to use a mapping technique different from that used at user input. Examples of the present invention may also enable users to perform a keyboard search with a language different from the target language. For example, a web page containing Japanese text might be written in kanji when a user tries to search for that page having only access to a standard Latin-based ASCII keyboard (or telephone).

FIG. 7 shows a method for making such a search. As shown in FIG. 7, the user enters a query using a standard input device (e.g. ASCII keyboard, telephone set, etc.) and submits the query to the search engine. The query may be entered in a character set (e.g. romaji) that differs from the character set used in some of the corresponding documents (e.g. kanji). The search engine receives the query (block 702),

EP 2388709 translates into the appropriate form (block 704) and searches for documents corresponding to the translated query using e.g. conventional search techniques (block 706). The search engine then lists the corresponding documents (and / or copies of the documents themselves) to the user (block 708). For example, the results should return to the user similarly as described above with respect to FIG. 6.

As shown in FIG. 7, the user's query is preferably translated at the search engine server as opposed to the client, freeing the client from obtaining specialized translation software. However, it will be apparent that in other examples, some or all of the translations may be performed at the client device. Additionally, in some examples, the query may be entered from a device such as a telephone keypad. In such cases, the initial numeric query must first be changed to alphanumeric form (e.g. romaji) using the mapping techniques described above with respect to FIG. 5 and 6, which includes, for example, the use of lexicon and / or probability techniques to discard low probability mapping (e.g. mapping involving letter combinations not present in romaji). After alphanumeric translation of the query is obtained, the remaining steps shown in FIG. 7 (i.e., 704, 706, and 708).

Translation of a query from one character set to another character set, or from a language to another language (i.e., block 704 in FIG. 7) can be performed in a number of ways. One technique used is a conventional static word meaning or translation dictionary to map each term in the query to the corresponding term in the target language or character set. The problem with this approach, however, is that you often get inaccurate results because words are often ambiguous and queries will often be too short to provide appropriate contextual clues to resolve such ambiguity. For example, the word "bank" may refer to a river bank, a financial institution or an airplane maneuver, making it difficult to accurately translate theoretically. Furthermore, if the dictionary is not large enough and / or frequently updated, it may not contain all the terms that the search engine may encounter, such as seldom used words, jargon, idioms, proper names, and the like. The examples of the present invention can be used to circumvent or alleviate some or all of the given problems by using a probabilistic dictionary (using probability) to translate query terms from one language or set of characters (e.g. ASCII) to another (e.g. kanji). In a preferred example, the probabilistic dictionary maps one term set to another term set and associates the probability with each of the mapping results. For convenience, "term or" token will refer to words, phrases, and / or (more generally) a sequence of one or more characters that may contain spaces.

In FIG. 8 shows an example of a probabilistic dictionary 800 as described above. The exemplary probabilistic dictionary 800 shown in FIG. 8 maps words written in romaji (a representation of Japanese in Latin) to words written in kanji (a set of Japanese characters based on ideograms different from the Latin alphabet). To facilitate explanation, in FIG. 8 romaji terms are presented as <term>_romaji and kanji terms as <term> kanji. It is clear that the actual romaji and kanji terms will be used in the current romaji-kanji dictionary instead of the English translations shown in FIG. 8. It is evident that the table FIG. 8 is provided to aid in explaining the embodiments of the present invention, and does not show the actual characters and meanings of the Japanese text.

The dictionary 800 shows the entries 808, 810, 812, 814 for the various terms romaji 802. The dictionary also includes a potential representation of each term in kanji 804 together with a corresponding probability 806 of each of the proposed terms being correct. For example, in romaji, the term bank can be mapped to kanji for a steep edge "steep slope with a probability of 0.3, to a term for

- 9 EP 2388709 financial institution "financial institution with a probability of 0.4, and an airplane maneuver with a probability of 0.2 With a probability of 0.1 for the term other" other, which is a simple generic method allowing each term to be mapped to terms not found in the dictionary.

Again, it is evident that the example shown in FIG. 8 is constructed to show that a given term (e.g., the word bank) provided in the first character set or language can be mapped to more than one term in a different character set or language. One skilled in the art will know, although for the sake of clarity, this particular example is shown in FIG. 8 the principle of using English words and meanings, the actual representation of the word in romaji, for example, "bank may not be ambiguous, as in the case of its English counterpart (e.g. there may be no ambiguity in romaji between the word for a financial institution and the word for an airplane maneuver). It will also be apparent that for ease of explanation, the dictionary shown in FIG. 8 has been simplified in other respects as well. For example, an actual probabilistic dictionary may contain many more potential mappings of each term, or it may only contain mappings exceeding a predetermined probability threshold.

The preferred examples of the present invention use such a probabilistic dictionary to translate queries expressed in one language and / or character set into another language and / or character set, thereby enabling users to find documents written in a different character set and / or language than the original query. For example, if a user enters a query for cars in romaji, then a probabilistic dictionary will be used to map the romaji term for cars cars, for example the term cars in kanji. This way, users can find documents related to their queries, even if the character set for the query (e.g. romaji) and the character set for the matching documents (e.g. kanji) are not the same. Note that in this particular example, the actual query language is not changed (both romaji and kanji are used to represent Japanese), only the character encoding.

In yet another example, the term tired "tired in ASCII in English can be mapped with the term" miide ​​in German using the Latin 1 character encoding, as the umlaut character does not exist in ASCII. Note that in this example, the dictionary provides both translation to another language (English to German) and translation to another character encoding (ASCII to Latin 1).

In the preferred examples, the mapping dictionary described above is built automatically using information available on the web in conjunction with statistical techniques. Preferred examples use parallel adapted bilingual bodies such as anchored text written in different languages ​​and / or character sets to obtain accurate translations. Using this data, the preferred embodiments can create a dictionary of potential word mappings. This can be done, for example, by simply counting the number of occurrences of a token in Si (source language) at the same time as the Tj token (target language) in matched text pairs (e.g. anchors, sentences, etc.). And it should be appreciated that any suitable technique can be used.

In the absence of sufficiently large and correctly matched datasets, this method can generate a relatively ambiguous many-to-many mapping. So for example it can be determined that Si should only be mapped to T2, T3, T7, and Ts with a certain probability. However, this is acceptable and, as described in more detail above, in some examples an additional refresh is performed to increase the corresponding similarity of each of the mappings, e.g. by checking the user's previous inquiries, the user's selection of items on the results page, and / or other similar.

FIG. 9 illustrates the use of parallel anchored text to create a probabilistic dictionary. Anchored text means text that is linked between web pages by a hyperlink (or places on a specified web page). On

-10 EP 2388709 example in HTML (Hypertext Markup Language), command: <A href = http: // www. abc.com> Banks and Savings and Loans </A> displays the text Banks and Savings and Loans in the form of a hyperlink pointing to the website at http://www.abc.com. We call Banks and Savings and Loans text "Anchor Text" and usually gives a short description of the website it points to (e.g. www.abc.com). In fact, anchor text (with a link) often provides a more accurate description of a web page than the page itself, and can therefore be particularly useful in determining the nature of the referenced web page. In addition, the use of the word and the distribution in anchor text is often closer to the spirit and length of that found in user queries. There is also the case that multiple anchors pointing to a given page will contain the same or very similar text. For example, anchors pointing to www.google.com will often simply point to "Google, or at least use the term together with other text. So by examining all the anchors from www.google.com, e.g. in katakana, the translation to katakana for Google can be deduced with a sufficiently high degree of certainty by looking at the term that appears most frequently (perhaps after discarding predetermined low-content anchors, such as only telling you to click "click here"). The preferred examples of the present invention use these anchor text characteristics to ensure accurate translations.

With reference to FIG. 9, upon receiving a query containing a term written in the first character set (e.g., ASCII) (block 902), the server identifies the set of anchored texts where the given term occurs (block 904). For example, the server can query the index of all known anchors to determine which anchors contain the given term. The webpages pointed to by the anchors are then identified (block 906), as are the anchors in the target language or target character set (e.g., hiragana, katakana, and / or kanji) that point to the webpages (block 908). The system will now have two document sets (where the anchor text is considered to be the document form). Distribution of the inquiry deadline in one document (e.g. anchors containing the original ASCII query) is then used to identify the most likely candidates for the translated phrase of a different set of documents (e.g. parallel anchors). The statistics can be computed considering the frequency with which the term occurs in the anchor texts, and the resulting statistics can be used to determine the relative frequency or probability of terms found in the anchor text as a valid translation of the original query (block 910). For a multi-word query, the process described above may be repeated for each word, or the entire query may be considered as a single term, or several other word groupings may be used. For example, when the query is big houses, a dictionary of possible translations can be constructed by finding a matched anchor text containing the given phrase (or at least words from the given phrase). Similarly, if the query contained more than two terms, experiments to determine the appropriate mapping could be constructed by retrieving the appropriate subset of the query terms and generating results for those terms.

The benefit of performing translation as shown in FIG. 9 is that the translation system requires not only prior knowledge of the mapping between terms in one language or character set and those in the target set. Instead, the mapping may be determined dynamically based on the data corpus available for statistical analysis. Thus, it is possible to discover the exact translations of slang terms, idioms, proper names and the like without the effort and cost (e.g., of linguistic analysis and research) of maintaining a conventional static dictionary.

An example depicting the previously described translation techniques is described with reference to FIG. 10-12. This example assumes that the user has entered a query with the term house (home) and wants the search results in Spanish (or

-11- EP2388709 simplifying the translation of the query term). The server will then try to translate the English term house into its Spanish equivalent.

With reference to FIG. 10, many websites 959, 961, 963, 965 are linked via anchor texts 960, 962, 964, 966 to pages 972 and 974. Some pages and the associated anchor text are in English (i.e. pages 959a-e and 963a -t) and some are in Spanish (i.e. pages 961a-e and 965a-j). The server first locates all anchors using the term house. Such anchors can be located, for example, by searching an index of anchored texts stored on the server. Using such an index, the server can first find five anchors 960 using the phrase big house and then point to the website 972. Then the server means that there are also found five target language (Spanish) anchors 962 also pointing to the page 972. For example, such anchors in the example of FIG. 10, contain the text casa granda (big house). Anchors that are linked to the same page (such as 960 anchors and 962 anchors) or to pages that have a predefined relationship are named "Matched" where, more generally, the match usually refers to the equivalence (or probable equivalence) of the matched terms.

In FIG. 11A shows the frequency with which each target language term appears in target language anchors 962. As shown in FIG. 11A, the terms casa and grande are each used five times (i.e., once in each 962 anchor). Thus, out of a total of ten terms found in target 962 anchors (i.e. two terms per anchor in all five anchors), the term casa is for half, and the term grande is for the other half. Thus, as shown in FIG. 11A, at this point the term house should be mapped to either casa or granda with the same frequency, since both terms occur with the same frequency.

However, as shown in FIG. 10 the system also finds twenty English anchors 964 containing the term house pointing to page 974, followed by Spanish anchors 966 containing the term casa also pointing to page 974. As shown in FIG. 11B, house will be mapped with a casa with a probability of 0.75 (i.e. 15/20), with a grand probability of 0.25 (i.e. 5/20). Such probabilities are calculated by dividing the total number of occurrences of each term in the target language anchors (i.e. fifteen for casa) by the total number of terms - including repetitions - in the target language anchors (i.e. twenty terms: ten in anchors 962, and ten contained in anchors 964). Alternatively, or in addition, other techniques may be used to calculate and / or refine the probability of a given translation or mapping. For example, those skilled in the art will recognize that any of a number of well-known techniques can be used to reduce error of variance or estimate probability, such as Bayesian methods, histogram smoothing, nonparametric kernel smoothing, shrinkage truncated estimators, and other estimation techniques. .

If more anchor texts are available, the probabilities can be adjusted even further. For example, the final probability distribution may be similar to that shown in FIG. 12, in which "house is mapped with a relatively high probability to casa and its diminutive casita, and with a lower probability to casino and mansion (the Spanish word for mansion) and with negligible probability to terms such as grande. Thus, a correct translation - as well as the identification of probable synonyms - can be obtained without the knowledge of the languages ​​and / or character set being translated.

After the query terms have been translated, the server then starts searching using the translation. For example, when a user entered a query in romaji hotels in Kyoto (Kyoto hotels), the techniques described above should be used to allow the server to obtain katakana, hiragana and kanji of the query, perform a search using these

EP 2,388,709 queries, and then present the combined results for each query form to the user on the appropriate user interface.

Note that the example described in FIG. 10-12 is provided for illustrative purposes only and is not intended to be limiting, and many variations can be made to the methodology described. For example, various statistical techniques may be used to obtain the probability and / or modifications should be made to the basic techniques described above. Likewise, it should be noted that the translation technique described above can be simply applied to translate words or phrases entered by users and need not be used for internet searches or the creation of a probabilistic dictionary as well. Moreover, while the preceding example describes a translation process that occurs upon receipt of a user query, it should be noted that in other examples the mapping process may be performed prior to receiving a user query. Such pre-mappings should be recorded in a dictionary as described in FIG. 8, which can then be used to translate user requests as they are received. Ultimately, it should be understood that a text other than the matching anchor text may be used to perform the translation. For example, matched sentences or other data can be used in a similar way. Many countries have more than one official or recognized language, and newspapers and periodicals will often contain the same article written in these languages. Such parallel translations can be used in the same way as the previously described anchor text for preparing probabilistic word translation dictionaries.

Thus, the examples advantageously facilitate users to enter search queries and / or a translation query in a convenient manner (e.g. using an ASCII keyboard) and provide accurate and automatic translation and searching. In some examples, additional refinement of the basic model described above can be performed. For example, in some examples, preferences (weights) may be given to anchors that contain a number of terms similar to the number of terms in the original query and / or other matched anchors. For example, in the system shown in FIG. 10, you can give preference to anchors pointing to page 974 because, like the original query, each contains a single term. Likewise, if an anchor containing la casa grande also points to page 972, its weight may be reduced by an appropriate factor as it contains more terms (i.e. 3) than the anchors to which it fits. This weighting scheme may reflect the probability calculations shown in FIG. 11B by multiplying the frequencies of the terms associated with these anchors by a suitable factor.

The translation process described above can also be used to improve the performance of the search itself. For example, a probabilistic dictionary may be used to extend the current query to include, e.g., various translations and synonyms of the original query terms. By extending the queries before searching for the document, you can perform a simultaneous search for the same "terms, increasing the likelihood that the search will contain the information the user is searching for. Alternatively or additionally, a probabilistic dictionary may be used to supplement the normal document indexing process by providing a term extension to the document. For example, terms found in a document can be supplemented in the document's index with translations from a probabilistic dictionary thereby increasing the likelihood that the document will be located even in searches where exactly the same terms as found in the original document are not used.

A problem can arise when using the translation techniques described above, due to a small amount of data (data scattering) (e.g. not enough anchors to explicitly specify that casa is mapped to house), or lack of diversity (e.g. all anchors give the same thing) ), the system cannot obtain a sufficiently accurate probabilistic mapping. Thus, in some examples, the probabilistic mapping may be further improved

-13 - EP 2388709 by checking user behavior. A number of techniques are described below to illustrate the problem.

For example, we're assuming again that the server wants to translate for house. We assume, however, that the only anchor text that can be found contains the phrase big house or the phrase casa grande. Due to the lack of variety in anchored text, a probabilistic dictionary may appear with the following mapping:

house + house, with a probability of 0.5 house + grand, with a probability of 0.5 big + house, with a probability of 0.5 big + house, with a probability of 0.5 grand + house, with a probability of 0.5 grand + big, with a probability of 0.5 house + house, with a probability of 0.5 casa + big, with a probability of 0.5

Imagine the user is now submitting a query for casa to a search engine. At this point, the search engine lists pages that contain the term casa as well as a mix of N results that contain only house and M results that contain only big. In practice, N and M can be matched to take into account the supporting mapping probabilities, such that the relatively improbable mappings produce fewer results displayed. If it was found that users clicked on results containing only house ten times more than results containing only big, then the probability of the mapping should, for example, be adjusted as follows:

house + house, with probability 0.9 house + house, with probability 0.1 big + house, with probability 0.1 house 4 grand, with probability 0.9 grand + house, with probability 0.1 grand + big, with probability 0.9 house + house, with probability 0.9 casa + big, with a probability of 0.1

Note that the actual numbers may be dependent on many other factors, such as the number of users targeted, the number of clicks on pages containing both terms, the placement of results containing the terms in question between the result set, and / or others. Also note that the adjusted probabilities in this example (ie 0.1 and 0.9) are provided for guidance only. As will be appreciated by those skilled in the art, the actual weights given to user feedback, such as described above, should be implemented in any suitable manner.

It should also be noted that the previous example has been simplified to help explain the use of the feedback. For example, in some systems it is possible to use information obtained from other translations as an aid to the resulting translation.For example, in the example just presented, even though the term house only appears in the anchor text as big house, it may still be possible to indicate that house is more likely to be it maps from casa rather than grande. For example, if it has already been determined that big is mapped with granda with a high probability or with more than a sufficiently large data set (and assuming that the anchor text is the only

-14- ΕΡ2388709 consists of a synonym list), then the house-to-casa mapping may still be given a preference for house-to-grande mapping, even if the house or "casa anchors were not convincing."

The accuracy of translation and / or the relevance of search results can also be improved by checking the user's query history. For example, in many cases the system knows (e.g. on the basis of cookies or information stored in the user's account on the server) the previous queries entered by that user. Such historical data can be used to rank the possible significance of inquiries from a given user and a potentially unambiguous "bank of fishing-related to flying-related inquiries". So this process can be used to narrow down the set of possible translations. In some embodiments, the system may suggest them by displaying them in conjunction with a message such as "Did you mean to search for X" on the user interface (where "X represents a supposed translation preference) while potentially displaying on the first page, the results produce a small number of results for each of the possible transformations. When the user selects one of the alternatives suggested by the displayed question "Do you want to search ....... or one of the results presented on the results page, then the system obtains additional information regarding similar word / word translations of the query, as well as the probable search base for the user. . Both signals can then be used by the system to update the probability score of the term mapping (e.g. in the probabilistic dictionary) both in the general case as well as in the user-specific case.

D. Summary

As described in detail above, methods and systems in accordance with the present invention may be used to provide search results in response to ambiguous search queries and / or to translate terms into another character set and / or languages. Various translation techniques as well as search and systems are described. However, it should be kept in mind that the foregoing description is provided for illustrative purposes and that many modifications and variations are possible in light of the above knowledge or as a result of practicing the present invention. For example, although the description provided is based on a client-server architecture, it will be apparent to those skilled in the art that a peer-to-peer architecture may be used in accordance with the present invention. Moreover, although the described implementation includes software, the invention may be implemented as a combination of hardware and software, or as hardware only. Furthermore, while aspects of the present invention have been described as being written to memory, it will be apparent to those skilled in the art that all aspects may be recorded on all computer readable media such as mass storage devices such as hard drives, floppy disks or CD-ROM; Internet carrier waves or other forms of RAM or ROM. The scope of the present invention is therefore defined in the appended claims and their equivalents.

Proxy:

KANCE'J \ P! A PPAW \ O ° ATENTIAL BELLEPAT

Iiabeiu Szych ulska-Hawranek ul. Słowackiego 44, 37-700 Prz ^ n ^ ślątel (0t6) 7 ^ 2-37-77 fax: (016) Ó75-92-87 mobile phone (0608) 503-081 e-man bellepat@cp.pl NIP: 795-207-16-72 REGON: 1803505: 6

ITEM mgr Izabt

<img file="PL2388709T3_D0001.tif" />

RENT uiska-Hmrmtk u 3162

EP 2388709