Systems and methods for searching using queries written in a different character-set and/or language from the target pages
Abstract
A method comprising: the identification (904) of a first set of anchor text written in a first format and containing a given term; the identification (906) of a set of documents to which the first set of anchor text points; the identification (908) of a second set of anchor text written in a second format, and pointing to the identified set of documents; the analysis (910) of the second set of anchor text to determine that a representation of the given term in the first format corresponds to the representation of a given term in the second format.

Term
Term ended
Projected expiry passed 13 September 2024, 2 years ago.
- Priority
- Filed
- Published
- Projected expiry
- Today
17 claims: 2 independent, 15 dependent
- 1ES 2 323 786 T3 REIVINDICACIONES 1. Un método que comprende:la identificación (904) de un primer conjunto de texto de anclaje escrito en un primer formato y conteniendo un término dado;la identificación (906) de un conjunto de documentos hacia los cuales apunta el primer conjunto de texto de anclaje;la identificación (908) de un segundo conjunto de texto de anclaje escrito en un segundo formato, y apuntando al conjunto identificado de documentos;el análisis (910) del segundo conjunto de texto de anclaje para determinar que una representación del término dado en el primer formato se corresponde a la representación de un término dado en el segundo formato.
- 2El método de la reivindicación 1, en donde el primer formato comprende un primer conjunto de caracteres, y el segundo formato comprende un segundo conjunto de caracteres.
- 3El método de la reivindicación 1, en donde el primer formato comprende un primer idioma y el segundo formato comprende un segundo idioma.
- 4El método de la reivindicación 1, en donde el análisis del segundo conjunto del texto de anclaje incluye la identificación de un término que aparece en el segundo conjunto de texto de anclaje, y la designación del termino más frecuente como la representación del termino dado en el segundo formato.
- 5El método de la reivindicación 1, en donde el análisis del segundo conjunto del texto de anclaje comprende:calcular una probabilidad de que el termino dado corresponde a un término en el segundo conjunto de texto de anclaje.
- 6El método de la reivindicación 5, en donde la probabilidad se obtiene utilizando al menos unos medios Bayesianos, alisamiento de histogramas, alisamiento Kernel, y estimadores de contracción.
- 7El método de la reivindicación 5, en donde la probabilidad de que un termino dado corresponda a un término en el segundo conjunto del texto de anclaje se obtiene por la división del numero de presencias del término en el segundo conjunto del texto de anclaje por el numero total de presencias de todos los términos en el segundo conjunto del texto de anclaje.
- 8El método de la reivindicación 1, en donde el análisis del segundo conjunto del texto de anclaje comprende:el cálculo de un probabilidad de que el termino dado se corresponda con cada termino en el segundo conjunto del texto de anclaje.
- 9El método de la reivindicación 1, en donde el análisis del segundo conjunto de texto de anclaje comprende:la identificación de un término que aparece más frecuentemente en el segundo conjunto del texto de anclaje.
- 10El método de la reivindicación 2, en donde se selecciona el primer formato a partir del grupo que comprende:formato, romaja y pinyin;y en donde el segundo conjunto de caracteres se selecciona a partir del grupo que comprende: katakana, haragana, kanji, hangul, hanja, y los caracteres chinos tradicionales.
- 11El método de la reivindicación 1, en donde los documentos comprenden páginas Web.
- 12El método de la reivindicación 1, que comprende además:la obtención de una pregunta o consulta escrita en el primer formato y conteniendo el término dado;traducción de la pregunta o consulta en el segundo formato basándose al menos en parte del mencionado paso de análisis;búsqueda de una base de datos para la información escrita en el segundo formato que sea sensible a la pregunta o consulta traducida.
- 13El método de la reivindicación 12, en donde las etapas se ejecutan en el orden expuesto. ES 2 323 786 T3
- 14Un producto de un programa de ordenador incluido en un medio legible por ordenador, en donde el programa de ordenado incluye instrucciones, las cuales se ejecutan mediante un sistema por ordenador, que son operativas para hacer que el sistema por ordenador ejecute acciones, que comprenden:la identificación (904) de un primer conjunto de texto de anclaje escrito en un primer formato y conteniendo un término dado;la identificación (906) de un conjunto de páginas Web a las cuales apunta el primer conjunto de texto de anclaje;la identificación (908) de un segundo conjunto de texto de anclaje escrito en un segundo formato, y apuntando a un conjunto identificado de páginas Web;determinación de la probabilidad de que una representación de un término dado en el primer formato se corresponda a una representación de un término dado en el segundo formato.
- 15El producto del programa de ordenador de la reivindicación 14, que incluye además instrucciones, las cuales al ejecutarse por el sistema de ordenador, son operativas para provocar que el sistema de ordenador ejecute acciones que comprenden:modificar la probabilidad de que una representación del termino dado en el primer formato se corresponda con una representación del término dado en el segundo formato, basándose al menos en parte en un análisis de la selección del usuario de los resultados de la búsqueda.
- 16El producto del programa de ordenador de la reivindicación 14, que incluye además instrucciones, las cuales al ser ejecutadas por el sistema de ordenador son operativas para hacer que el sistema de ordenador ejecute acciones, que comprenden:modificar la probabilidad de que una representación del término dado en el primer formato se corresponda con una representación del término dado en el segundo formato, basándose al menos en parte, en un análisis de las preguntas o consultas previas del usuario.
- 17El producto del programa de ordenador de la reivindicación 14, en donde la probabilidad se determina al menos en parte, utilizando al menos uno de los métodos Bayesianos, alisamiento del histograma, alisamiento kernel, y estimadores de contracción.
Independent claims17
106 paragraphs in 6 sections, as filed
ES 2 323 786 T3
DESCRIPTION
Systems and methods for searching using questions written in a different character set and / or language than the target pages.
Background of the invention
1. Field of the invention
The present invention is generally related to information search and retrieval. More specifically, systems and methods for searching using questions or queries that are written in a character set or language that is different from the character set or language of at least some of the documents being searched are described.
2. Description of Related Art
Most search engines operate under the assumption that the end user is entering search questions or queries, using a conventional keyboard, where input of alphanumeric strings is not difficult. However, as small devices become common, this assumption is not always valid. For example, users can query search engines using radio telephones that support the standard WAP (Radio Application Protocol) system. Devices such as radio telephones typically have a data entry interface, where a particular action by the user (eg, pressing a key) may correspond to more than one alphanumeric character. The detailed description of the WAP architecture is available at http://wwwl.wapforum.org/tech/documents/SPECWAPArch-19980439.pdf ("WAP 100 Radio Application Protocol Architecture Specification").
In the usual case, the WAP user navigates to the search query page, and is presented with a format in which his question or search query is entered. With conventional methods, the user is required to press multiple keys to select a particular letter. On the keyboard of a standard telephone, for example, the user would select the letter “b” by pressing the “2” key twice, or he would select the letter “s” by pressing the “7” key four times. . Consequently, to enter a question or query for "ben smith", the user would normally need to enter the following string of keystrokes:
223366077776444844, which would correspond to the letters according to the following:
-> b
-> e
-> n
-> space
7777 -> s
-> m
444 -> i
-> t
-> h
After the user has entered their question or search query, the search engine receives the word or words from the user, and will proceed in the same way as if it received the question or query from a desktop browser, where the user I would have used a conventional keyboard.
As can be seen from the previous example, this form of data entry is inefficient because it requires eighteen keystrokes to be able to enter the nine alphanumeric characters (including space) corresponding to “ben smith”.
Similar difficulties can arise when typing questions or queries with the use of non-target language keyboards. For example, Japanese text can be expressed using a variety of different character sets, including the characters lazy, katakana, and kanji, none of which can be easily entered using a typical ASCII keyboard, which is based on the Roman alphabet. In such a situation, the user will make frequent use of a word processor such as Ichitaro, produced by JustSystem Corporation of Tokushima City, Japan, which is capable of converting written text into romaji (a phonetic representation
ES 2 323 786 T3 of the Roman alphabet from Japanese) to katakana, haragana, and kanji. Using the word processor, the user can type a question or query in romaji, and then cut and paste the translated text from the word processor screen to a search box in the browser. A drawback of this solution is that it can be relatively time consuming and tedious, requiring access to a copy of the word processor, which may not be feasible due to cost and / or memory limitations.
The need therefore remains for methods and apparatus to provide relevant search results in response to an efficient search query or question.
Document EP-A-597611 discloses a document analysis system that manages documents in two formats.
The invention is set forth in claim 1.
The methods and apparatus described extensively herein provide relevant search results in response to an ambiguous search query or question. Consistent with the invention, said method includes receiving a sequence of ambiguous information components by the user. The method obtains mapping information that corresponds from ambiguous information components to less ambiguous information components. This mapping information is used to translate the sequence of ambiguous information components into one or more corresponding sequences of less ambiguous information components. One or more of these less ambiguous information sequences is provided as input to a search engine. Search results are retrieved from the search engine and presented to the user.
In addition to this, systems and methods for conducting searches using questions or queries that are expressed in character sets or languages that are different from the character set or languages of at least some of the documents in which the search has to be performed are exposed. The embodiments of the present invention allow the user to type the questions or queries using standard input devices (for example, ASCII keyboards), where the queries translated into relevant formats are obtained on a server (for example, translate a question or query written in romaji to katakana, haragana, and / or kanji), and be able to receive search results based on the converted formats.
It will be appreciated that the present invention may be implemented in a number of ways, including as a process, an apparatus, a system, a device, a method, or a computer-readable medium, such as a computer-readable storage medium, carrier wave , or a computer network where program instructions are sent through optical or electronic communication lines. Various embodiments of the invention are described below.
In one embodiment, a method is described for automatically translating the terms of the question or query from one language and / or character set to another. A first set of anchor text containing a given question or query term is like a set of documents (for example, Web pages) to which the anchor text points. A second set of anchor text, written in a second format and pointing to the same set of documents, is thus identified. The second set of anchor text is then analyzed, in order to obtain a probability where a representation of the given term of the question or query in the first format may correspond to a representation of the given term of the question or query in the second format.
In yet another embodiment, a question or query provided in a first language or character set is translated into a second language or character set, by comparing the anchor text that contains one or more of the terms of the question or query and that are written in the first language or character set with the anchor text that corresponds to the first anchor text and that is written in the second language or character set.
In another embodiment, a computer program product is provided for translating a term written in a first format to a second format. The product of the computer program is operative to cause a computer system to identify the aligned anchor text, and to determine a probability that a representation of a given term in the first format corresponds to one or more terms in the second format .
In another embodiment, a method is provided for executing searches using potentially ambiguous questions or queries. When a user enters a question or query in a first format, it will be translated into a group of one or more variants in a second format. A search is then executed using the translated variants, and returning the sensitive information to the user. For example, the first format could comprise a sequence of numbers entered using a telephone keypad, and the second format could comprise alphanumeric text (eg, English, romaji, romaja, pinyin, or the like). In some embodiments, the group of one or more variants is selected, by discarding translated variants that do not appear in a predefined lexicon, and / or that contain low probability combinations of predefined characters. In some embodiments, a probabilistic dictionary is used to further translate the group of one or more variants into a third format before running the search. For example, the probabilistic dictionary can be used to translate the group of one or more variants
ES 2 323 786 T3 from romaji, romaja, or pinyin, to kanji, katakana, haragana, hangul, hanja, or traditional Chinese characters, and the search can then be performed using the translated variants.
These and other features and advantages of the present invention will be presented in more detail in the following detailed description and in the accompanying figures, which illustrate by way of example the principles of the invention.
Brief description of the drawings
The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments of the invention, and together with the description, serve to explain the advantages and principles of the invention. In the drawings:
Figure 1 illustrates a block diagram of a system in which methods and apparatus compatible with the present invention can be implemented;
Figure 2 illustrates a block diagram of a client device, compatible with the invention;
Figure 3 illustrates a diagram describing three documents;
Figure 4a illustrates a conventional alphanumeric index;
Figure 4b illustrates a flow chart for providing search results in response to a conventional alphanumeric search query or question;
Figure 5a illustrates a flow chart, compatible with the invention, for providing search results, in response to an ambiguous search query or question;
Figure 5b illustrates a diagram for mapping alphanumeric information to numerical information; <sup>Y</sup> Figure 6 illustrates another flowchart, compatible with the invention, for providing search results in response to an ambiguous search query or question.
Figure 7 illustrates a method for executing a search in accordance with embodiments of the present invention.
Figure 8 illustrates a probabilistic dictionary of character set translations.
Figure 9 illustrates the use of parallel anchor text to build a probabilistic dictionary.
Figure 10 illustrates a collection of linked documents using anchor text.
Figures 11A and 11B illustrate the calculation of probable translations based on the anchor text shown in Figure 10.
Figure 12 shows a probability distribution associated with a translation of illustrative words.
Description of specific realizations
Reference will now be made in detail to embodiments of the present invention as illustrated in the accompanying drawings. The same reference numbers may be used throughout the drawings and the following description to refer to the same or similar parts. The following description is presented to enable anyone in the art to make and use the operative body of the invention. Descriptions of specific embodiments and applications are provided as examples only, and various modifications will be readily apparent to those skilled in the art. For example, although many of the examples are described in the context of Internet Web pages, it will be understood that embodiments of the present invention could be used to search for other types of documents and / or information, such as books, newspapers, magazines, or the like. . Similarly, although for the sake of illustration many of the examples describe the translation of Japanese text from romaji to katakana, lazy, and / or kanji, those skilled in the art will appreciate that the systems and methods of the present invention may be applied. to any suitable translation. For example, without limitation, embodiments of the present invention could be used to search for text written, for example, with traditional Chinese characters or Korean characters in Hangul or Hanja, based on questions or queries received in some other format (for example, pinyin or romaja). The general principles described herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. Thus, the present invention must be in accordance with the broadest scope, encompassing numerous alternatives, modifications and equivalents compatible with the principles and characteristics set forth herein. For the sake of clarity, details related to technical material that is known in the fields related to the invention have not been described in detail, in order not to unnecessarily obscure the present invention.
ES 2 323 786 T3
A. General
Methods and apparatus compatible with the invention allow a user to propose an ambiguous search query or question, and to receive potentially unambiguous search results. In one embodiment, a sequence of numbers received from a user on a standard telephone keypad is translated into a set of potentially corresponding alphanumeric sequences. These corresponding alphanumeric sequences are provided as input to a conventional search engine, using a Boolean expression "OR". In this way the search engine is used to help narrow the results of the search in which the user was probably interested.
B. Architecture
Figure 1 illustrates a system 100 in which methods and apparatus compatible with the present invention can be implemented. System 100 may include multiple client devices 110 connected to multiple servers 120 and 130 via network 140. Network 140 may include local area network (LAN), wide area network (WAN), telephone network , such as the public switched telephone network (PSTN), an intranet, the Internet, or a combination of networks. Two client devices 110, and three servers 120 and 130, have been illustrated connected to the network 140 for the sake of simplicity. In practice, there may be more or fewer client and server devices. Also, in some cases, a client device can perform the functions of a server, and a server can perform the functions of a client device.
Client devices 110 can include devices, such as large computers, minicomputers, personal computers, portable computers, personal digital assistants (PDAs), or the like, capable of connecting to the network 140. Client devices 110 can transmit data over network 140 or receive data from network 140 through a wired, radio or optical connection.
Figure 2 illustrates an exemplary client device 110 compatible with the present invention. The client device 110 may include a bus 210, a processor 220, a main memory 230, a read-only memory (ROM) 240, a storage device 250, an input device 260, an output device 270, and an interface. communications 280.
Bus 210 can include one or more conventional buses that allow communication between components of client device 110. Processor 220 can include any type of conventional processor or microprocessor that interprets and executes instructions. Main memory 230 may include random access memory (RAM) or another type of dynamic storage device, which stores information and instructions for execution by processor 220. ROM 240 may include a conventional ROM device or other type of static storage device, which stores static information and instructions for use by processor 220. Storage device 250 may include magnetic and / or optical recording medium. and its corresponding operating unit.
The input device 260 can include one or more conventional mechanisms that allow a user to enter information into the client device 110, such as a keyboard, a mouse, a pencil, voice recognition mechanisms and / or biometric type. , etc. The output device 270 may include one or more conventional mechanisms that provide information output to the user, including a screen, a printer, a speaker, etc. Communications interface 280 may include any transceiver-like mechanism that allows client device 110 to communicate with other devices and / or systems. For example, communication interface 280 may include mechanisms for communicating with another device or system over a network, such as network 140.
As will be described in detail below, client devices 110, compatible with the present invention, perform certain search-related operations. Client devices 110 can execute these operations in response to a processor 220 by executing software instructions contained on a computer-readable medium, such as memory 230. A computer-readable medium can be defined as one or more memory devices and / or carrier waves. Software instructions can be read into memory 230 from another computer-readable medium, such as data storage device 250, or from another device through communication device 280. Software instructions contained in memory 230 cause processor 220 to perform search related activities described below. Alternatively, hard-wired physical circuits may be used in place of or in combination with the software instructions, to implement processes compatible with the present invention. Thus, the present invention is not limited to any specific combination of physical circuit and software.
Servers 120 and 130 may include one or more types of computer systems, such as a central computer, minicomputer, or a personal computer, capable of connecting to network 140, to enable servers 120 and 130 to communicate with client devices 110. In alternative implementations, servers 120 and 130 may include mechanisms for directly connecting to one or more client devices 110. Servers 120 and 130 can transmit data over network 140, or receive data from network 140 through a wired, radio, or optical connection.
ES 2 323 786 T3
The servers may be configured in a manner similar to that described above with reference to FIG. 2 for the client device 110. In an implementation compatible with the present invention, the server 120 may include a search engine 125 usable by the client devices 110. Servers 130 can store documents (or Web pages) accessible by client devices 110.
C. Configuration architecture operation
Figure 3 illustrates a diagram describing three documents, which can be stored for example on one of the servers 130.
A first document (Document 1) contains two entries - "car repair" - and which is numbered with "3" at the bottom. A second document (Document 2) contains the entry “Video rental”. A third document (Document 3) contains three entries for - "wine", "champagne", and "bar items" - which includes a link (or reference) to Document 2.
For the sake of illustrative simplicity, the documents shown in Figure 3 contain only alphanumeric strings of information (eg "car", "repair", "wine", etc.). Technicians skilled in the art will recognize, however, that in other situations the documents could contain other types of information, such as phonetic or audiovisual information.
Figure 4a illustrates a conventional alphanumeric index, based on the documents shown in Figure 3. The first column of the index contains a list of alphanumeric terms, and the second column contains a list of the documents corresponding to those terms. Some terms, such as the alphanumeric term “3”, only apply (for example, appear) in a document, in this case in Document 1. Other terms, such as “rent”, correspond to multiple documents, in this case in Documents 1 and 2.
Figure 4b illustrates how a conventional search engine, such as search engine 125, would use the index illustrated in Figure 4a to provide search results, in response to an alphanumeric search query or question. The alphanumeric question or query can be generated using any conventional technique. For the purposes of illustration, Figure 4b describes two alphanumeric questions or queries: "car" and "wine." Under a conventional solution, the search engine 125 receives an alphanumeric question or query, such as "car" (step 410), and uses the alphanumeric index to determine which documents correspond to said question or query (step 420). In this example, a conventional search engine 125 would use the index illustrated in Figure 4a, to determine which "car" would correspond to Document 1, and would return Document 1 (or a reference to it) to the user as a search result. . Similarly, a conventional search engine would determine that "came" would correspond to Document 3 and return Document 3 (or a reference to it) to the user (step 430).
Figure 5a illustrates a flowchart, compatible with the invention, of a preferred technique for providing search results, in response to a question or numerical search query, based on the documents and index shown in Figures 3 and 4a, respectively. For the sake of clarity of exposition, Figure 5a describes a particular technique for processing a numerical question or query, based on matching or mapping with a standard hand-held telephone; however, those skilled in the art will recognize that other techniques compatible with the invention may be used.
At step 510, the sequence "227" (consisting of the numerical components "2", "2" and "7") is received from a user. In step 520, information is obtained on how the numerical components correspond to letters. Assuming the user entered the information from a standard telephone keypad, this mapping or matching information is shown in Figure 5b. As shown in Figure 5b, the letters "a", "b", and "c" each correspond to the number "1", the letters "p", "q", "r", and " s ”each correspond to the number“ 7 ”, and so on.
In step 530, using this mapping information, the sequence "227" is translated into its potential alphanumeric equivalents. Based on the information shown in Figure 5b, there are 36 possible letter combinations, corresponding to the sequence "227", including the following: aap, bap, cap, abp, bbp, ... bar ... car .. ccs. If the numbers are included in the possible combinations (for example, "aa7") then there would be 80 possible combinations. Rather than generating all possible alphanumeric equivalents, it may be desirable to limit the generated equivalents based on some lexicon. For example, it may be desirable to generate only those alphanumeric equivalents that can appear in a dictionary, in a search engine record of previous search queries or questions, etc .; or, on the contrary, limit the alphanumeric equivalents by using known statistical techniques (for example, the probability of certain words appearing together).
At step 540, these alphanumeric equivalents are provided as input to the conventional search engine, such as those described with reference to Figures 4a and 4b, using a logical "OR" operation. For example, the search query or question provided to the search engine might be "aap OR bap OR cap OR abp ... OR bar ... OR car." Although all possible alphanumeric equivalents can be provided to the search engine, a subset can instead be used, using conventional techniques, to eliminate improper equivalents.
ES 2 323 786 T3 bables. For example, a narrower list of possible combinations could be generated, by using techniques that use probabilistic information on the use of letters or words: combinations starting with "qt" could be ignored, but including (and favoring) the combinations that begin with "what".
In step 550, the search results are obtained from the search engine. Since terms such as "aap" and "abp" do not appear in the search engine index, they will actually be ignored. Actually, the only terms contained within the index shown in figure 4b are "car" and "bar", and therefore the only search results returned are those that refer to Documents 1 and 3. In step 560, these search results are presented to the user. Search results can be presented in the same order provided by the search engine, or they can be reordered based on considerations such as the user's language. Assuming that the user was the only one interested in the documents containing the term "bar", the user would receive an undesirable result (Document 3) in addition to the desired result (Document 1). This may be an acceptable price to pay, however, with the advantage that the user only has to press three keys to formulate the question or search query.
Figure 6 illustrates another flowchart, compatible with the invention, of a preferred technique for providing search results, in response to the question or numerical search query, based on the documents and index shown in Figures 3 and 4a , respectively. This flowchart demonstrates how increasing the dimension of the received stream can help limit the search results to those desired by the user. For the sake of illustrative clarity, Figure 6 again describes a particular technique for processing a numerical question or query based on standard handset mapping or matching; although those skilled in the art will recognize that other techniques compatible with the invention may be used.
In step 610, the sequence "227 48367" (consisting of the numerical components "2", "2", "7", "4", "8", "3", "6", "7") is received from the user. For the sake of simplification of explanation, the sequence "227" will be referred to as the "number word" and the entire sequence "227 48367" will be referred to as the "number phrase". Possible alphanumeric equivalents of a number word will be referred to as "letter words" and possible alphanumeric equivalents of a number phrase will be referred to as "letter phrases".
In step 620, information is obtained about how the numerical components correspond or map to the letters. Assuming the same matching information is used as shown in Figure 5b, at step 630, the number phrase "227 48367" is translated into potentially corresponding letter phrases. Based on the information shown in Figure 5b, there are 11664 possible letter phrases that correspond to the sequence "227 48367".
At step 640, the letter phrases are provided as input to a conventional search engine, such as that described with reference to Figures 4a and 4b, using a logical "OR" operation. For example, the question or search query that is provided to the search engine might be “'aap gtdmp' OR 'aap htdmp' ... OR 'bar articles'”. Although all possible letter phrases can be supplied to the search engine, a subset may instead be used by using conventional techniques to eliminate unlikely letter phrases.
In step 650, the search results are obtained from the search engine. Because many search engines are designed to rank high for documents that contain the exact phrase, Document 3 would likely be the highest-ranking search result (that is, because it contains the exact phrase of "articles bar ”). No other document in the example contains one of the other letter phrases generated in step 620. Additionally, many search engines downgrade (or remove) the search results that contain individual parts of a phrase but not the entire phrase. For example, Document 1 would be downgraded or eliminated because it contains the letter word "car", which corresponds to the first part of the letter phrase, although it does not contain any letter word that corresponds to the second part of the lyrics phrase. Finally, letter phrases such as "aap htdmp" are actually ignored because they do not contain letter words that appear in the search engine index.
In step 660, the search results are presented to the user. In the example shown, the first result shown to the user would be Document 3, which is probably the most relevant to the user's question or query. Document 1 can be deleted together, because it does not contain one of the possible letter phrases. In this way, the user is provided with the most relevant search results.
Although the above descriptions with reference to Figures 5 and 6 are made with reference to the received numerical information, and in correspondence with the alphanumeric information, those skilled in the art will recognize that other implementations compatible with the invention are possible. For example, instead of receiving a sequence of numbers corresponding to keys pressed by a user, the received sequence may comprise the first letters corresponding to keys pressed by the user. In other words, instead of receiving "227", the received sequence can be "aap". Consistent with the invention, the equivalent letter sequences generated in steps 530 or 630 could be other letter sequences (eg, "bar") corresponding to "aap". In reality, the received sequence may contain phonetic, audiovisual elements, or any other type of information components.
ES 2 323 786 T3
Regardless of the format in which the sequence is received, it is generally preferred that the received sequence be translated into a sequence corresponding to the format in which the information is stored in the search engine index. For example, if the search engine index is stored in the alphanumeric format, the received sequence would be translated into alphanumeric sequences.
Additionally, it is generally preferred that the mapping or mapping technique that is used to translate the received sequence of information components is the same technique that is used in the user device to perform mapping of user input into the information generated by the device. However, there may be cases where it is preferable to use a different mapping or matching technique than that used for user input.
Embodiments of the present invention may enable users to be able to execute entered searches using keyboards of languages other than the intended purpose. For example, a web page containing Japanese text may be written in kanji, while a user attempting to search for such a page may only have access to a standard ASCII keyboard (or hand phone) based on the Roman alphabet.
Figure 7 illustrates a method for executing such a search. As shown in Figure 7, a user types a question or query, using a standard input device (for example, ASCII keyboard, handheld phone, etc.), and submits the question or query to the search engine . The question or query can be written in a character set (eg romaji) that is different from the character set in which some of the sensitive documents are written (eg kanji). The search engine receives the question or query (block 702), translates it into the relevant format (s) (block 704), and executes a search of the documents sensitive to the translated question or query, fueling for example the search techniques conventional (block 706). The search engine then returns a list of sensitive documents (and / or copies of the documents themselves) to the user (block 708). For example, the results could be returned to the user in a manner similar to that described above in connection with Figure 6.
As shown in figure 7, the user's question or query is preferably translated on the search engine server, as opposed to the client, thus relieving the user of the need to obtain special-purpose software in order to run the translation. . However, it will be appreciated that in other embodiments, some or all of the translations could be executed on the client. Furthermore, in some embodiments the question or query can be entered using a device such as a telephone keypad. In such embodiments, the initial numeric question or query may first be converted to an alphanumeric format (eg, romaji), using the mapping or matching techniques previously described in connection with Figures 5 and 6, including for example the application of a lexicon. and / or probabilistic techniques to rule out low probability mappings or correspondences (for example, those mapped that include combinations of letters that do not have a presence in romaji). Once an alphanumeric translation of the question or query has been obtained, the rest of the steps shown in Figure 7 could be executed (ie, 704, 706 and 708).
The translation of the question or query from one character set to another (ie block 704 in FIG. 7) can be performed in different ways. One technique is to use a conventional static dictionary of word meanings or translations to map or match each term in the question or query to a corresponding term in the target language or character set. However, a problem with this solution is that it will frequently generate inaccurate results, since the words are often ambiguous, and the questions or queries will often be too short to provide adequate contextual clues to resolve this ambiguity. For example, the word "bank" may refer to a river bank, or a financial institution, or an airplane maneuver, thus making it difficult to translate accurately in the abstract. Furthermore, if the dictionary is not relatively large and / or frequently updated, it may not contain entries for all the terms that the search engine can find, such as rarely used words, slang, idioms, proper names, or the like.
Embodiments of the present invention can be used to solve or alleviate some or all of these problems, by using a probabilistic dictionary to translate the terms of the question or query from one language or set of characters (for example, ASCII) to another ( for example, kanji). In a preferred embodiment, the probabilistic dictionary maps or maps a set of terms to another set of terms, and associates a probability with each of the mappings. For convenience, a "term" or "token" will refer to words, phrases, and / or (more generally) to sequences of one or more characters that may include spaces.
Figure 8 shows an example of a probabilistic dictionary 800 such as the one described above. The probabilistic dictionary 800 in the example shown in Figure 8 maps or matches words written in romaji (an alphabetical representation of the Roman alphabet from Japanese) to words written in kanji (a Roman set of Japanese characters based on ideograms). For ease of explanation, Figure 8 represents Romaji terms such as “<term><sub>romaji</sub>", And kanji terms such as" <teimmo><sub>kanji</sub>”. It will be noted that in a current romaji to kanji dictionary, the current terms romaji and kanji would be used, rather than the English translations shown in figure 8. It will therefore be noted that figure 8 is provided for ease of explanation of the embodiments of the present invention, and not to illustrate the current features and meaning of the Japanese text.
ES 2 323 786 T3
Dictionary 800 contains entries 808, 810, 812, 814 for various romaji 802 terms. The dictionary also contains the potential 804 kanji representations of each of these terms, along with the corresponding probability 806 of each representation being correct. For example, the romaji term "bank" could correspond or be mapped to the kanji meaning "steep slope" with probability 0.3, to a term of meaning "financial institution" with probability 0.4, and to a term of meaning " airplane maneuver ”with probability 0.2. With probability 0.1, the term could be matched or mapped to "other," which is a generic way of allowing each term to correspond to terms that may not be in the dictionary.
Again, it will be noted that the example shown in Figure 8 has been constructed to illustrate that a given term (eg, the word "bank") in a first set of characters or language, can be mapped to or correspond to more than one term. in another character set or language. The person skilled in the art will note, however, that while for the sake of clarity the particular example in Figure 8 illustrates this principle, using English words and meanings, the current Romaji representation of the word "bank", for example , might not be ambiguous in the same format as the English equivalent (for example, there may be no ambiguity in romaji between the word for financial institution and the word for airplane maneuver). It will be appreciated that for ease of explanation, the dictionary shown in Figure 8 has been simplified in other respects as well. For example, a current probability dictionary might contain many potential matches or mappings for each term, or it might contain only matches that exceed a predefined probability threshold.
The preferred embodiments of the present invention use said probabilistic dictionary for the translation of questions or queries expressed in a language 7 / or set of characters, thus enabling users to find documents written in a different set of characters and / or in a language other than that of the original question or query. For example, if the user enters a question or query for "cars" in romaji, the probabilistic dictionary can be used to match the term romaji for "cars", for example, for the kanji term for "cars". In this way, users can find documents related to their questions or queries, even if the character set of the questions or queries (for example, romaji) and the character set of the same documents (for example, kanji) are not the same. It will be noted that in this particular example, the current language of the question or query has not been changed (both romaji and kanji are used to express Japanese), but only the character encoding.
As a further example, the term "tired" in ASCII English could match or map to the term "müde" in German, using the Latin 1 character encoding, since the umlaut-u character does not exist in ASCII. It will be noted that in this example the dictionary provides both a translation into another language (English to German) and a translation into another character encoding (ASCII to Latin 1).
Anchor text comprises the text associated with a hyperlink between web pages (or places within a given web page). For example, in the language of hypertext marks (HTML), the command: “<A ref==http://www.abc.com"> Banks and Savings and Loans </A>” causes the text “Banks and Savings and Loans ”is displayed as a hyperlink that points to the Web page found at http://www.abc.com. The text "Banks and Savings and Loans" is referred to as anchor text, and typically provides a short description of the web page to which it points (eg www.abc.com). In reality, anchor text will often provide a more accurate description of the web page than the page itself, and can therefore be particularly useful in determining the nature of the web page to which it points. In addition to that, the use of the word and the distribution in the anchor text is closer in spirit than that found in the questions or user queries. It is also the case that many anchors that point to a given page can contain the same highly similar text. For example, anchors pointing to www.google.com will often simply display “Google”, or at least use this term throughout other texts. So by examining all of this, for example katakana, the anchors pointing to www.google.com, the katakana translation of “Google” can be inferred with a relatively high degree of confidence, simply by searching for the term that appears with the highest frequency (possibly after discarding certain low-information content anchors, such as those that simply state "click here"). Preferred embodiments of the present invention take advantage of these anchor text characteristics to provide more accurate translations.
With reference to figure 9, upon receiving a question or query that contains a term written in a first set of characters (for example, ASCII) (block 902), the server identifies a set of anchor text where the term can appear (block 904). For example, the server can examine an index of all known anchors, to identify those anchors that contain the term. Next, the web pages for which the anchors are identified (block 906), will be the anchors written in the target language or target character set (for example, lazy, katakana, and / or kanji) that point to these. pages (block 908). The system will now have two sets of documents (where the anchor text is considered as a document format). The distribution of the question or query term in one set of documents (for example, the anchors containing the original ASCII question or query) will then be used to identify the most likely candidates for the translated phrase in the other set of documents (for example , the anchors in parallel). Statistics can be calculated regarding the frequency with which anchor text terms appear, and these statistics can be used to determine the relative frequencies or probabilities of terms found in the anchor text that comprise the correct translation of the anchor text. original question or query (block 910). For multi-word questions or queries, the process described above can be repeated for each word, or the entire question or query can be treated simply as a single term, or it could
ES 2 323 786 T3 use a suitable grouping of words. For example, if the question or query is "big houses", possible translations could be constructed by locating the aligned anchor text that contains that phrase (or at least one of the words in the phrase). Similarly, if the question or query contained more than two terms, experiments could be constructed to determine any mapping or correspondence, by selecting the appropriate subsets of the terms in the question or query and generating the results for those terms.
An advantage of performing a translation as shown in Figure 9 is that the translation system does not require prior knowledge of the correspondences or mapping between the terms in a language or set of characters and the corresponding ones in the target set. Instead, the correspondences or mappings can be determined dynamically, based on the body of data that is available to run the statistical analysis. Thus, for example, it is possible to discover accurate translations of slang terms, idioms, proper names, and the like, without incurring the effort or expense (eg, linguistic analysis and research) of maintaining a conventional static dictionary.
An illustrative embodiment of the above translation techniques will now be described with reference to Figures 10-12. In this example, it will be assumed that the user has entered the question or query term “casa”, and wants to obtain the search results written in Spanish (or simply a translation of the question or query term). The server will therefore try to translate the English term "house" into the equivalent Spanish.
Referring to Figure 10, the variety of Web pages 959, 961, 965 link via anchor text 960, 962, 964, 966 to pages 972 and 974. Some of these pages, and their associated anchor text , are written in English (that is, pages 959a-e and 963a-t) and some are written in Spanish (that is, pages 961a-e and 965aj). The server first finds all the anchors that use the term "house". These anchors can be located, for example, by searching an index of the anchor text stored on the server. Using that index, the server could first find the five anchors 960 that use the phrase "big house", and that point to the Web page 972. The server then determines that there are also five anchors 962 in the language of the target (that is, Spanish) to point to page 972 as well. In the example shown in Figure 10, these anchors contain the text "big house." Anchors that point to the same page (such as anchors 960 and anchors 962) or to pages that support a predefined relationship, are said to be "aligned", where in a more general sense alignment is typically referred to (or a probable equivalence) to the equivalence of the aligned units.
Figure 11A shows the frequency with which the term appears in the anchors 962 of the target language. As shown in FIG. 11A, the terms "home" and "large" each appear five times (ie, once at each anchor 962). So, aside from the total ten terms that appear in the 962 target anchors (that is, two terms per anchor in each of the five anchors), “home” counts in half, and “large” counts in half. other half. Thus, as shown in Figure 11A, at this point the term "house" could map or correspond well to "house" or "big" with equal probability, since both terms appear with equal frequency.
However, as shown in figure 10, the system also finds twenty English anchors 964 that contain the term "house" and that point to page 974, and ten Spanish anchors 966 that contain the term "house" and that point also to page 974. As shown in Figure 11B, the term “house” will correspond or map to “house” with probability 0.75 (that is, 15/20), and to “large” with probability 0.25 (that is, 5/20). These probabilities are simply calculated by dividing the total number of occurrences of each term in the target language anchors (that is, fifteen, in the case of "home") by the total number of terms, including duplicates, in the target language anchors. target language (that is, twenty terms: ten contained in anchors 962, and ten contained in anchors 964). Alternatively, or additionally, other techniques could be used to calculate and / or refine the probabilities of a given translation or match. For example, those skilled in the art will appreciate that a variety of well-known techniques could be used to reduce variance error and probability estimates, such as Bayesian methods, histogram smoothing, kernel smoothing, shrinkage estimators, and / or other estimation techniques.
Should more text become available, the probabilities could be further refined. For example, a final probability distribution could be similar to that shown in figure 12, in which the term "house" is mapped or corresponds to a relatively high probability with respect to "house" and its diminutive form "house. ”, And with a somewhat lower probability with terms similar to“ casino ”and“ mansión ”(the Spanish word for mansion), and with a negligible probability with terms similar to“ grande ”. Thus, a correct translation, as well as the identification of probable synonyms, can be obtained without knowledge of the languages and / or character sets being translated.
It will be appreciated that the example described in connection with Figures 10-12 is provided for the purposes of illustration, and not limitation, and that many changes can be made to the methodology described herein. For example, different statistical techniques could be used to achieve probabilities, and / or modifications to the basic techniques described above. Furthermore, although the preceding example describes the translation process as it takes place after receipt of the question or query from the user, it will be seen in the other embodiments the mapping or matching process could be executed before the question is received. or user query. Such pre-computed mappings or correspondences could be stored in a dictionary such as that described in
ES 2 323 786 T3 figure 8, which would then be applied to translate user questions or queries as they might be received. Finally, it will be understood that text other than aligned anchor text could be used for translation. For example, inline statements or other data could be used in a similar way. In many countries there is more than one official or recognized language, and newspapers and magazines will often contain the same article written in each of these languages. These parallel translations can be used in the same way as the previously described anchor text, to prepare probabilistic dictionaries of word translations.
Thus, the preferred embodiments advantageously allow users to enter questions or search queries and / or translation requests in a convenient way (eg, using an ASCII keyboard), and provide accurate and automatic translation and search and search. In some embodiments, further refinements can be made with the basic model described above. For example, in some embodiments a preference (weighting) may be given to anchors that contain multiple terms that are similar to the number of terms in the original question or query and / or other aligned anchors. For example, in the system shown in Figure 10, preference could be given to the anchors pointing to page 974, just like the original question or query, each containing a unique term. Similarly, if an anchor that contains the text "the big house" is also pointed to page 972, its weight could be decreased by an appropriate factor, since it will contain more terms (that is, 3) than the other anchors with the which are aligned. Said weighting scheme could be reflected in the probability calculation shown in Figure 11B, by multiplying the frequencies associated with these anchor terms by a suitable factor.
D. Conclusion
As described above, methods and systems compatible with the invention can be used to provide search results in response to ambiguous search queries or questions and / or to translate terms in another set of characters and / or languages. Various translation and search techniques and systems have been described. However, it will be appreciated that the foregoing description has been presented for the purposes of illustration, and that many modifications and variations are possible in light of the foregoing descriptions, or through practice of the invention. For example, although the above description is based on a client-server architecture, those skilled in the art will recognize that a peer-to-peer (P2P) architecture, compatible with the invention, can be used. Furthermore, although the described implementation includes software, the invention can be implemented as a combination of hardware and software or only with hardware. Additionally, while aspects of the present invention are described as being stored in memory, the person skilled in the art will appreciate that these aspects may also be stored on other types of computer-readable media, such as secondary storage devices, similar to hard drives, floppy disks, or CD-ROMs; an Internet carrier wave; or other forms of RAM or ROM. The scope of the invention is therefore defined by the claims and their equivalents.
Contents6
15 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15
48 members in 13 offices
Priority claims5
| Document | Office | Kind | Date |
|---|---|---|---|
| 20030676724 | United States of America | – | |
| 67672403 | United States of America | A | |
| 67672403 | United States of America | A | |
| 04783836676724 | – | – | – |
| US20030676724 | – | – | – |
Members48
| Document | Office | Kind | |
|---|---|---|---|
| US2002042791A1 | United States of America | A1 | |
| US2002133481A1 | United States of America | A1 | |
| US6529903B2 | United States of America | B2 | |
| US2004261021A1 | United States of America | A1 | |
| US6865575B1 | United States of America | B1 | |
| WO2005033967A2 | World Intellectual Property Organization (WIPO) | A2 | |
| WO2005033967A3 | World Intellectual Property Organization (WIPO) | A3 | |
| EP1676211A2 | European Patent Office (EPO) | A2 | |
| KR20060090689A | Republic of Korea | A | |
| CN1860473A | China | A | |
| US7136854B2 | United States of America | B2 | |
| US2007022101A1 | United States of America | A1 | |
| JP2007507796A | Japan | A | |
| RU2006114696A | Russian Federation | A | |
| EP1676211B1 | European Patent Office (EPO) | B1 | |
| EP2043003A2 | European Patent Office (EPO) | A2 | |
| AT426206T | Austria | T | |
| ATE426206T1 | Austria | T1 | |
| DE602004020086D1 | Germany | D1 | |
| EP2043003A3 | European Patent Office (EPO) | A3 | |
| ES2323786T3This record | Spain | T3 | |
| RU2363983C2 | Russian Federation | C2 | |
| JP2010282639A | Japan | A | |
| JP2011090718A | Japan | A | |
| JP4717821B2 | Japan | B2 | |
| KR20110117218A | Republic of Korea | A | |
| KR20110117219A | Republic of Korea | A | |
| CN102236702A | China | A | |
| EP2388709A1 | European Patent Office (EPO) | A1 | |
| KR20120039755A | Republic of Korea | A | |
| KR101140187B1 | Republic of Korea | B1 | |
| HK1163846A | Hong Kong, China | A | |
| HK1163846A1 | Hong Kong, China | A1 | |
| KR101242961B1 | Republic of Korea | B1 | |
| JP2013084306A | Japan | A | |
| KR101261158B1 | Republic of Korea | B1 | |
| JP5231491B2 | Japan | B2 | |
| CN102236702B | China | B | |
| JP5425820B2 | Japan | B2 | |
| US8706747B2 | United States of America | B2 | |
| US2014188454A1 | United States of America | A1 | |
| JP5608766B2 | Japan | B2 | |
| US9734197B2 | United States of America | B2 | |
| US2017351673A1 | United States of America | A1 | |
| EP2388709B1 | European Patent Office (EPO) | B1 | |
| TR2018016343T4 | Türkiye | T4 | |
| TR201816343T4 | Türkiye | T4 | |
| PL2388709T3 | Poland | T3 |
Numbers
- Publication
- 2323786
- Publication, DOCDB
- 2323786
- Publication, EPODOC
- ES2323786T
- Application
- 4783836
- Application, DOCDB
- 04783836
- Application, EPODOC
- ES20040783836T
Titles2
- Spanish
- SISTEMAS Y METODOS PARA BUSCAR UTILIZANDO PREGUNTAS ESCRITAS EN UN CONJUNTO DE CARACTERES Y/O IDIOMA DISTINTO AL DE LAS PAGINAS OBJETIVO.
- English
- SYSTEMS AND METHODS TO SEARCH USING WRITTEN QUESTIONS IN A SET OF CHARACTERS AND / OR LANGUAGE DIFFERENT FROM THAT OF THE OBJECTIVE PAGES.
Classification
- CPC, 7
- G06F3/0237
- G06F16/24522
- G06F16/972
- G06F16/2452
- G06F16/3332
- G06F40/12
- G06F40/237
- IPC, 3
- G06F17 27
- G06F17 30
- G06F40 237