CROSS-ORTHOGRAPHY FUZZY STRING COMPARISONS

Fuzzy string comparison between a first textual string of a first orthography and a second textual string of a second orthography is provided. The first and second textural strings are transliterated to a first phonetic spelling and a second phonetic spelling, respectively. Application of constraints of the first orthography on the first phonetic spelling and of constraints of the second orthography on the second phonetic spelling is detected. The detected constraints of the first orthography on the first phonetic spelling are reversed to generate a first revised phonetic spelling, and the detected constraints of the second orthography on the second phonetic spelling are reversed to generate a second revised phonetic spelling. The first revised phonetic spelling and the second revised phonetic spelling are compared to generate a similarity score for the first textual string and the second textual string.

CROSS-ORTHOGRAPHY FUZZY STRING COMPARISONS

Background

The ability to perform searches of proper names and locations using any language in a query presents many benefits and yet many challenges. In an example, a user submits a Mandarin-language (e.g., Standard Mandarin Language) query to a database containing English-language (e.g., US English Language) documents. The user would benefit greatly if the search tool could transliterate the query between the two languages and perform fuzzy string comparisons to generate accurate search results matching the original query (proper names and locations are seldom translated and are most often transliterated). However, the accuracy of such transliterations and comparisons between different languages can induce inaccuracies. As a result, the user's search of an English-language database using the Mandarin-language query is likely to provide inadequate results without additional processing.

SUMMARY

The described technology provides fuzzy string comparison between a first textual string of a first orthography and a second textual string of a second orthography. The first textural string and the second textual string are transliterated to a first phonetic spelling and a second phonetic spelling, respectively. Application of one or more constraints of the first orthography on the first phonetic spelling and of one or more constraints of the second orthography on the second phonetic spelling is detected. The detected constraints of the first orthography on the first phonetic spelling are reversed to generate a first revised phonetic spelling, and the detected constraints of the second orthography on the second phonetic spelling are reversed to generate a second revised phonetic spelling. The first revised phonetic spelling and the second revised phonetic spelling are compared to generate a similarity score for the first textual string and the second textual string.

DETAILED DESCRIPTIONS

The described technology provides improved comparison between strings of different languages (cross-orthographic comparisons). An orthography is a set of conventions for writing a language, including without limitation norms of spelling, hyphenation, capitalization, word breaks, emphasis, and/or punctuation. Aspects of one or more implementations for the described technology may include:

Comparing phoneme feature vectors rather than individual characters of two strings from different languages Reversing phonological constraints of a language to the transliteration of an input string in that language Applying orthographical constraints of both input string languages to the transliteration of an input string

Using the aspects and/or various combinations listed above, the described technology improves the reliability and accuracy of fuzzy-matching of strings across orthographies and across differing transliteration schemes.

FIG.1illustrates a search engine100with an example cross-orthography fuzzy string comparison engine102. InFIG.1, a search query104(containing the Mandarin text string “”) is input to the search engine100for use in searching an English language database106.

Such a search involves cross-orthographic comparison, a challenging operation that can nevertheless be useful in other applications as well, including without limitation semantic processing, spam filtering, intrusion detection, and text and speech translation between different languages. In the case of a search engine, the cross-orthographic string comparison may be employed to categorize and organize data efficiently during the search. Categorization is accomplished based at least in part on matching the search query keywords to related keywords in the searched data.

In the illustrated search engine100, the comparison engine102performs cross-orthographic fuzzy string comparison using one or more of reversing phonological of a language to a transliterated phonetic string of search query104in that language and/or applying orthographical constraints of both languages to each input string and then comparing phoneme feature vectors of processed phonetic spellings the Mandarin language search query104and strings in the English language database106. Based on the scoring of the cross-orthographic string comparisons performed by the comparison engine102, the search engine100outputs the cross-orthographic search results108(e.g., a ranked listing of similar strings from the English language database106).

FIG.2illustrates an example cross-orthography fuzzy string comparison engine (comparison engine200). The comparison engine200includes a transliterator202, a constraints normalizer204, and a string comparator206. Such components may be implemented in software executable on one or more hardware processors, in hardware circuitry, or in combinations thereof.

In the process of executing a cross-orthography search, for example, a search engine performing a cross-orthography fuzzy string comparison using the comparison engine200. InFIG.2, assume a search query208(including the string “”) has been input to the search engine. One or more of the records of the English language database that is to be searched includes a string210(“Bill Clinton”). For the purposes of this description, it is assumed that the search query208and the string210should have a high similarity score from a comparison operation, indicating a strong match. Other string pairings may have higher or lower similarity scores from a comparison operation. As such, the comparison engine is tasked with generating a similarity score220for the string pairs, represented by the following function:

The described technology implements various combinations of reversed phonological constraints and applied orthographical constraints. In linguistics, such phonological constraints may be consistent with the linguistic model referred to as “Optimality Theory” or “OT,” which proposes that observed forms of languages arise from an optimal satisfaction of conflicting linguistic constraints rather than from strict adherence to a set of linguistic rules. As such, OT models grammars as linguistic systems that provide mappings from textual inputs to phonological outputs. It should be understood that the described technology need not be limited to implementations of the OT model and that implementation in the context of other constraint-based models may also be contemplated.

In some implementations, the OT model assumes that such phonological constraints are universal in definition, although they may be ranked differently for different grammars. As such, constraints may be ranked on a per-language basis. For example, two competing OT constraints on the same syllable often only result in the higher ranking constraint being applied. The term “phonological constraints” are considered with associated per-language rankings, and in the OT model, there are two basic types of constraints (faithfulness constraints and markedness constraints). Faithfulness constraints require that the observed surface form (the output) match the underlying or lexical form (the input) in some particular way. As such, faithfulness constraints require identity between input and output forms.

Example faithfulness constraints for a given orthography may include one or more of the following:The output must preserve all segments present in the inputThe output must preserve the linear order of segments in the inputOutput segments must have counterparts in the inputOutput segments and input segments must share values for voice

Markedness constraints impose requirements on the structural well-formedness of the output. Example markedness constraints for a given orthography may include one or more of the following:Any Vowel must not be nasalAny Syllable must not have a codaAny Obstruent in coda position must not be voicedAny Sonorant must be voicedAny Syllable must have an onsetAny Obstruent after a nasal must be voiced

In contrast, the term “orthographical constraints” refers to limitations upon the written representation of words in a given orthography. As such, the term “orthographical constraints” refers to restrictions on the way in which letters may be arranged in the written form of a language. For example, “ck” does not occur at the beginnings of English words. While many orthographical constraints exist in various languages, such constraints that affect pronunciation are less common than phonological constraints (when an orthographical constraint has no effect on the transliteration into a phonetic alphabet, it has no cascading effect on subsequent phonetic comparisons). However, if such a misspelling were to occur and the transliteration treated this as the “k” sound, this spelling error would have no more impact on downstream comparison than any other spelling error. Still, there are orthographical constraints that do affect pronunciation. For example, Standard Arabic spells out words and optionally omits low vowels (English also has only two low vowels: IPA:/α/ and IPA:/æ/, as in pot and pat). If either of these vowels were part of the normal pronunciation of an Arabic word, the transliteration process might not include these sounds if not present in the incoming Arabic script text. Normalizing this type of orthographical constraint involves an insertion of the missing low vowel at the proper insertion point after phonetic alignment and detection has occurred.

To implement the search, the comparison engine200processes the string of the search query208and the strings in the English language database according to the described technology and then executes a fuzzy string comparison to identify matches between the search query208and the content of the English language database. Referring to the three phases suggested inFIG.2(transliteration, constraints application, and comparison), the first two phases of the comparison operation condition the input data, performing a phonetic transliteration, reversing phonological constraints on the strings from their respective orthographies, and applying orthographical constraints on the strings from their respective orthographies. A comparison phase performs vectorized comparisons at the phoneme level, thus obfuscating away orthographical and phonological noise between languages.

In the first phase, the transliterator202receives the search query208and the string210and transforms both into their respective phonetic spellings, shown as a phonetic spelling212and a phonetic spelling214. In various implementations, the transliterator202may use the International Phonetic Alphabet (IPA), ARPAnet, or other systems of phonetic notation, which represent phonemes and/or allophones of one or more languages with distinct sequences of ASCII characters. As shown inFIG.2, the example transliteration of “” results in the notation “bi er ke lin dun”, and the example transliteration of “Bill Clinton” results in the notation “bIl klIn tn”. While these results appear to be somewhat similar, they are different enough to potentially result in a low enough similarity score that the two strings, which are described above as a strong match, are nevertheless identified as a poor match. To address this concern, the described technology improves the accuracy of such similarity scores over this type of transliteration when applied to cross-orthography fuzzy string comparisons. In at least one implementation, the characters of the phonetic spelling212and the phonetic spelling214are vectorized into feature vectors for each input string before the next phase. The vectorization process deterministically converts a phonetic character into a Boolean array. Each of these Boolean values is called a “feature.”

