Simplifying query terms with transliteration

[0001] This invention relates to the handling of language uncertainty in processing search queries and searches over a corpus including documents and other searchable resources, where the queries and resources can be expressed in any one of a number of different languages.

[0002] A search engine indexes documents and provides a means to search for documents whose contents are indexed by the search engine. Documents are written in many different languages; some documents have content in multiple languages. A variety of characters are used to express the words of these languages: the Latin alphabet (i.e., the 26 unaccented characters from A to Z, upper and lower case), diacritics (i.e., accented characters), ligatures (e.g., , β, ), Cyrillic characters and others.

[0003] Unfortunately the ability and ease of producing these characters varies greatly from device to device. Both the authors of content and the users of search engines may not be able to produce conveniently characters that they would prefer. Instead, users of such devices will often provide a character or character sequence that is a close substitute. For example, AE may be provided in lieu of . Moreover the conventions of such substitutions vary among languages and users. For example, some users who search for AE may prefer to see results including as well.

[0004] One approach for addressing this issue in a search engine is to process the indexed content to remove accents and convert special characters into a standard set of characters. This approach removes information from the index, making it impossible to retrieve only specific accented instances of a word. This approach also suffers from language agnosticism which is insensitive to users whose expectations are shaped by the conventions of their particular language.

[0005] This specification discloses various embodiments of technologies for using the terms of a search query. Embodiments feature methods, systems, apparatus, including computer program product apparatus. Each of these will be described in this summary be reference to the methods, for which there are corresponding systems and apparatus.

[0006] In general, in one aspect, methods feature receiving from a user through a user interface a search query comprising one or more query terms, the user interface having an interface language, the interface language being a natural language; and determining a query language for the query from the query terms and the interface language, the query language being a natural language. These and other embodiments can optionally include one or more of the following features. The methods include determining a score for each one of multiple languages, the score indicating a likelihood that the query language is that one of the multiple languages. The methods include using the query language to select one or more mappings and using the selected one or more mappings to simplify each query term to a corresponding simplified query term; and applying each simplified query term to a synonyms map to identify possible synonyms with which to augment the search query. The methods include determining a score for each one of multiple languages, the score indicating a likelihood that the query language is that one of the multiple languages.

[0007] In general, in another aspect, methods feature receiving from a user through a user interface a search query made up of one or more query terms, the user interface having an interface language, the interface language being a natural language; using the interface language to select one or more mappings and using the selected one or more mappings to simplify each query term to a corresponding simplified query term; and applying each simplified query term to a synonyms map to identify possible synonyms with which to augment the search query.

[0008] In general, in another aspect, methods feature generating a synonyms map from a corpus of documents, each document having attributed to it a document language, the document languages each being a natural language; wherein the synonyms map maps each of a plurality of keys to one or more corresponding variants; and each variant is associated with one or more of the document languages. These and other embodiments can optionally include one or more of the following features. The methods include for each associated language, each variant is associated with a score indicating a relative frequency of the variant among all variants for the associated language for the same key. The attribution of a document language to each document is determined automatically.

[0009] In general, in another aspect, methods feature generating a synonyms map from a corpus of documents by applying a first collection of language-dependent mappings to words in the corpus to generate keys for the map, each document having a document language attributed to it, the document language attributed to each document being used to determine the language-dependent mapping applied to words the document. These and other embodiments can optionally include one or more of the following features. The methods include generating a simplified query term from each query term in a search query by applying a second collection of language-dependent mappings to each query term, the search query having an query language attributed to it, the query language attributed to the search query being used to determine the language-dependent mapping applied to each query term. The first collection of language-dependent mappings is different from the second collection of language-dependent mappings.

[0010] In general, in another aspect, methods feature generating a synonyms map from a corpus of documents by applying a first collection of language-dependent mappings to words in the corpus to generate keys for the map, each document having a document language attributed to it, the document language attributed to each document being used to determine the language-dependent mapping applied to words the document; generating simplified query terms from a search query by applying a second collection of language-dependent mappings to query terms in the search query, the search query having an query language attributed to it, the query language attributed to the search query being used to determine the language-dependent mapping applied to the query terms; wherein the search query includes a first query term, the first query term being mapped to a first simplified query term by the applied language-dependent mapping from the second collection of language-dependent mappings determined by the query language, the first query term being mapped to a first key by the language-dependent mapping in the first collection of language-dependent mappings determined by to the query language, and the first simplified query term is different from the first key. These and other embodiments can optionally include one or more of the following features. The methods include attributing the interface language to the query as the query language.

