Fuzzy word search on the iOS platform
Good day! Today we want to share our Developer Story ... as well as the experience of optimizing standard fuzzy search algorithms for mobile devices.
It all started with watching Stanford University's lectures on the “CS193P Developing Apps for iOS” course. But as a pilot project I didn’t want to give out another calculator. We were constantly looking for an interesting idea to develop. As is usually the case, the idea came suddenly when the brain was getting ready to fall asleep ... The idea was quite simple: the application must determine how to write the word correctly. And if the word is entered by a user with an error, show the correct spelling variants. Such an application could be useful for traveling journalists and students (just coming winter session). What was our surprise when we found out that there are no such applications! Yes, there are dictionaries that, at best, try to supplement the search word and allow one typo ... But the search speed and size of the application itself is depressing!
In addition to all of the above, there was another incentive to work with the fuzzy search algorithms described in the article on Habré . I have long wanted to implement similar algorithms and measure the speed of their work on a mobile device.
Initially, the approach was chosen when the search word is compared with each element from the dictionary using the “Levenshtein distance”. But the test in the “combat” conditions on the iPhone showed that such a search takes on average 30-90 seconds - this is in the dictionary of all of 90,000 words! Inadmissibly long! Then another way was chosen: initially to build an index according to a dictionary, using the signature hashing method. And only then look for the word on the finished index. Quickly adapting the application for a new method, we immediately checked it on the iPhone. And again, failure - creating an index and, accordingly, the start of the application took about 90-120 seconds! Not every user will wait 2 minutes to check if he has written a few words correctly. The application required even more optimization.
')
The next step was to create a dictionary index on the Mac, and also save the finished index to the sqlite database. Next, the iOS device loads the ready-made index. Again, refactoring and adapting the application to the new method. And finally, a positive result - a cold start of the application in 7-12 seconds! Then we tried to load the application even more - the dictionary base of the application was expanded to 355742 words (just as many unique words were collected from several spelling and explanatory dictionaries of the Russian language). After updating the dictionary index, the start of the application began to take 10-15 seconds. But the most important thing is that now the search for a word takes from several milliseconds to ten seconds with a large number of similar words. This result suited me perfectly. We had to move on.
To make the application more convenient to use, we added several additional features:
* Grouping the result by category: full match, with the change of one letter in the word (and so on - up to three).
* Any word found by the application can be copied to the clipboard.
Added search for word values ​​in the wiki dictionary, wikipedia, yandex dictionary and google search. But this feature requires an internet connection.
* The application was originally developed as a universal and supports horizontal and vertical screen modes.
After we decided on the name of the application, it “acquired a face”, and there was no dispute over the appearance. There was a school board in front of my eyes, with capital letters in a beautiful teacher's handwriting. Letters that add up to perhaps the most popular rule of the Russian language: “live” “shi” write with the letter “and”! Most often, we have to look for and correct spelling errors in the school. Therefore, the school atmosphere in the name and design of the application seemed to us the most appropriate.
Link to the project page
Link to the application in the AppStore: Ji-Shi
Upd1:
Link to the free app in the AppStore: Ji-Shi Lite
Upd2:
Later, based on feedback from our users, we made the following changes to the application:
* Search the built-in explanatory dictionary (edited by TF Efremova).
* Added the current rules of the Russian language (spelling).
We are waiting for any constructive criticism, suggestions and suggestions!
PS: Promotional codes for review:
N7TMEN3HTPHA
EKRTARHTRYRL
PKYJMERYWMKP
L9TYPNEFA7AH
FETYYTW33TLH
NEN6KFPX74HT
NY7HHLNL4X33
NXHEXR7F3L66
N37F7MTYLN77
9RW9JNYJ43X7
M9FFKK6FTYWA
F69YLWNT4PEN
JWKAELJ3YA7X
R7WMNHW37X94
AHJFRJ3HRAMN
96PTNLTXKJ76
LFPNXNHWA799
WFLENJAMJPK4
HRX6T93W644E
M7YR9T4TTJKL
6HXERELJ7YF7
NJMWP3J6FLLR
M39KYPLFYHE7
7LPAEN4L99KP
YWEP4EPMYM6Y
Y7NWK9ERMHYN
KLHH63HFEWJT
LLKY3PPJ3LLL
WHJFRP63WXRP
FK3WWXJ7MPN9
Prehistory
It all started with watching Stanford University's lectures on the “CS193P Developing Apps for iOS” course. But as a pilot project I didn’t want to give out another calculator. We were constantly looking for an interesting idea to develop. As is usually the case, the idea came suddenly when the brain was getting ready to fall asleep ... The idea was quite simple: the application must determine how to write the word correctly. And if the word is entered by a user with an error, show the correct spelling variants. Such an application could be useful for traveling journalists and students (just coming winter session). What was our surprise when we found out that there are no such applications! Yes, there are dictionaries that, at best, try to supplement the search word and allow one typo ... But the search speed and size of the application itself is depressing!
In addition to all of the above, there was another incentive to work with the fuzzy search algorithms described in the article on Habré . I have long wanted to implement similar algorithms and measure the speed of their work on a mobile device.
Beginning of work
Initially, the approach was chosen when the search word is compared with each element from the dictionary using the “Levenshtein distance”. But the test in the “combat” conditions on the iPhone showed that such a search takes on average 30-90 seconds - this is in the dictionary of all of 90,000 words! Inadmissibly long! Then another way was chosen: initially to build an index according to a dictionary, using the signature hashing method. And only then look for the word on the finished index. Quickly adapting the application for a new method, we immediately checked it on the iPhone. And again, failure - creating an index and, accordingly, the start of the application took about 90-120 seconds! Not every user will wait 2 minutes to check if he has written a few words correctly. The application required even more optimization.
')
Optimization
The next step was to create a dictionary index on the Mac, and also save the finished index to the sqlite database. Next, the iOS device loads the ready-made index. Again, refactoring and adapting the application to the new method. And finally, a positive result - a cold start of the application in 7-12 seconds! Then we tried to load the application even more - the dictionary base of the application was expanded to 355742 words (just as many unique words were collected from several spelling and explanatory dictionaries of the Russian language). After updating the dictionary index, the start of the application began to take 10-15 seconds. But the most important thing is that now the search for a word takes from several milliseconds to ten seconds with a large number of similar words. This result suited me perfectly. We had to move on.
Additional features
To make the application more convenient to use, we added several additional features:
* Grouping the result by category: full match, with the change of one letter in the word (and so on - up to three).
* Any word found by the application can be copied to the clipboard.
Added search for word values ​​in the wiki dictionary, wikipedia, yandex dictionary and google search. But this feature requires an internet connection.
* The application was originally developed as a universal and supports horizontal and vertical screen modes.
Program face
After we decided on the name of the application, it “acquired a face”, and there was no dispute over the appearance. There was a school board in front of my eyes, with capital letters in a beautiful teacher's handwriting. Letters that add up to perhaps the most popular rule of the Russian language: “live” “shi” write with the letter “and”! Most often, we have to look for and correct spelling errors in the school. Therefore, the school atmosphere in the name and design of the application seemed to us the most appropriate.
Link to the project page
Link to the application in the AppStore: Ji-Shi
Upd1:
Link to the free app in the AppStore: Ji-Shi Lite
Upd2:
Later, based on feedback from our users, we made the following changes to the application:
* Search the built-in explanatory dictionary (edited by TF Efremova).
* Added the current rules of the Russian language (spelling).
We are waiting for any constructive criticism, suggestions and suggestions!
PS: Promotional codes for review:
N7TMEN3HTPHA
EKRTARHTRYRL
PKYJMERYWMKP
L9TYPNEFA7AH
FETYYTW33TLH
NEN6KFPX74HT
NY7HHLNL4X33
NXHEXR7F3L66
N37F7MTYLN77
9RW9JNYJ43X7
M9FFKK6FTYWA
F69YLWNT4PEN
JWKAELJ3YA7X
R7WMNHW37X94
AHJFRJ3HRAMN
96PTNLTXKJ76
LFPNXNHWA799
WFLENJAMJPK4
HRX6T93W644E
6HXERELJ7YF7
NJMWP3J6FLLR
M39KYPLFYHE7
7LPAEN4L99KP
YWEP4EPMYM6Y
Y7NWK9ERMHYN
KLHH63HFEWJT
LLKY3PPJ3LLL
WHJFRP63WXRP
FK3WWXJ7MPN9
Source: https://habr.com/ru/post/136406/
All Articles