Method for fast retrieval of phonetically similar words and search engine system therefor

• US 10,409,861 B2
• Filed: 05/09/2016
• Issued: 09/10/2019
• Est. Priority Date: 05/09/2016
• Status: Active Grant

• Current Assignee: WizSoft Ltd.
• Original Assignee: WizSoft Ltd.
• Inventors: Meidan, Abraham, Zbeda, Oren
• Primary Examiner(s): Leroux, Etienne P
• Application Number:
  US15/149,349
• Publication Number:
  US 20170323014A1
• Time in Patent Office: 1,219 Days
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/151 Transformation

Abstract

Useful search results are obtained when the search logic retrieves, not only text strings, or “words,” that match exactly the search arguments but also when the search logic retrieves phonetically similar words, which are misspelled. The method and system disclosed herein provide both results faster than known conventional methods and systems, and in some embodiments such speed may be achieved using conventional resources as described.

Claims

1. A method of phonetically retrieving words from a source file that is associated with an index file, the index file containing a record for each word to be tested for phonetic similarity, the record having a primary string of letters and secondary strings of letters from the word, the i^th secondary string generated by omitting the i^th letter from the primary string, the method comprising:

receiving by a search system from a user device a word to be searched, the word becoming a search argument;

generating by the search system a primary string of letters and secondary strings of letters from the search argument, the argument'"'"'s i^th secondary string generated by omitting the i^th letter from the argument'"'"'s primary string;

searching the records'"'"' primary strings for equivalence with the argument'"'"'s primary string and marking records containing equivalent primary strings;

searching each record'"'"'s i^th secondary string for equivalence with the argument'"'"'s i^th secondary string and marking records containing equivalent i^th secondary strings;

searching each secondary string of each record for equivalence with the argument'"'"'s primary string and marking records containing equivalent secondary strings;

searching the records'"'"' primary strings for equivalence with each of the argument'"'"'s secondary strings and marking records containing equivalent primary strings;

generating one or more tertiary strings of letters from the search argument, the argument'"'"'s i^th tertiary string formed from the argument'"'"'s primary string by transposing the i^th letter with the (i+1)^th letter of the argument'"'"'s primary string;

searching the records'"'"' primary strings for equivalence with each of the argument'"'"'s tertiary strings and marking records containing equivalent primary strings; and

for each marked record, retrieving the word from the source file that is associated with the marked record in the index file.

2. The method of claim 1, wherein the primary strings of letters in the records of the index file and the primary string of letters from the search argument are generated by:

omitting all vowels from the word to be tested for phonetic similarity and from the search argument, except the first letters, if the first letters are vowels; and

if two adjacent letters are the same consonant, omitting one of the two adjacent letters.

3. The method of claim 1 further comprising:

sorting the retrieved words according to their similarity to the word to be searched.

4. The method of claim 1 further comprising:

sorting the retrieved words according to the number of marked records associated with each word.

5. A method of phonetically retrieving words from a source file that is associated with an index file, the index file containing a record for each word to be tested for phonetic similarity, the record having a primary string of letters and secondary strings of letters from the word, the i^th secondary string generated by omitting the i^th letter from the primary string, the method comprising:

receiving by a search system from a user device a word to be searched, the word becoming a search argument;

generating by the search system a primary string of letters and secondary strings of letters from the search argument, the argument'"'"'s i^th secondary string generated by omitting the i^th letter from the argument'"'"'s primary string;

searching the records'"'"' primary strings for equivalence with the argument'"'"'s primary string and marking records containing equivalent primary strings;

searching each record'"'"'s i^th secondary string for equivalence with the argument'"'"'s i^th secondary string and marking records containing equivalent i^th secondary strings;

searching each secondary string of each record for equivalence with the argument'"'"'s primary string and marking records containing equivalent secondary strings; and

for each marked record, retrieving the word from the source file that is associated with the marked record in the index file;

generating one or more tertiary strings of letters from the search argument, the argument'"'"'s i^th tertiary string formed from the argument'"'"'s primary string by transposing the i^th letter with the (i+1)^th letter of the argument'"'"'s primary string;

searching the records'"'"' primary strings for equivalence with each of the argument'"'"'s tertiary strings and marking records containing equivalent primary strings; and

for each marked record, retrieving the word from the source file that is associated with the marked record in the index file.