[0011] In general, in another aspect, methods feature receiving from a user through a user interface a search query that includes a query term, the search query having attributed to it a query language; deriving a simplified query term from the query term; and identifying one or more potential synonyms for the query term by looking up the simplified query term in a synonyms map, the synonyms map mapping each of a plurality of keys to one or more corresponding variants, each variant being a word associated with one or more document languages, and each variant being associated for each associated language with a variant-language score indicating a relative frequency of the variant among all variants for the associated language for the same key. These and other embodiments can optionally include one or more of the following features. The methods include using the attributed query language and the variant-language scores of one or more variants for the simplified query term to select variants to use in augmenting the search query. The methods include attributing the interface language to the query as the query language. Where the search query has attributed to it multiple query languages, each with a respective query-language score, the methods further include using (a) the query-language scores and (b) the variant-language scores of one or more variants for the simplified query term to select variants to use in augmenting the search query. Using the query-language scores and the variant-language scores includes summing over all languages the product for each language of the query-language score for the language and the variant-language score for the language.

[0012] In general, in another aspect, methods feature receiving from a user through a user interface a search query made up of one or more query terms; and receiving an indication of a user preference to apply transliteration in simplifying the query terms of the search query. These and other embodiments can optionally include one or more of the following features. The methods include applying transliteration in simplifying the query terms of the search query to generate simplified query terms if the user preference is to apply transliteration and otherwise not applying transliteration in simplifying the query terms of the search query to generate simplified query terms; and using the simplified query terms to identify synonyms to use in augmenting the search query. The indication of a user preference to apply transliteration in simplifying the search query is a user selection of one of a number of particular interface languages. The methods include receiving from a user through a user interface a search query made up of one or more query terms; applying transliteration in simplifying the query terms of the search query to generate simplified query terms; and using the simplified query terms to identify synonyms to use in augmenting the search query.

[0013] In general, in another aspect, methods feature receiving from a user through a user interface a search query made up of one or more original query terms for searching a collection of documents, the user interface having a user interface language; identify the user interface language as a small language or not a small language, a small language being a natural language having a relatively small representation in the collection of documents; simplifying each query term to a simplified form; and if the user interface language is a small language, for each original query term that has a simplified form that is different from the original term, using the original query term as-is and not providing any synonyms for the query term, and for each original query term that is identical to its simplified form, using the simplified form to identify synonyms for the original query term for use in augmenting the search query. These and other embodiments can optionally include one or more of the following features. Simplifying each query term includes transliterating.

[0014] Particular embodiments of the invention can be implemented to realize one or more of the following advantages. A system can correctly add appropriate accents to words in Spanish or Portuguese, where the accents are different in each language. A system can correctly add accents to words in a language different from the language of the user interface with which a user is interacting. A system can transliterate in appropriate circumstances. A system can avoid adding unnecessary diacritical variants to a search query, increasing the likelihood that search results will be in a language desired by the user.

[0015] The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the invention will be apparent from the description and drawings, and from the claims.

[0022] Like reference numbers and designations in the various drawings indicate like elements.

[0023] As shown in FIG. 1, a process 100 creates a synonyms map from a corpus of documents. The documents can be HTML (Hypertext Markup Language) documents, PDF (Portable Document Format) documents, text documents, word processing documents (e.g., Microsoft® Word documents), Usenet articles, or any other kinds of documents having text content, including metadata content. The process 100 can also be applied to other kinds of text-searchable resources, e.g., media resources identified by metadata.

[0024] The synonyms map contains common-form words as keys, each of which is associated with one or more variants. For example, consider a simple corpus in which only two languages are found: French and English. If “elephant” is a common-form entry in the synonyms map, then the variants “elephant”, “éléphant” and “eléphant” would be associated with that entry as values, if these variants are found in the corpus. Each value also includes additional information: the languages of the documents in which instances of the variant appear, and the number of times the variant appears in that language. Continuing the example, “eléphant” might be found in the corpus 90 times among documents recognized as being English and 300 times among documents recognized as being French.

[0025] Process 100 operates on a training corpus of documents (step 110). The training corpus of documents is ideally a collection of documents representative of documents contained in a search corpus. Alternatively, the training corpus and the search corpus can be the same, or the training corpus can be a snapshot of, or an extract from, the search corpus. The training corpus should contain documents from all languages represented in the search corpus. The training corpus should contain a sufficient number of documents in each language so that the documents contain a significant portion of the words found within all documents of the language in the search corpus.

[0026] In one implementation, each document in the training and search corpus is encoded in a known and consistent character encoding, such as 8-bit Uniform Transformation Format (UTF-8), which can encode any character in the Unicode standard (i.e., most known characters and ideographs). Documents that are in an inconsistent or unknown encoding are subject to encoding conversion. In one implementation, the corpus is a collection of documents from the Web found by a web crawler.