The next phase detects and reverses one or more phonological constraints that have been applied to the phonetic spelling212and the phonetic spelling214in their respective orthographies. The constraints normalizer204reverses phonological constraints based upon detection logic: detected constraints are reversed when detected. First, each language has a tunable parameter (implemented as a detection condition) for a ranking threshold that applies across the language for phonological constraints. Effectively, the satisfaction of the detection condition of a constraint by a string triggers the reversal of the language's phonological constraints on that strong, independent of a ranking threshold for each constraint. In other words, on a per-language basis, the reverse constraints are either triggered or not triggered. (Per-language ranking typically only affects inclusion versus exclusion in the detection logic for that language.) The constraints need not be ranked relative to one another. Instead, the pair of feature vectors of the string drive (and the satisfaction of the detection condition) define whether the constraint should be reversed on that string. The output of the constraints normalizer204includes a revised phonetic spelling for each input string.

In some implementations, in addition to reversal of phonological constraints, the constraints normalizer204detects and reverses orthographical constraints of both orthographies to both input strings with the goal of further normalizing the two revised phonetic spellings prior to comparison. As will be described in more detail with respect toFIGS.3and4, reversals of orthographical constraints to both input languages are applied to the revised phonetic spellings of both input strings and are incorporated therein.

The constraints normalizer204, therefore, outputs processed versions of the transliterated (e.g., IPA) forms of the search query208and the string210from the English language database (i.e., the phonetic spelling212and the phonetic spelling214, respectively). The processed version of the phonetic spelling212is depicted as revised phonetic spelling216(“birklindun”), and the processed version of the phonetic spelling214is depicted as revised phonetic spelling218(“bIlklIntn”), which even visually appears more similar than the raw phonetic spellings (e.g., the phonetic spelling212and the phonetic spelling214).

The string comparator206receives the revised phonetic spelling216and the revised phonetic spelling218and executes similarity evaluations of the revised phonetic spelling216and the revised phonetic spelling218, such as using a cosine similarity function, although other similarity evaluations may be employed including without limitation a Jaccard similarity function, a Gaussian similarity function and a radial basis function (RBF) kernel. The output of the string comparator206includes a similarity score that represents a measure of the similarity between the revised phonetic spelling216and the revised phonetic spelling218. Typically, the similarity score is a value between 0 and 1 or 0 and 100, although other scales may be employed.

It should be understood from even a casual review of the phonetic spellings212and214, as compared to the revised phonetic spelling216and218, that the revised phonetic spellings appear more similar than the phonetic spellings. Reversal of phonological constraints and orthographical constraints on the phonetic spellings obfuscate away orthographical and phonological noise between the individual languages, resulting in a more accurate similarity score than would typically be obtained from the phonetic spellings212and214alone.

FIG.3illustrates operations300of an example cross-orthography fuzzy string comparison engine. The described technology is concerned with one or more linguistic concepts, including without limitation phonetic features, phonological constraints, and orthographical constraints, including the ranking of constraints on a per-language basis. The technology also recognizes the benefit of faithfulness constraints by providing two faithfulness constraint scores, which provide a more accurate transliteration result than prior approaches:The first score uses all constraint detection and reversal logic, obfuscating away all the noise induced by constraintsThe other score [faithfulness] compares unrevised phonetic spellings

Additionally, in some applications, orthographical constraints of each orthography are detected and reversed in each input string. Typically, the reversal of orthographical constraints is performed after the reversal of phonological constraints, although other implementations may reverse or intersperse these reversals.

In one implementation, the linguistic concepts are implemented using functions executed in a predefined sequence to process the strings prior to comparison, although other implementations may change the ordering in some manner. A comparator( ) function is used for dependency injection, allowing for customization of how character-level feature vectors are deemed similar. In one implementation, a hash map is used in a vectorizing operation to convert characters into feature vectors representing each string, although other methods may be employed.

Example functions are provided below in the context of the operations300for use in at least one implementation of the described technology. It should be understood, however, that different functions may be employed within the scope of the claims.

A transliteration operation302receives the string304(“”) and the string306(“Bill Clinton”) and transforms them into phonetic spellings, such as into IPA form. The function description provided below describes example functionality capable of performing this operation.