6. A method of phonetically retrieving words from a source file that is associated with an index file, the index file containing a record for each word to be tested for phonetic similarity, the record having a primary string of letters and secondary strings of letters from the word, the i^th secondary string generated by omitting the i^th letter from the primary string, the method comprising:

receiving by a search system from a user device a word to be searched, the word becoming a search argument;

generating by the search system a primary string of letters and secondary strings of letters from the search argument, the argument'"'"'s i^th secondary string generated by omitting the i^th letter from the argument'"'"'s primary string;

searching the records'"'"' primary strings for equivalence with the argument'"'"'s primary string and marking records containing equivalent primary strings;

searching each record'"'"'s i^th secondary string for equivalence with the argument'"'"'s i^th secondary string and marking records containing equivalent i^th secondary strings;

searching each secondary string of each record for equivalence with the argument'"'"'s primary string and marking records containing equivalent secondary strings; and

for each marked record, retrieving the word from the source file that is associated with the marked record in the index file;

wherein the primary string of letters in the records of the index file and the primary string of letters from the search argument are generated by;

omitting all vowels from the word to be tested for phonetic similarity and from the search argument, except the first letters, if the first letters are vowels; and

if two adjacent letters are the same consonant, omitting one of the two adjacent letters.

7. A phonetic search engine system for retrieving words from a source file that is associated with an index file, the index file containing a record for each word to be tested for phonetic similarity, the record having a primary string of letters and secondary strings of letters from the word, the i^th secondary string generated by omitting the i^th letter from the primary string, the search engine comprising:

one or more interfaces operative;

(1) to receive from a user device a word to be searched, the word becoming a search argument, and (2) to send to the user device search results;

a processor operatively connected to the one or more interfaces; and

storage operatively connected to the processor and holding instructions that when executed activate the processor to;

generate a primary string of letters and secondary strings of letters from the search argument, the argument'"'"'s i^th secondary string generated by omitting the i^th letter from the argument'"'"'s primary string;

search the records'"'"' primary strings for equivalence with the argument'"'"'s primary string and marking records containing equivalent primary strings;

search each record'"'"'s i^th secondary string for equivalence with the argument'"'"'s i^th secondary string and marking records containing equivalent i^th secondary strings;

search each secondary string of each record for equivalence with the argument'"'"'s primary string and marking records containing equivalent secondary strings; and

for each marked record, retrieve the word from the source file that is associated with the marked record in the index file;

wherein the retrieved words become the search results to send to the user device; and

wherein the storage holds additional instructions that when executed activate the processor also to;

generate one or more tertiary strings of letters from the search argument, the argument'"'"'s i^th tertiary string formed from the argument'"'"'s primary string by transposing the i^th letter with the (i+1)^th letter of the argument'"'"'s primary string;

search the records'"'"' primary strings for equivalence with each of the argument'"'"'s tertiary strings and marking records containing equivalent primary strings; and

for each marked record, retrieve the word from the source file that is associated with the marked record in the index file.

8. A phonetic search engine system for retrieving words from a source file that is associated with an index file, the index file containing a record for each word to be tested for phonetic similarity, the record having a primary string of letters and secondary strings of letters from the word, the i^th secondary string generated by omitting the i^th letter from the primary string, the search engine comprising:

one or more interfaces operative;

(1) to receive from a user device a word to be searched, the word becoming a search argument, and (2) to send to the user device search results;

a processor operatively connected to the one or more interfaces; and

storage operatively connected to the processor and holding instructions that when executed activate the processor to;

generate a primary string of letters and secondary strings of letters from the search argument, the argument'"'"'s i^th secondary string generated by omitting the i^th letter from the argument'"'"'s primary string;

search the records'"'"' primary strings for equivalence with the argument'"'"'s primary string and marking records containing equivalent primary strings;

search each record'"'"'s i^th secondary string for equivalence with the argument'"'"'s i^th secondary string and marking records containing equivalent i^th secondary strings;

search each secondary string of each record for equivalence with the argument'"'"'s primary string and marking records containing equivalent secondary strings; and

for each marked record, retrieve the word from the source file that is associated with the marked record in the index file;

wherein the retrieved words become the search results to send to the user device;

wherein the primary string of letters in the records of the index file and the primary string of letters from the search argument are generated by;

omitting all vowels from the word to be tested for phonetic similarity and from the search argument, except the first letters, if the first letters are vowels; and

if two adjacent letters are the same consonant, omitting one of the two adjacent letters.