[0027] The language of each document in the training corpus is identified. Determining the language of each document can be explicitly part of process 100 (step 120). Alternatively the document's language can be part of the information contained in the training corpus. The language of a document or word does not necessarily correspond simply to natural languages. A language can include any distinguishable linguistic system defined by its orthography, syntax, lexicon or morphology. For example, Roman Indic, a roman transliterated equivalent of a group of languages (e.g., Bengali and Hindi), can be considered a separate language from either Bengali and Hindi in their conventional orthographic script.

[0028] The document language detection process uses statistical learning theories. In one implementation, it uses Naive Bayes classification models to calculate the likelihoods of possible classes and predicts the class that has the maximum likelihood. A class is a language/encoding pair that a document can be expressed in, for example, English/ASCII, Japanese/Shift-JIS, or Russian/UTF8. Some languages correspond to multiple classes because they can be encoded in multiple encodings, while some encodings correspond to multiple classes because they can be used to express multiple languages.

[0029] The Naive Bayes models are used to determine the most likely class or classes for a page of text based on the text and (optionally) a Universal Resource Locator (URL) of the page of text.

[0030] The encoding of a page of text is determined using a Naive Bayes model that predicts the maximum likelihood encoding based on pairings of the bytes that represent the text. If the URL of the page of text is available, the model also factors in the probability of a specific encoding given that the text came from a certain top level domain (i.e., the last part of the Internet domain name).

[0031] The text is converted from its original encoding into Unicode when performing language detection, and the language detection is performed using features. Typically, natural language words are the best features to use, so the text is segmented into words. A Naive Bayes model computes probabilities of individual words given a language and predicts the maximum likelihood language for the text based on the probabilities.

[0032] The Naive Bayes models can be trained and tested using a large sample of electronic documents in various encodings and languages. Training the Naive Bayes model is essentially calculating the probability of a feature given a language.

[0033] Document language identification is further described in U.S. patent application Ser. No. 60/793,708, entitled Identifying a Property of a Document, to inventor Xin Liu, filed on Apr. 19, 2006, the entire disclosure of which is incorporated here by reference.

[0034] The process 100 creates a dictionary containing each unique word found among all the documents in the training corpus (step 125). Each instance of a given word found in the corpus is counted according to the identified language of the document it was found in. The frequency of each word in each document language is recorded in the dictionary. For example, if hello is encountered 200 times—150 times within documents identified as English documents and 50 times within documents identified as German documents—then the hello dictionary entry records that hello was found in English and German documents and that it was found 150 and 50 times, respectively.

[0035] For each language, a pre-determined blacklist of characters can be defined. The blacklist of characters is a list of characters which would not normally occur in documents in that language. The blacklist of characters does not necessarily reflect strict inherent characteristics of the language. For example, ‘w’ does not occur in French words so it can be added to the French blacklist. However, borrowed and foreign words that contain a ‘w’ occur in French documents often enough that ‘w’ can be excluded from the French blacklist. The list can be determined manually in whole or in part. Alternatively, occurrences of characters in documents known to be in a particular language can be statistically analyzed to inform the manual process or to produce a blacklist of characters automatically.

[0036] Process 100 can use the blacklist of characters to determine whether a word found in the training corpus appears to violate the conventional rules of the language. Such a word is ignored, i.e., it is not inserted into the dictionary. For example, if “QqWwXxYy” is a blacklist of characters for Hungarian, then “xylophone” is ignored when it is found in a Hungarian document.

[0037] The process 100 maps each word entry in the dictionary to a common form for each language in which the word appears (step 130). Generally, the common form is a word that conforms to a simplified, standardized, canonical or otherwise consistent orthography, for example, words expressed without the use of accented characters. Process 100 maps each word according to pre-defined and language-specific mappings. For example, a mapping converts “éléphant”, found in a document identified as French, to “elephant”.

[0038] A word is mapped to a common form according to language-specific mappings. Every language-specific mapping is a collection of one or more character conversion maps. Each conversion map specifies one or more input characters and one or more output characters to which the one or more input characters are mapped. The process 100 replaces the maximal sequence (or prefix) of characters matching the input of a conversion map with the map's one or more output characters. Other characters are copied unchanged. For any given word, the result of this character conversion process generates the word's common form. A data structure designed to facilitate longest-prefix matching can be used to store language-specific mappings (e.g., a trie or prefix tree).

[0039] For example, “BOKa” from a Russian document is mapped to “BOa” (no change), while “BOa” in a Serbian document is mapped to “vodka”. Language specific conversion is intended to capture the expectations of the writers of those languages. This reflects that while Russian-writers are likely to provide “BOKa”, Serbian practice suggests that Cyrillic words are more often given as their Roman-transliterated equivalent in search queries.

