How to realize the spelling correction function in search engine

         When the user is in the search box , When typing a misspelled word , Let's compare this word with the words in the thesaurus , Calculate edit distance , The word with the smallest distance will be edited , As a corrected word , Prompt to user .

         This is the basic principle of spelling correction . however , A real commercial search engine , The spelling correction function is obviously not that simple . One side , Simply use editing distance to correct errors , The effect is not necessarily good ; On the other hand , The amount of data in the thesaurus may be very large , Search engines should support a large number of searches every day , So the performance of error correction is very high .

         Aiming at the problem that the error correction effect is not good , We have many optimization ideas , Here are some .

         We don't just take out the word with the smallest editing distance , But take out the one with the smallest editing distance TOP 10, Then according to other parameters , Decide which word to choose as the spelling correction word . For example, use search popularity to determine which word is used as spelling correction word .

         We can also use a variety of editing distance calculation methods , For example, the two types mentioned today , Then edit the least distance TOP 10, Then find the intersection , Using the result of intersection , Continue to optimize .

         We can also count the search logs of users , Get a list of the most commonly misspelled words , And the corresponding correctly spelled words . When the search engine corrects spelling , First, look in this list of the most commonly misspelled words . If once found , Directly return the corresponding correct word . The effect of this correction is very good .

         We have more advanced methods , Introduction of personalization factors . For each user , Maintain this user specific search preferences , That is, commonly used search keywords . When the user enters the wrong word , Let's start with the search keywords that users often use , Calculate edit distance , Find the word with the smallest editing distance .

         For error correction performance , We also have corresponding optimization methods . Here are two optimization ideas of divide and conquer .

         If the error correction function TPS Not high , We can deploy multiple machines , Each machine runs an independent error correction function . When there is an error correction request , We use load balancing , Assigned to one of the machines , To calculate the edit distance , Get error correcting words .

         If the response time of the error correction system is too long , That is to say , Each error correction request takes too long to process , We can put the vocabulary of error correction , Split into many machines . When there is an error correction request , Let's put this misspelled word , Send to these multiple machines at the same time , Let multiple machines process in parallel , Get the word with the smallest editing distance , Then compare and merge , Finally, an optimal error correction word is determined .

         Real search engine spelling correction optimization , It must be more than what I said above , But everything is the same . Master the core principles , Is to master the method to solve the problem , The rest depends on your own flexible use and practice .