Function: TextToIPA(text, lang): This function converts any supported language/orthography into IPA (although other language models may be employed). If the language parameter “lang” is not supplied, the language may be automatically detected based upon the orthography and/or the actual text. In some implementations, beyond transliteration into IPA, this function marks boundaries between syllables, which may be used when reversing phonological constraints. Marking syllable boundaries is also called “segmenting,” as syllables are sometimes known as segments.

A vectorizing operation308(e.g., performed by a vectorizer, not shown) receives the phonetic spellings output from the transliteration operation302and converts each character of the phonetic spellings into a vector in a vector space. The function description provided below describes example functionality capable of performing this operation.

Function: Vectorizelipal: This function employs a hash map that takes an IPA character as input and vectorizes it into an unsigned integer representation of the character with 64 bits. Each bit is treated as a dimension in the vector, providing 64 dimensions of features per character (e.g., each dimension is a single bit: zero or one). Alternative vectorizing functions may be employed.

A detection operation310executes detection logic that detects whether a phonological constraint has been applied to each string in its original orthography. The detection operation310evaluates feature vectors (corresponding to individual characters in the transliterated strings) to determine whether individual phonemes, syllables, and other linguistic aspects of the phonetic spelling satisfy one or more detection logic conditions (e.g., such as those example detection logic conditions shown in the middle column of the table below). If so, the detection operation310determines that a phonological constraint had been applied within the string, word, or syllable, and a reversal operation312reverses the application of the phonological constraint in the transliterated string (e.g., a phonetic spelling), such as applying the action listed in the rightmost column of the table below.

Table 1 provides a detection logic/reversal mapping for six example constraints:

Table 1 above uses known linguistics terminology, such as coda, obstruent, sonorant, onset, and voice, which are further described as follows. The coda is defined as a final consonant phoneme of a syllable (e.g., /L/ is the consonant phoneme in the single-syllable word “Bill”). Syllables that do not end with a consonant sound have no coda. Many languages, such as Chinese, forbid a coda on most syllables. Other languages, such as English, generate a liberal application of codas on most words in any syllable. This impedance mismatch is what motivates phonological constraint reversal in the constraint normalization process. In effect, phonological constraint reversal eliminates comparison noise induced by language-specific phonological constraints.

An obstruent is a speech sound such as [k], [], or [f] that is formed by obstructing airflow. Obstruents contrast with sonorants, which have no such obstruction and so resonate. All obstruents are consonants, but sonorants include vowels as well as consonants. In phonetics and phonology, a sonorant or resonant is a speech sound that is produced with continuous, non-turbulent airflow in the vocal tract; these are the manners of articulation that are most often voiced in the world's languages. Vowels are sonorants, as are nasals like [m] and [n], liquids like [l] and [r], and semivowels like [j] and [w]. This set of sounds contrasts with the obstruents (stops, affricates, and fricatives).

The onset is defined as a final consonant phoneme of a syllable (e.g., /B/is the consonant phoneme in the single-syllable word “Bill”). Syllables that do not begin with a consonant sound have no onset or have a zero onset. Most syllables of most languages have an onset. Syllables without an onset may be said to have a zero onset. Voice is a feature that indicates whether the vocal cords are vibrating or not. When the vocal cords are vibrating, a phoneme is said to have voice. Otherwise, it is said to have no voice (e.g., /v/ and /f/ phonemes differ only by voice. /v/ has voice. /f/ has no voice).

The function described below provides an example implementation that performs both the detection operation310and the reversal operation312, although they may be implemented in two or more different functions in other designs. In some implementations, the ReversePhonologicalContraints function and/or the ReverseOrthographicalConstraints function are implemented in a constraints normalizer, although other allocations of these functions may be employed.

Function: ReversePhonologicalContraints(ipa1, lang1, ipa2, lang2): Feature vectors of ipa1 and ipa2 are generated (or alternatively, passed in to the function). Phonological constraints of a source language are applied (and dimensions are updated) to feature vectors of the input strings. With respect to certain phonological constraints, for example, an IPA character (representing a phoneme) can be inserted or deleted from the array of feature vectors to reverse a phonological constraint. Since OT-based phonological constraints are defined as characteristics that are constrained to happen within the orthography, the reversal operation recasts each of these phonological constraints as a detectable effect that can be reversed.