[0040] A conversion map that specifies more than one input character is a special case of conversion for mapping words that contain collapsible digraphs. Collapsible digraphs are two-character combinations that, in some languages, can be represented as a single, often accented, character. For example, German convention suggests that if ‘Ü’ cannot be typeset, then ‘Ue’ or ‘UE’ is a suitable substitute. Therefore a German document can spell the word “über” as “ueber”. During mapping to a common form, a two-character conversion map will often collapse the collapsible digraph and de-accent the result. For example, in one implementation, German conversion maps convert both “ueber” and “über” to “uber”.

[0041] The process 100 creates a synonyms map (step 150) from: the common form mappings, the dictionary entries, and the entries' associated language statistics. Each distinct common form, as derived above, becomes a key in the synonyms map. Dictionary entries that map to a given key, using a mapping for each of the entry's languages, become the key's values. In the synonyms map, the dictionary entries will be called variants. Generally, each key is associated with multiple variants, each of which is associated with the variant's language statistics. Given the mapping in the above example, “BOa” is one key whose value refers to at least one variant “BOa”, associated with Russian (but not Serbian). Furthermore, “vodka” is another key whose value refers to at least one variant “BOa” associated with Serbian (but not Russian).

[0042] FIG. 2 illustrates one implementation of a process 200 for creating a synonyms map (step 150 of FIG. 1). The process 200 includes receiving common-form entries, as described above (step 210). Any common-form entry containing only one variant that is the same as its common form is omitted from the synonyms map (step 220). Such an entry does not provide synonyms for the common form.

[0043] The process 200 also removes any languages associated with a variant that have a frequency that does not exceed a pre-defined absolute threshold (step 230). The absolute threshold is pre-determined and specified on a per-language basis. This threshold is used to remove variants that are likely to be misspellings or mistakes in the training corpus. For a language that is well represented in the training corpus, a large threshold (e.g., 40 for English) will generally omit obscure misspellings. The threshold for a small language which is not well represented would be set lower (e.g., 10) to preserve legitimate but rare words. The threshold can be turned off (or set to 0) for languages which are poorly-represented in the corpus.

[0044] Within a particular language, process 200 omits variants for a key if the variant contains a collapsible digraph and its accented equivalent is not also a variant for the key (step 240).

[0045] Some variants can have different meaning depending solely on their accents. To avoid undesirable contamination of the synonyms map by such variants, language-specific blacklists of words can be defined. Each blacklist contains a list of words that should not be a variant associated with a given language. If the variant is on a language's blacklist, that language is de-associated from the variant. For example, if “the” is on the French blacklist, then no variant whose common form is “the” can be associated with the French language. This prevents confusion between the English “the” and the French “thé”.

[0046] For each key, the relative frequency of each variant among all the variants for a particular language is calculated (step 250). To calculate the relative frequency of any given variant in a given language, the number of times the variant occurs in the language is divided by the total number of occurrences of all variants in the same language for the same key. For example, if the key is “elephant”, and if “éléphant” occurs in English and French, 100 and 1000 times, respectively; and “eléphant” occurs in English and French 90 and 300 times, respectively, then the relative frequency of “éléphant” in English is 52% (i.e., 100/(100+90)). In one implementation, the relative frequency of each variant for each language is stored in the synonyms map.

[0047] From each variant in the synonyms map, the process 200 removes any languages where the language's relative frequency does not meet a pre-defined relative threshold (e.g., 10%) (step 260). The same threshold applies to all variants and all languages. Any variants that are not associated with at least one language are also removed from the synonym map (step 270).

[0048] For illustrative purposes the process 200 has been described as a process that alters an existing synonyms map, for example, by removing entries or variants from it. Alternatively, the same effect can be achieved during the initial construction of the synonyms map by not including certain entries or variants in the first place.

[0049] An illustrative example synonyms map is shown in FIG. 4. The illustration assumes that the corpus is represented by four languages: English, French, Roman Indic and Bengali. This map contains three keys, “elephant”, “liberte” and “nityananda”. Each key is associated with numerous variants. In particular the variant “nity.a-nanda” (410) appears in documents from the corpus that are identified as Roman Indic and Bengali. However the variant only occurs in each language 6 times. If an absolute threshold greater than 6 is specified for each language, then these languages and the variant would be removed from the synonyms map.

[0050] The variant “nit{dot over (y)}anānda” appears in three languages (430), according to the language's relative frequency, this variant is relatively minor compared to other variants in each language. If a relative frequency threshold of 10% is applied, these languages and the entire variant would be removed from the synonyms map. Assuming the same relative threshold for the “nityAnanda” variant, the association with the Bengali language (420) would also be removed. This variant and the rest of its language associations would remain since these other languages each occur frequently enough to exceed the assumed relative and absolute thresholds.

[0051] One of the useful things that can be done with a synonyms map is to use it to augment queries made to a search engine.

