IOS पर फ़ज़ी वर्ड सर्च

आपका दिन शुभ हो! आज हम अपनी डेवलपर स्टोरी ... और साथ ही मोबाइल उपकरणों के लिए मानक फ़ज़ी सर्च एल्गोरिदम को अनुकूलित करने के अपने अनुभव को साझा करना चाहते हैं।

प्रागितिहास

यह सब स्टैनफोर्ड यूनिवर्सिटी में "CS193P iOS के लिए विकासशील ऐप्स" पर एक व्याख्यान के साथ शुरू हुआ। लेकिन एक पायलट प्रोजेक्ट के रूप में, मैं एक और कैलकुलेटर देना नहीं चाहता था। हम लगातार विकास के लिए एक दिलचस्प विचार की तलाश कर रहे थे। जैसा कि आमतौर पर होता है, विचार अचानक आया जब मस्तिष्क सो रहा था ... विचार काफी सरल था: आवेदन को यह निर्धारित करना चाहिए कि शब्द को कैसे वर्तनी दी जाए। और यदि शब्द त्रुटि के साथ उपयोगकर्ता द्वारा दर्ज किया गया है - सही वर्तनी दिखाएं। इस तरह के एक आवेदन पत्रकारों और छात्रों (शीतकालीन सत्र बस आ रहा था) पर जाने के लिए उपयोगी हो सकता है। जब हमें पता चला कि हमारे आवेदन ऐसे नहीं थे, तो हमें क्या आश्चर्य हुआ! हां, ऐसे शब्दकोष हैं जो खोजे गए शब्द को पूरक करने की कोशिश करते हैं और एक टाइपो की अनुमति देते हैं ... लेकिन खोज की गति और अनुप्रयोग का आकार स्वयं ही निराशाजनक है!
उपरोक्त सभी के अलावा, हैबे पर लेख में वर्णित फजी सर्च एल्गोरिदम के साथ काम करने के लिए एक और प्रोत्साहन था। मैं लंबे समय से ऐसे एल्गोरिदम को लागू करना चाहता हूं और मोबाइल डिवाइस पर उनके काम की गति को मापता हूं।

शुरुआत हो रही है

प्रारंभ में, दृष्टिकोण को चुना गया था जब खोज शब्द "लेवेन्सहाइटिन दूरी" का उपयोग करते हुए शब्दकोश से प्रत्येक तत्व के साथ तुलना की जाती है। लेकिन एक iPhone पर "मुकाबला" स्थितियों में परीक्षण से पता चला कि इस तरह की खोज में औसतन 30-90 सेकंड लगते हैं - यह शब्दकोश में केवल 90,000 शब्द हैं! अस्वीकार्य रूप से लंबा! फिर एक और तरीका चुना गया: शुरू में शब्दकोश से सूचकांक बनाने के लिए, हस्ताक्षर द्वारा हैशिंग विधि का उपयोग करना। और उसके बाद ही समाप्त सूचकांक में शब्द की तलाश करें। नए तरीके से एप्लिकेशन को जल्दी से अपनाने के बाद, हमने तुरंत एक iPhone पर इसका परीक्षण किया। और फिर से विफलता - सूचकांक का निर्माण और, तदनुसार, आवेदन की शुरुआत में लगभग 90-120 सेकंड लगे! हर उपयोगकर्ता 2 मिनट प्रतीक्षा नहीं करेगा ताकि यह जांचा जा सके कि उसने कुछ शब्दों को सही ढंग से लिखा है। आवेदन और भी अधिक अनुकूलन की आवश्यकता है।

अनुकूलन

अगला कदम मैक पर एक शब्दकोश सूचकांक बनाना था, साथ ही समाप्त सूचकांक को साइक्लाइट डेटाबेस में सहेजना था। इसके बाद, iOS डिवाइस तैयार इंडेक्स को लोड करता है। फिर से आवेदन करने और नई विधि के लिए अनुकूलन करने के लिए। और अंत में, एक सकारात्मक परिणाम - 7-12 सेकंड में आवेदन की एक ठंडी शुरुआत! फिर हमने एप्लिकेशन को और भी अधिक लोड करने की कोशिश की - एप्लिकेशन के शब्दावली डेटाबेस को 355742 शब्दों तक विस्तारित किया गया (वास्तव में रूसी भाषा के कई वर्तनी और व्याख्यात्मक शब्दकोशों से कई अद्वितीय शब्द एकत्र किए गए थे)। डिक्शनरी इंडेक्स को अपडेट करने के बाद, एप्लिकेशन की शुरुआत में 10-15 सेकंड लगते हैं। लेकिन सबसे महत्वपूर्ण बात यह है कि अब एक शब्द खोज कुछ मिलीसेकंड से दस सेकंड तक बड़ी संख्या में समान शब्दों के साथ होती है। इस परिणाम ने मुझे पूरी तरह से अनुकूल बना दिया। आगे बढ़ना जरूरी था।

अतिरिक्त विशेषताएं

उपयोग करने के लिए एप्लिकेशन को अधिक सुविधाजनक बनाने के लिए, हमने कई अतिरिक्त सुविधाएँ जोड़ी हैं:
* परिणाम को श्रेणियों में समूहित करना: पूर्ण संयोग, एक शब्द में एक अक्षर में बदलाव (और इसी तरह - तीन तक)।



* आवेदन द्वारा पाया गया कोई भी शब्द क्लिपबोर्ड पर कॉपी किया जा सकता है।
विकी शब्दकोश, विकिपीडिया, यैंडेक्स शब्दकोश और Google खोज में शब्द के अर्थ के लिए खोज को जोड़ा गया। लेकिन इस फीचर के लिए इंटरनेट कनेक्शन की जरूरत होती है।



* आवेदन मूल रूप से सार्वभौमिक और सहायक क्षैतिज और ऊर्ध्वाधर स्क्रीन मोड के रूप में विकसित किया गया था।

प्रोग्राम करने वाला व्यक्ति

हमने आवेदन के नाम पर निर्णय लेने के बाद, यह "एक चेहरा मिला", और उपस्थिति के बारे में कोई बहस नहीं हुई। इससे पहले कि मेरी आँखें एक ब्लैकबोर्ड पर खड़ी होतीं, जिस पर एक सुंदर शिक्षक की लिखावट में बड़े अक्षरों को खींचा जाता था। पत्र, जो रूसी भाषा के सबसे लोकप्रिय, शायद, सबसे लोकप्रिय नियम को जोड़ते हैं: "पत्र" और "शि" लिखो! सबसे अधिक बार, हमें स्कूल में वर्तनी की त्रुटियों को सुधारना होगा। इसलिए, आवेदन के नाम और डिजाइन में स्कूल का माहौल हमें सबसे उपयुक्त लगा।



प्रोजेक्ट पेज से लिंक करें
AppStore ऐप लिंक: जी-शी

Upd1:
AppStore में मुफ्त ऐप का लिंक: जी-शी लाइट

upd2:
बाद में, हमारे उपयोगकर्ताओं से मिले फीडबैक के आधार पर, हमने आवेदन में निम्नलिखित बदलाव किए:

* अंतर्निहित व्याख्यात्मक शब्दकोश (T.F. Efremova द्वारा संपादित) में खोजें।
* रूसी भाषा के मौजूदा नियम (वर्तनी)।

हम किसी भी रचनात्मक आलोचना, सुझाव और इच्छाओं की प्रतीक्षा करते हैं!

पुनश्च: पहचान के लिए प्रचार कोड:

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