For example, referring to Table 1, if a feature vector representing a vowel in the input string does not include an IPA character representing a nasal sound (as determined by the detection operation310that executes the detection logic in the first substantive row of Table 1, then the reversal operation312executes the reversal action described in the last column of that row (e.g., adding an IPA character representing a nasal sound to the vowel). In another example, referring again to Table 1, if a syllable of a feature vector with no onset has an IPA onset character Inserted (as determined by the detection operation310that executes the detection logic in the fifth substantive row of Table 1, then the reversal operation312executes the reversal action described in the last column of that row (e.g., removing the IPA onset character from the syllable).

As such, the detection operation310and the reversal operation312evaluates and process elements of the input string based on detection logic and reversal instructions, respectively. In other implementations, the detection operation310may also detect orthographical constraints, which are reversed in another reversal operation314.

In addition to reversing phonological constraints in an input string, in some implementations, the reversal operation314reverses orthographical constraints of both orthographies to the input string. Again, orthographical constraints refer to restrictions on the way in which letters may be arranged in the written form of a language. For example, “ck” does not occur at the beginnings of English words. Accordingly, if “ck” is detected at the beginning of the phonetic spelling of an input string, the application operation314replaces the “ck” with a IPA:/k/. In one implementation, the detection logic for the reversal of orthographical constraints is included in the reversal operation314, although other implementations may remove the detection logic into a separate operation.

Function: ReverseOrthographicalConstraints(ipa, lang1, lang2): Orthographical constraints of the source languages lang1 and lang2 are detected and reversed (and the features are updated) to feature vectors of the phonetic spelling ipa. For example, one known orthographical constraint is unique to the Arabic language in written form: short vowels are implied between consonants but not written. This constraint implies that all short vowels might be absent from text that originated as an Arabic string. Orthographical constraints for both languages are reversed in the phonetic spellings of both input strings. As such, if one of the input strings is in Arabic, the reversal operation314adds short vowels between consonants using the other comparison string as a guide to determine the specific low vowel to be inserted. Additional orthographical constraints of the source languages lang1 and lang2 can also be reversed in the phonetic spellings of each input string. In one implementation, the reversal of orthographical constraints is executed after the reversal of phonological constraints, although other implementations may adjust the order according to design preferences.

Function: Conflate(ipa): A conflation operation316(e.g., performed by a conflator, not shown) deletes all syllable markers (e.g., IPA syllable boundary markers) to conflate the segments of the phonetic spellings of each input string.

After the processing of the phonetic spellings of each input string, including one or more of transliteration, vectorization, phonological constraint detection, phonological constraint reversal, orthographical constraint reversal, and conflation, the resulting feature vectors of characters in the revised phonetic spellings of the input strings are pair-wise compared to generate a similarity score320for the input string pair, such as by executing the example Compare( ) function below.

Function: Compare(ipa1, ipa2, comparator): After vectorizing each IPA character of each revised phonetic spelling into a feature-vector, a comparison operation318(implemented in one example by a Compare( ) function) perform per-character similarity calculation using the comparator( ) function passed in as a parameter. Dictionary spellings322are input to the comparison operation318as an input to the similarity function (e.g., a cosine similarity function, a Jaccard similarity function).

In one implementation, 64 dimensions are sufficient to represent phonological markedness and other phonological features, although other dimensions are also contemplated, such as 128 dimensions. Each character is compared for similarity using its relative position within the other string. Notwithstanding, characters themselves are not strictly compared in at least one implementation. Instead, the feature vectors that represent the two characters within each IPA string are compared via the comparator function.

In short, the comparison operation318performs a similarity function on each IPA character using the character's corresponding feature vector in the other comparison string and generates a similarity score for each feature vector. The scores are summed for all feature vectors. The resulting similarity score returned by Compare( ) function is the summation divided by the number of candidate feature vectors. The character comparator itself is specified in an input parameter to the Compare( ) function. Per-character feature-vectors can be deemed similar when the comparison operation318deems them to be similar. An example comparator function is cosine similarity, defined as:

By utilizing an integer to represent a vector, the described technology streamlines processing overhead, obviating the need for actual arrays and thus minimizing object instantiations. This compact representation is designed to optimize performance in some implementations.

In one implementation, each invocation of a comparator function returns two scores:Phonetic faithfulness scores with relaxation neither upon phonological constraints nor upon orthographical constraints (0 to 10000)Constraint-relaxation score (0 to 10000)

There are two levels of comparison in both scores:character granularity: cosine similarity (−1.0<=similarity<=1.0)// or Jaccard, or other // normalized to 0-10000string_granularity: scoring is a roll-up of character similarity // average of all character scores aligned via MPS

The comparison operation318provides a comparison score that indicates similarity between two phonemes. A phoneme is represented initially as IPA (International Phonetic Alphabet) and later as a feature vector represented as an array of bits. For the sake of compactness and performance, in one implementation, each feature vector is represented as an unsigned integer (here, the number of bits that compose the unsigned integer indicates the number of dimensions in the feature vector. As 128-bit integers are supported on modern computing systems, the number of dimensions supported in a 64-bit unsigned integer is adequate to represent as many features as will be required to represent individual phonemes). The comparison scores for each phoneme pair are summed to yield the similarity score320for the two input strings.

Cosine Similarity, Jaccard Similarity, or a custom comparator is passed as a function parameter to the Compare( ) function using a dependency injection pattern. Any similarity method can be utilized.

Pseudo-code for implementing an example comparison operation318is provided below, although it should be understood that alternative logic may be employed. Also, featureVector variables and variables of the form similar to elv and clv are arrays of vectors that store the per-character feature vectors corresponding to each string. For example, in one implementation, each character is converted into an integer that represents up to 64 dimensions, although greater or fewer dimensions may be represented in other implementations.

An example implementation of a transliterator (Phase 1) on the two strings “Bill Clinton” and “” to IPA may be described as follows, where the feature vectors of the two strings are indicated as “elv” and “clv”:

An example implementation of the detection operation310, the reversal operation312, and the reversal operation314can be described by the functions calls below (wherein the detection operation310and the reversal operation312are both included in the ReversePhonologicalConstraints( ) function):

An example implementation of the conflation operation316and the comparison operation318can be described by the function calls below:

FIG.4illustrates an example computing device for use in cross-orthography fuzzy string comparison. The computing device400may be a client device, such as a laptop, mobile device, desktop, tablet, or a server/cloud device. The computing device400includes one or more processor(s)402, and a memory404. The memory404generally includes both volatile memory (e.g., RAM) and nonvolatile memory (e.g., flash memory). An operating system410resides in the memory404and is executed by the processor(s)402.

In an example computing device400, as shown inFIG.4, one or more modules or segments, such as applications450, a transliterator, a constraints normalizer, a string comparator, and other modules are loaded into the operating system410on the memory404and/or storage420and executed by processor(s)402. The storage420may store strings, feature vectors, dictionary strings, per-character comparison scores, per-string similarity scores, and other data and be local to the computing device400or may be remote and communicatively connected to the computing device400. In one implementation, a transliterator, a constraints normalizer, a string comparator, and other modules may include circuitry to perform intended functions. In particular, in one implementation, components of the cross-orthography fuzzy string comparison engine may be implemented entirely in hardware or in a combination of hardware circuitry and software.

The computing device400includes a power supply416, which is powered by one or more batteries or other power sources, and which provides power to other components of the computing device400. The power supply416may also be connected to an external power source that overrides or recharges the built-in batteries or other power sources.

The computing device400may include one or more communication transceivers430, which may be connected to one or more antenna(s)432to provide network connectivity (e.g., mobile phone network, Wi-Fi®, Bluetooth®) to one or more other servers and/or client devices (e.g., mobile devices, desktop computers, or laptop computers). The computing device400may further include a network adapter436, which is a type of communication device. The computing device400may use the adapter and any other types of communication devices for establishing connections over a wide-area network (WAN) or local-area network (LAN). It should be appreciated that the network connections shown are exemplary and that other communications devices and means for establishing a communications link between the computing device400and other devices may be used.

The computing device400may include one or more input devices434such that a user may enter commands and information (e.g., a keyboard or mouse). These and other input devices may be coupled to the server by one or more interfaces438, such as a serial port interface, parallel port, or universal serial bus (USB). The computing device400may further include a display422, such as a touch screen display.

An example method of fuzzy string comparison between a first textual string of a first orthography and a second textual string of a second orthography is provided. The method includes transliterating the first textual string to a first phonetic spelling and the second textual string to a second phonetic spelling, detecting application of one or more constraints of the first orthography on the first phonetic spelling and of one or more constraints of the second orthography on the second phonetic spelling, reversing the detected constraints of the first orthography on the first phonetic spelling to generate a first revised phonetic spelling and the detected constraints of the second orthography on the second phonetic spelling to generate a second revised phonetic spelling, and comparing the first revised phonetic spelling and the second revised phonetic spelling to generate a similarity score for the first textual string and the second textual string.

Another example method of any preceding method is provided, further including vectorizing the first phonetic spelling and the second phonetic spelling, wherein the reversing operation and the comparing operation are performed on vectorized forms of the first phonetic spelling and the second phonetic spelling.

Another example method of any preceding method is provided, wherein the reversing operation includes reversing one or more phonological constraints of the first orthography on the first revised phonetic spelling and one or more phonological constraints of the second orthography on the second revised phonetic spelling, wherein the comparing operation is performed on the first revised phonetic spelling and the second revised phonetic spelling after the reversal of the one or more phonological constraints.

Another example method of any preceding method is provided, wherein the reversing operation includes reversing one or more orthographical constraints of the first orthography on the first revised phonetic spelling and one or more orthographical constraints of the second orthography on the second revised phonetic spelling, wherein the comparing operation is performed on the first revised phonetic spelling and the second revised phonetic spelling after the reversal of the one or more orthographical constraints.

Another example method of any preceding method is provided, further including deleting one or more syllable boundaries in the first revised phonetic spelling and the second revised phonetic spelling, wherein the comparing operation is performed on the first revised phonetic spelling and the second revised phonetic spelling after deletion of one or more syllable boundaries.

Another example method of any preceding method is provided, wherein the comparing operation includes executing a similarity function between the first revised phonetic spelling and the second revised phonetic spelling, wherein the similarity function is pair-wise executed on each feature vector corresponding to each character of the first revised phonetic spelling and the second revised phonetic spelling to generate per-character output scores.

Another example method of any preceding method is provided, wherein the first textual string is a search query and the second textual string is included in data to be searched, and further including outputting a ranked listing of the data to be searched based on the similarity score for the first textual string and the second textual string and other similarity scores between the first textual string and other strings in the data to be searched.

An example system for fuzzy string comparison between a first textual string of a first orthography and a second textual string of a second orthography is provided. The system includes one or more hardware processors, a transliterator executable by the one or more hardware processors and configured to transliterate the first textual string to a first phonetic spelling and the second textual string to a second phonetic spelling, a constraints normalizer executable by the one or more hardware processors and configured to detect application of one or more constraints of the first orthography on the first phonetic spelling and of one or more constraints of the second orthography on the second phonetic spelling and to reverse the detected constraints of the first orthography on the first phonetic spelling to generate a first revised phonetic spelling and the detected constraints of the second orthography on the second phonetic spelling to generate a second revised phonetic spelling, and a string comparator executable by the one or more hardware processors and configured to compare the first revised phonetic spelling and the second revised phonetic spelling to generate a similarity score for the first textual string and the second textual string.

Another example system of any preceding system is provided, further including a vectorizer executable by the one or more hardware processors and configured to vectorize the first phonetic spelling and the second phonetic spelling, wherein the reversing operation and the comparing operation are performed on vectorized forms of the first phonetic spelling and the second phonetic spelling.

Another example system of any preceding system is provided, wherein the constraints normalizer is configured to reverse one or more phonological constraints of the first orthography on the first revised phonetic spelling and one or more phonological constraints of the second orthography on the second revised phonetic spelling, wherein the comparing operation is performed on the first revised phonetic spelling and the second revised phonetic spelling after application of the one or more phonological constraints.

Another example system of any preceding system is provided, wherein the constraints normalizer is configured to reverse one or more orthographical constraints of the first orthography on the first revised phonetic spelling and one or more orthographical constraints of the second orthography on the second revised phonetic spelling, wherein the comparing operation is performed on the first revised phonetic spelling and the second revised phonetic spelling after application of the one or more orthographical constraints.

Another example system of any preceding system is provided, further including a conflator executable by the one or more hardware processors and configured to delete one or more syllable boundaries in the first revised phonetic spelling and the second revised phonetic spelling, wherein the comparing operation is performed on the first revised phonetic spelling and the second revised phonetic spelling after deletion of one or more syllable boundaries.

Another example system of any preceding system is provided, wherein the string comparator is configured to execute a similarity function between the first revised phonetic spelling and the second revised phonetic spelling, wherein the similarity function is pair-wise executed on each feature vector corresponding to each character of the first revised phonetic spelling and the second revised phonetic spelling to generate per-character output scores.

Another example system of any preceding system is provided, wherein the first textual string is a search query and the second textual string is included in data to be searched, and the string comparator is further configured to output a ranked listing of the data to be searched based on the similarity score for the first textual string and the second textual string and other similarity scores between the first textual string and other strings in the data to be searched.

One or more example tangible processor-readable storage media embodied with instructions for executing on one or more processors and circuits of a computing device a process for fuzzy string comparison between a first textual string of a first orthography and a second textual string of a second orthography are provided. The process includes transliterating the first textual string to a first phonetic spelling and the second textual string to a second phonetic spelling, detecting application of one or more constraints of the first orthography on the first phonetic spelling and of one or more constraints of the second orthography on the second phonetic spelling, reversing the detected constraints of the first orthography on the first phonetic spelling to generate a first revised phonetic spelling and the detected constraints of the second orthography on the second phonetic spelling to generate a second revised phonetic spelling, and comparing the first revised phonetic spelling and the second revised phonetic spelling to generate a similarity score for the first textual string and the second textual string.

One or more other example tangible processor-readable storage media of any preceding media are provided, wherein the process further includes reversing one or more orthographical or phonological constraints of the first orthography on the first revised phonetic spelling and one or more orthographical or phonological constraints of the second orthography on the second revised phonetic spelling, wherein the comparing operation is performed on the first revised phonetic spelling and the second revised phonetic spelling after the application of the one or more orthographical or phonological constraints.

One or more other example tangible processor-readable storage media of any preceding media are provided, wherein the process further includes deleting one or more syllable boundaries in the first revised phonetic spelling and the second revised phonetic spelling, wherein the comparing operation is performed on the first revised phonetic spelling and the second revised phonetic spelling after deletion of one or more syllable boundaries.

One or more other example tangible processor-readable storage media of any preceding media are provided, wherein the comparing operation includes executing a similarity function between the first revised phonetic spelling and the second revised phonetic spelling, wherein the similarity function is pair-wise executed on each feature vector corresponding to each character of the first revised phonetic spelling and the second revised phonetic spelling to generate per-character output scores.

One or more other example tangible processor-readable storage media of any preceding media are provided, wherein the comparing operation further includes summing the per-character output scores from the similarity function to yield the similarity score for the first textual string and the second textual string.

One or more other example tangible processor-readable storage media of any preceding media are provided, wherein the first textual string is a search query and the second textual string is included in data to be searched, and further including outputting a ranked listing of the data to be searched based on the similarity score for the first textual string and the second textual string and other similarity scores between the first textual string and other strings in the data to be searched.

Another example system for fuzzy string comparison between a first textual string of a first orthography and a second textual string of a second orthography is provided. The system includes means for transliterating the first textual string to a first phonetic spelling and the second textual string to a second phonetic spelling, means for detecting application of one or more constraints of the first orthography on the first phonetic spelling and of one or more constraints of the second orthography on the second phonetic spelling, means for reversing the detected constraints of the first orthography on the first phonetic spelling to generate a first revised phonetic spelling and the detected constraints of the second orthography on the second phonetic spelling to generate a second revised phonetic spelling, and means for comparing the first revised phonetic spelling and the second revised phonetic spelling to generate a similarity score for the first textual string and the second textual string.

Another example system of any preceding system is provided, further including means for vectorizing the first phonetic spelling and the second phonetic spelling, wherein the means for reversing and the means for comparing operate on vectorized forms of the first phonetic spelling and the second phonetic spelling.

Another example system of any preceding system is provided, wherein the means for reversing includes means for reversing one or more phonological constraints of the first orthography on the first revised phonetic spelling and one or more phonological constraints of the second orthography on the second revised phonetic spelling, wherein the means for comparing operates on the first revised phonetic spelling and the second revised phonetic spelling after the reversal of the one or more phonological constraints.

Another example system of any preceding system is provided, wherein the means for reversing includes means for reversing one or more orthographical constraints of the first orthography on the first revised phonetic spelling and one or more orthographical constraints of the second orthography on the second revised phonetic spelling, wherein the means for comparing operates on the first revised phonetic spelling and the second revised phonetic spelling after the reversal of the one or more orthographical constraints.

Another example system of any preceding system is provided, further including means for deleting one or more syllable boundaries in the first revised phonetic spelling and the second revised phonetic spelling, wherein the means for comparing operates on the first revised phonetic spelling and the second revised phonetic spelling after deletion of one or more syllable boundaries.

Another example system of any preceding system is provided, wherein the means for comparing includes means for executing a similarity function between the first revised phonetic spelling and the second revised phonetic spelling, wherein the similarity function is pair-wise executed on each feature vector corresponding to each character of the first revised phonetic spelling and the second revised phonetic spelling to generate per-character output scores.

Another example system of any preceding system is provided, wherein the first textual string is a search query and the second textual string is included in data to be searched, and further including means for outputting a ranked listing of the data to be searched based on the similarity score for the first textual string and the second textual string and other similarity scores between the first textual string and other strings in the data to be searched.