[0052] As shown in FIG. 3, a process 300 can be used to augment a query to incorporate synonyms from the synonyms map. In practice, the query that is received (step 310) often imperfectly describes the user's desired query. The user is constrained by the limitations of an input device and the inconvenience of accurately indicating the language of the query. The ideal synonyms are those that reflect what the user would have provided under ideal circumstances. Process 300 is intended to approximate the ideal synonyms by scoring variants in the synonyms map relative to the words in the query and the language intended by the user, which is approximated by the language of the query.

[0053] Process 300 determines the language of the interface that received the query (step 315). A user provides the query to an interface. The interface will have an interface language, that is, a language in which the interface presents information to the user, e.g., English, French, or Esperanto. However, the words within a query are not necessarily in the same language as the interface the query was provided to.

[0054] The process 300 identifies individual words from the query (step 320). The identification of words depends on the particular conventions of the query language. In Latin script languages, for example, words are delimited by spaces or other punctuation (e.g., ‘−’).

[0055] The process 300 determines which languages the query is likely to be in (step 325). In one implementation, the query language is determined in two parts: determining a likelihood that the query is in the language of the interface, e.g., a probability; and determining for each term in the query, a likelihood, e.g., a probability, that the term is in some particular language.

[0056] Determining whether the query is likely to be in the same language as the interface language can be done using past queries. If a past query delivered search results, the past query can be automatically classified as being in a particular language based on the language of the results that the user subsequently selected. It is reasonable to assume that the language of the query is the same as the language of the documents the user chose to view, especially if the presentation of choices includes snippets from the search results documents. A past query can also be manually inspected to determine its language. Both automatic and manual techniques can be combined: the queries that have been manually classified serve as seeds used during automatic determination to improve accuracy. Results of the automatic classifier can inform subsequent adjustment of the classifier. Manual seeding and adjustment of the query classifier can be iteratively repeated to further improve the accuracy. The current query, in its entirety, is matched with past queries received by the same interface, generating a likelihood score or a probability that the query is in the same language as the interface language.

[0057] The process 300 determines how often a term from the query occurs in the corpus within documents for each language. From the frequency counts, a vector is generated that, for each language, gives a likelihood score in the range of zero to one that the term is in the language. A score vector, e.g., a probability vector, is generated for each term in the query.

[0058] Words that appear in many different languages, for example, proper names (e.g., Internet), can unduly affect the score vector for the query. The scores of such words, if found among the query terms, can be arbitrarily set to suggest that the word is likely in the interface language. Alternatively, such words can be ignored.

[0059] The process 300 can further process each vector by smoothing it. In one implementation, while computing the vector, a small smoothing value s is added to reduce noise. For example, if term t occurs n times in language L and N times across k languages, then the probability that the term is in the language is smoothed to be P(L|t)=(n+s)/(k×s+N), rather than P(L|t)=n/N. The smoothing value can be selected depending on size of N and k. For example, s can be selected to increase as N increases and to decrease as k increases.

[0060] Query language identification is further described in U.S. patent application Ser. No. 60/793,677, entitled Query Language Identification, to inventor Fabio Lopiano, filed on Apr. 19, 2006, the entire disclosure of which is incorporated here by reference.

[0061] All of the vectors from the previous step are multiplied together. The resultant vector is multiplied by the probability (or score) that the query is in the language of the interface, producing a query probability (or score) vector. This query probability vector contains, for each language, a probability (or score) that the query is in the language. The language with the highest probability (or score) is selected as the query language that is attributed to the query.

[0062] The process 300 simplifies each word in the query (step 330). In simplifying each word, the process collapses digraphs, removes accents, and transliterates characters in each word. This is accomplished in exactly the same way as common forms were derived from the training corpus, as described above. However, the specific conversion maps used to simplify query words here are in some respects different from the conversion maps used in the creation of the synonyms map. In particular, simplifying each word is normally language independent.

[0063] In specific cases, however, the identified query language can affect how query words are simplified. This is particularly important when the result of word simplification makes no sense in the query language. For example, in Turkish ‘ue’ is a nonsensical substitution for ‘ü’, unlike in German. Simplifying “Türk” to “Tuerk” would be undesirable for a Turkish user.

