Searching and matching of data

• US 8,745,077 B2
• Filed: 10/25/2012
• Issued: 06/03/2014
• Est. Priority Date: 06/23/2010
• Status: Active Grant

• Current Assignee: Business Objects Incorporated (SAP SE)
• Original Assignee: Business Objects Incorporated (SAP SE)
• Inventors: Huang, Xinrong
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US13/659,911
• Publication Number:
  US 20130054225A1
• Time in Patent Office: 586 Days
• Field of Search: 707/748, 707/759, 707/760, 707/769
• US Class Current: 707/760
• CPC Class Codes: G06F 16/3337 Translation of the query language, e.g. Chinese to English
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion

Abstract

Described herein is a technology for facilitating searching and matching of data. In some implementations, an input data string, including one or more ideographic elements, is received and converted to a Latin-based input data string. One or more input keys may be generated based on the Latin-based input data string. A reference database may be searched for one or more candidate records indexed by at least one of the one or more input keys. If the one or more candidate records are found, a match score is determined for the one or more candidate records.

Claims

1. A method implemented by a computer comprising at least one processor and at least one memory for facilitating searching and matching of data, comprising:

receiving an input data string including one or more ideographic elements;

converting the input data string to a Latin-based input data string at least in part by deconstructing the one or more ideographic elements into constituent radicals or strokes and cross-referencing a constituent radical or stroke to a pre-defined Latin character so as to generate one or more sets of Latin characters;

generating one or more input keys based on the Latin-based input data string, including replacing any element in the Latin-based input data string that has a corresponding sounds-alike element to generate a phonetic key;

searching, using the one or more input keys, a reference database stored in a memory device for one or more candidate records, wherein similar records in the database are indexed by a common lookup key; and

if the one or more candidate records are found, determining a match score of the one or more candidate records.

2. The method of claim 1 wherein the one or more ideographic elements comprise one or more Chinese, Japanese, Korean or Vietnamese characters.

3. The method of claim 1 wherein the converting the input data string to the Latin-based input data string comprises converting the input data string to one or more phonetic spellings of the one or more ideographic elements.

4. The method of claim 3 wherein the generating the one or more input keys comprises generating the phonetic key based on at least one of the one or more phonetic spellings.

5. The method of claim 3 wherein the generating the one or more input keys comprises generating multiple phonetic keys based on multiple phonetic spellings.

6. The method of claim 4 wherein the generating the phonetic key comprises removing any non-space silent element from one of the one or more phonetic spellings.

7. The method of claim 6 wherein the silent element comprises a letter “

H,”

“

G,”

“

I,”

or “

U.”

8. The method of claim 1 wherein the constituent radical comprises a set of strokes pre-defined according to a given language.

9. The method of claim 8 wherein the set of strokes comprises a horizontal stroke, a vertical stroke, a left-falling stroke, a right-falling stroke or a turning stroke.

10. The method of claim 1 wherein the generating the one or more input keys comprises generating one or more radical keys based on the one or more sets of Latin characters.

11. The method of claim 10 wherein the generating the one or more radical keys comprises replacing any Latin character in the set of Latin characters that is associated with a radical that has a corresponding looks-alike radical.

12. The method of claim 1 wherein the constituent stroke comprises a horizontal stroke, a vertical stroke, a left-falling stroke, a right-falling stroke or a turning stroke.

13. The method of claim 12 wherein the generating the one or more input keys comprises generating one or more stroke keys based on the one or more sets of Latin characters.

14. The method of claim 13 wherein the generating the one or more stroke keys comprises replacing any Latin character in the set of Latin characters that is associated with a stroke that has a corresponding looks-alike stroke.

15. The method of claim 1 wherein the reference database comprises an index table, wherein each record in the index table comprises a standard key, a phonetic key, a radical key, a stroke key, or a combination thereof.

16. The method of claim 1 wherein the searching the reference database comprises issuing a query statement based on at least one of the one or more input keys.

17. The method of claim 16 wherein the query statement comprises a structured query language (SQL) statement.

18. The method of claim 1 wherein the determining the match score comprises determining an edit distance between the Latin-based input data string and a Latin-based representation of a language text string in the one or more candidate records.

19. The method of claim 18 further comprising converting the language text string to the Latin-based representation.

20. The method of claim 19 wherein the Latin-based representation comprises a phonetic spelling of the language text string.

21. The method of claim 19 wherein the Latin-based representation comprises a set of Latin characters, wherein a Latin character represents a radical of the language text string.

22. The method of claim 19 wherein the Latin-based representation comprises a set of Latin characters, wherein a Latin character represents a stroke of the language text string.

23. The method of claim 18 wherein the edit distance comprises a Levenshtein distance.

24. The method of claim 18 wherein the determining the match score comprises normalizing the edit distance.

25. The method of claim 1 further comprising generating multiple input keys based on the input data string.

26. The method of claim 25 wherein the searching the reference database and the determining the match score are iteratively repeated by using one of the multiple input keys until a candidate record is found where the match score exceeds a predetermined threshold.

27. The method of claim 1 further comprising presenting a suggestion list of one or more language text strings of one or more candidate records with highest match scores.

28. A non-transitory computer usable medium having a computer readable program code tangibly embodied therein, the computer readable program code adapted to be executed by a processor to implement a method for facilitating searching and matching of data, comprising:

receiving an input data string including one or more ideographic elements;

converting the input data string to a Latin-based input data string at least in part by deconstructing the one or more ideographic elements into constituent radicals or strokes and cross-referencing a constituent radical or stroke to a pre-defined Latin character so as to generate one or more sets of Latin characters;

generating one or more input keys based on the Latin-based input data string, including replacing any element in the Latin-based input data string that has a corresponding sounds-alike element to generate a phonetic key;

searching, using the one or more input keys, a reference database for one or more candidate records, wherein similar records in the database are indexed by a common lookup key; and

if the one or more candidate records are found, determining a match score of the one or more candidate records.

29. A system for facilitating searching and matching of data, comprising:

a non-transitory memory device for storing computer readable program code; and

a processor in communication with the memory device, the processor being operative with the computer readable program code to;

receive an input data string including one or more ideographic elements;

convert the input data string to a Latin-based input data string at least in part by deconstructing the one or more ideographic elements into constituent radicals or strokes and cross-referencing a constituent radical or stroke to a pre-defined Latin character so as to generate one or more sets of Latin characters;

generate one or more input keys based on the Latin-based input data string, including replacing any element in the Latin-based input data string that has a corresponding sounds-alike element to generate a phonetic key;

search, using the one or more input keys, a reference database for one or more candidate records, wherein similar records in the database are indexed by a common lookup key; and

if the one or more candidate records are found, determining a match score of the one or more candidate records.