[0064] In general, the simplified words from the query are used to look up and retrieve variants from the synonyms map using each simplified words as a key (step 340). Each variant is a potential synonym of the original query word. The relative frequency under a key of each variant within each language is used to estimate whether the variant is desirable as a synonym for the key in each language (step 350). This estimate is calculated by summing, for each language, the probability that the query is in the language multiplied by the relative frequency of the variant in that language. For example, consider when “éléphant” is a variant in English 52% of the time and a variant in French 77% of the time. Then for a query determined likely to be in English with a probability of 70% and French with a probability of 30%, the resultant estimate for “éléphant” is: 52%×70%+77%×30%=59.5%. If the calculated estimation exceeds a synonyms probability threshold (e.g., 50%), the variant is selected to augment the query. The particular synonyms probability threshold is selected to provide good results given the language statistics in the synonyms map and the probabilities provided by the query language classifier. In the special case that a variant, in the given language, is the result of collapsible digraphs, then the relative frequency of the variant is reduced (e.g., quartered) when calculating the variant's estimate. This penalty to the variant's relative frequency reflects the potential risk of having collapsed the variant's digraphs inappropriately.

[0065] Each selected variant is added to the query (step 360), unless the variant is a stop word and the variant does not appear in the probable query language: such variants are ignored. Each original term from the query is augmented with each of its selected variants. Each variant is appended as a conjunction with the original term. For example, the query “eléphant trunk” is augmented to “(eléphant or elephant or éléphant) trunk”, assuming that both elephant and éléphant are selected variants for elephant.

[0066] The process uses the augmented query to search a search corpus (step 370). The search corpus contains documents in their original, unaltered form. Except for the effects of augmenting of the query, searching and providing results from the corpus is not otherwise affected.

[0067] If the probable query language is an under-represented language in the search corpus (i.e., a small proportion of the total documents), then it can be undesirable to include variants from the synonyms map. Adding variants to the search query increases the risk of matching documents from outside the desired language, potentially overwhelming the results with foreign language documents. However, when the original query word contains only unaccented letters and does not contain collapsible digraphs (e.g., “ueber”, simplified to “uber”), then variants should be sought regardless of the probable query language. In one implementation the decision to include variants depends on the interface language rather than the query language.

[0068] FIG. 5A through FIG. 34 illustrate one implementation of the conversion maps used to map words in the training corpus or to simplify words in a search query. Each figure shows one or more named groups of conversion maps. Each conversion map is shown as one line in one column in the figures. A conversion map is shown with at least an input character and an output character, as discussed above. In addition, columns marked “UCS” show the hexadecimal value of a character's encoding according to the Universal Character Set (UCS). When a UCS value is not given, each character is one of the 95 printable ASCII characters.

[0069] The grouping of conversion maps is governed by convenience or convention rather than necessity: one or more conversion map groups can constitute the language-specific mapping for a particular language. The composition of groups for a particular language can depend on whether the groups are used to map words in the training corpus or to simplify words in a query.

[0070] FIGS. 5A, 5B, and 5C illustrate a generic group of conversion maps. Generally, these are safe conversion maps that are unlikely to conflict with the conversion maps pertaining to particular languages.

[0071] FIG. 6 illustrates a Russian group of conversion maps. This group is used to map words from Russian documents during generation of the synonyms map.

[0072] FIG. 7 illustrates a Macedonian group of conversion maps. This group is used to map words from Macedonian documents during generation of the synonyms map.

[0073] FIG. 8 illustrates a Ukrainian group of conversion maps. This group is used to map words from Ukrainian documents during generation of the synonyms map.

[0074] FIG. 9 illustrates a Greek group of conversion maps. This group is used to map words from Greek documents during generation of the synonyms map

[0075] As shown in FIG. 10 and FIG. 11, some conversion maps also specify the accented equivalent of the collapsed digraph (column headed “A.E.” in the figures). These maps have a two-character input, i.e., the collapsible digraph, and one output, the collapsed digraph. This information can be used to determine whether two characters (input) are collapsible digraphs. Alternatively, this information also indicates whether a particular character (output) can be the result of a collapsible diagraph.

[0076] FIG. 10 illustrates an Esperanto H/X-System group of conversion maps. This group is used to map words from Esperanto documents during generation of the synonyms map.

[0077] FIG. 11 illustrates a Ch and an ShZh groups of conversion maps. This group is composed with other groups during generation of the synonyms map and query term simplification.

[0078] FIG. 12 illustrates a Croatian group of conversion maps. This group is used to map words from Croatian documents during generation of the synonyms map. The Generic, Ch, ShZh, A-Umlaut, O-Umlaut, U-Umlaut, and Y-Umlaut groups are composed and used to simplify query terms that are identified as Croatian. The A-Umlaut, O-Umlaut, U-Umlaut, and Y-Umlaut groups are described below in reference to FIG. 23.)

[0079] FIG. 13 illustrates a Catalan group of conversion maps. This group is used to map words from Catalan documents during generation of the synonyms map.

[0080] FIG. 14 illustrates a Serbian group of conversion maps. This group is composed with the Croatian group and used to map words from Serbian documents during generation of the synonyms map. The Generic, A-Umlaut, O-Umlaut, U-Umlaut, Y-Umlaut, Ch, ShZh and Serbian groups are composed and used to simplify query terms that are identified as Serbian.

[0081] FIG. 15 illustrates a French group of conversion maps. This group is used to map words from French documents during generation of the synonyms map.

[0082] FIG. 16 illustrates an Italian group of conversion maps. This group is used to map words from Italian documents during generation of the synonyms map.

[0083] FIG. 17 illustrates a Portuguese group of conversion maps. This group is used to map words from Portuguese documents during generation of the synonyms map.

[0084] FIG. 18 illustrates a Romanian group of conversion maps. This group is used to map words from Romanian documents during generation of the synonyms map.

[0085] FIG. 19 illustrates a Spanish group of conversion maps. This group is used to map words from Spanish documents during generation of the synonyms map.

[0086] FIG. 20 illustrates a Dutch group of conversion maps. This group is used to map words from Dutch documents during generation of the synonyms map. The Generic, A-Umlaut, O-Umlaut, U-Umlaut, and Dutch-Y groups are composed and used to simplify query terms that are identified as Dutch.

[0087] FIG. 21 illustrates a Danish group of conversion maps. This group is used to map words from Danish documents during generation of the synonyms map.

[0088] FIG. 22 illustrates an English group of conversion maps. This group is used to map words from English documents during generation of the synonyms map.

[0089] FIG. 22 also illustrates a German group of conversion maps. This group is used to map words from German documents during generation of the synonyms map. The Generic, Y-Umlaut and German Umlaut groups are used to simplify query terms that are identified as German.

[0090] FIG. 22 also illustrates a Dutch-Y group of conversion maps. This group is composed with other groups to simplify query terms that are identified as Dutch.

[0091] FIG. 22 also illustrates a German Umlaut group of conversion maps. This group is composed with other groups to simplify query terms that are identified as German.

[0092] FIG. 22 also illustrates a Swedish group of conversion maps. This group is used to map words from Swedish documents during generation of the synonyms map. The Generic, U-Umlaut and Y-Umlaut groups are used to simplify query terms that are identified as Swedish or Finnish.

[0093] FIG. 23 shows four groups: A-Umlaut, O-Umlaut, U-Umlaut and Y-Umlaut groups. These groups are used in composition with other groups to simplify query terms.

[0094] FIG. 24 illustrates an Icelandic group of conversion maps. This group is used to map words from Icelandic documents during generation of the synonyms map.

[0095] FIG. 25 illustrates a Czech group of conversion maps. This group is composed with the ShZh group and used to map words from Czech documents during generation of the synonyms map. The Generic, A-Umlaut, O-Umlaut, U-Umlaut, Y-Umlaut and ShZh groups are used to simplify query terms that are identified as Czech.

[0096] FIG. 26 illustrates a Latvian group of conversion maps. This group is composed with the Ch and ShZh group and used to map words from Latvian documents during generation of the synonyms map. The Generic, A-Umlaut, O-Umlaut, U-Umlaut, Y-Umlaut, Ch and ShZh groups are used to simplify query terms that are identified as Latvian.

[0097] FIG. 27 illustrates a Lithuanian group of conversion maps. This group is composed with the Ch and ShZh group and used to map words from Lithuanian documents during generation of the synonyms map. The Generic, A-Umlaut, O-Umlaut, U-Umlaut, Y-Umlaut, Ch and ShZh groups are used to simplify query terms that are identified as Lithuanian.

[0098] FIG. 28 illustrates a Polish group of conversion maps. This group is used to map words from Polish documents during generation of the synonyms map.

[0099] FIG. 29 illustrates a Slovakian group of conversion maps. This group is composed with the ShZh group and used to map words from Slovakian documents during generation of the synonyms map. The Generic, A-Umlaut, O-Umlaut, U-Umlaut, Y-Umlaut and ShZh groups are composed and used to simplify query terms that are identified as Slovakian

[0100] FIG. 30 illustrates a Slovenian group of conversion maps. This group is composed with the Ch and ShZh group and used to map words from Slovenian documents during generation of the synonyms map.

[0101] FIG. 31 illustrates an Estonian group of conversion maps. This group is composed with the Ch and ShZh group and used to map words from Estonian documents during generation of the synonyms map. The Generic, A-Umlaut, O-Umlaut, U-Umlaut, Y-Umlaut, Ch and ShZh groups are composed and used to simplify query terms that are identified as Estonian.

[0102] FIG. 32 illustrates a Hungarian group of conversion maps. This group is used to map words from Hungarian documents during generation of the synonyms map.

[0103] FIG. 33 illustrates an Esperanto group of conversion maps. This group is composed with the Esperanto HX-system group and used to map words from Esperanto documents during generation of the synonyms map. The Generic, A-Umlaut, O-Umlaut, U-Umlaut, Y-Umlaut and Esperanto HX-system groups are composed and used to simplify query terms that are identified as Esperanto.

[0104] FIG. 34 illustrates a Turkish group of conversion maps. This group is used to map words from Turkish documents during generation of the synonyms map.

[0105] The table below illustrates which conversion map groups can be used to map words during generation of the synonyms map. Each language is specified with its blacklist of characters (as discussed above), and one or more conversion map groups which together constitute the suite of conversion maps used while deriving a common form from words in the training corpus.

[0106]

Language	Character Blacklist	Conversion Maps
Catalan	kw	Catalan
French		French
Italian	jkwxy	Italian
Portuguese	kw	Portuguese
Romanian	kqwy	Romanian
Spanish	w	Spanish
Danish		Danish
Dutch		Dutch
English		English
German		German
Icelandic	cqw	Icelandic
Swedish		Swedish
Estonian	qwxy	Ch, ShZh, Estonian
Finnish	bcfqwxz
Hungarian	qwxy	Hungarian
Greek		Greek
Turkish	qwx	Turkish
Croatian	qwxy	Croatian
Czech	qwx	ShZh, Czech
Latvian	qwxy	Ch, ShZh, Latvian
Lithuanian	qwxy	Ch, ShZh, Lithuanian
Macedonian		Macedonian
Norwegian		Danish
Polish	qvx	Polish
Russian		Russian
Serbian	qwxy	Croatian, Serbian
Slovak	qw	ShZh, Slovakian
Slovenian	qwxy	Ch, ShZh, Slovenian
Ukrainian		Ukrainian
Esperanto	qwxy	Esperanto (hx-system), Esperanto

[0107] FIG. 35 is a schematic diagram of a search engine 3550 that receives multilingual queries and provides multilingual results in response. The system 3550 is generally equipped to obtain information about the occurrences and frequency of terms from various sources, and to generate search results in response to queries based upon an analysis of word use in such sources. Such sources could include, for example, multilingual documents and files found on the Internet.

[0108] The system 3550 includes one or more interfaces 3552 each in a different language. The interfaces allow users to use and interact with the services of the search engine. In particular, the interface receives queries from users. A query includes a list of words where each word can be in any language. None of the words in the query need be in the language of the interface. The specific interface 3552 which receives a user's query is dependent on the user's choice of interface.

[0109] System 3550 can be communicatively connected to a network such as the Internet 3558, and thereby can communicate with various devices connected to the Internet such as wireless communication devices 3562, and personal computers 3564. The communication flow for any device can be bidirectional so that system 3550 receives information (e.g., queries or the contents of documents) from the devices and can also send information (e.g., results) to the devices.

[0110] Queries received by the interface 3552 are provided to a query processor 3566. The query processor 3566 processes the query, optionally augments it, and passes it on to another component of system 3550. For example, query processor 3566 can cause the retrieval system 3570 to generate search results corresponding to the query. Such a retrieval system 3570 can use data retrieval and search techniques like those used by the Google PageRank™ system. The results generated by retrieval system 3570 can then be provided back to the original querying device.

[0111] The system 3550 can rely on a number of other components for its proper operation. For example, the system 3550 refers to a search corpus 3572 of documents each time a request is made. The search corpus can be indexed to make searching more efficient. The search corpus can be populated using information collected from documents found on the Web (e.g., by a web crawler). The documents can also be stored in a training corpus 3574 for subsequent processing.

[0112] The training corpus 3574 can be processed by a synonyms processor 3580. The synonyms processor 3580 can generate a synonyms map 3585 from the training corpus 3574. The synonyms map 3585 can be used by the query processor 3566 to augment search queries with synonyms.

[0113] Embodiments of the invention and all of the functional operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the invention can be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a computer-readable medium for execution by, or to control the operation of, data processing apparatus. The computer-readable medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more of them. The term “data processing apparatus” encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them. A propagated signal is an artificially generated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus.

[0114] A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub-programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

[0115] The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

[0116] Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto-optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio player, a Global Positioning System (GPS) receiver, to name just a few. Computer-readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

[0117] To provide for interaction with a user, embodiments of the invention can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input.

[0118] Embodiments of the invention can be implemented in a computing system that includes a back-end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front-end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the invention, or any combination of one or more such back-end, middleware, or front-end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet.

[0119] The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

[0120] While this specification contains many specifics, these should not be construed as limitations on the scope of the invention or of what may be claimed, but rather as descriptions of features specific to particular embodiments of the invention. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.

[0121] Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

[0122] Thus, particular embodiments of the invention have been described. Other embodiments are within the scope of the following claims. For example, the actions recited in the claims can be performed in a different order and still achieve desirable results.