हम Google को देखते हैं, फ़ायरफ़ॉक्स कुछ AJAX पृष्ठ संभावित प्रकार की सूची दिखाते हैं जबकि उपयोगकर्ता प्रकार के वर्ण होते हैं।सबसे अच्छा स्वत: पूर्ण/सुझाव एल्गोरिदम, डेटास्ट्रक्चर [सी ++/सी]
क्या कोई स्वत: पूर्ण लागू करने के लिए एक अच्छा एल्गोरिदम, डेटा संरचना दे सकता है?
ए trie एक डेटा संरचना है जिसका उपयोग उपसर्ग से मेल खाने वाले शब्दों को तुरंत खोजने के लिए किया जा सकता है।
संपादित करें: यहाँ एक का उपयोग करने के लिए कैसे स्वत: पूर्ण http://rmandvikar.blogspot.com/2008/10/trie-examples.html
यहाँ 3 अलग auto-complete implementations की तुलना की गई (हालांकि यह जावा में नहीं सी ++) लागू करने के लिए दिखा एक उदाहरण है।
* In-Memory Trie
* In-Memory Relational Database
* Java Set
जब चाबी की तलाश में, trie सेट कार्यान्वयन की तुलना में मामूली तेजी से होता है। त्रिभुज और सेट दोनों संबंधपरक डेटाबेस समाधान से थोड़ा तेज हैं।
सेट की सेटअप लागत ट्री या डीबी समाधान से कम है। आपको यह तय करना होगा कि क्या आप अक्सर "शब्द" का निर्माण करेंगे या फिर लुकअप की गति उच्च प्राथमिकता है या नहीं।
ये परिणाम जावा में हैं, आपका माइलेज एक सी ++ समाधान के साथ भिन्न हो सकता है।
एक सरल उपाय के लिए: यदि आप एक एक न्यूनतम संपादित करें (Levenshtein) दूरी (1 या 2) तो आप एक हैश कंटेनर के साथ उम्मीदवार के अस्तित्व का परीक्षण के साथ 'उम्मीदवार' उत्पन्न (सेट एक सरल soltion के लिए पर्याप्त होगा , तो tr1 या boost से unordered_set का उपयोग करें)।
उदाहरण: आपने कार लिखा और आप कार चाहते हैं। एआर 1 हटाने से उत्पन्न होता है। क्या आपके unordered_set में arr है? नहीं। Crr 1 हटाने से उत्पन्न होता है। क्या आपके unordered_set में crr है? नहीं। कार 1 हटाने से उत्पन्न होती है। क्या आपकी अनॉर्डर्ड_सेट में कार है? हाँ, आप जीतते हैं।
बेशकवहाँ प्रविष्टि, विलोपन, स्थानांतरण आदि है ...
आप देखते हैं कि उम्मीदवारों पैदा करने के लिए अपने एल्गोरिथ्म वास्तव में जगह है जहाँ आप समय बर्बाद कर रहे हैं, खासकर यदि आप एक बहुत कम unordered_set है।
बड़े डेटासेट के लिए, बैकएंड के लिए एक अच्छा उम्मीदवार टर्नरी खोज पेड़ होगा। वे दो दुनिया के सर्वश्रेष्ठ संयोजन को जोड़ते हैं: द्विआधारी खोज पेड़ के निम्न स्थान के ऊपर और डिजिटल खोज की चरित्र-आधारित समय दक्षता की कोशिश करता है।
डॉ डोब्स जर्नल में देखें: http://www.ddj.com/windows/184410528
लक्ष्य में प्रकार उपयोगकर्ता के रूप में एक परिमित resultset के तेजी से पुनः प्राप्ति है चलो पहला यह है कि खोजने के लिए "कंप्यूटर विज्ञान" आप "कंप्यूटर" से लिखना प्रारंभ कर सकते पर विचार करें। या "विज्ञान" लेकिन "ओम्प्यूटर" नहीं। तो, एक वाक्यांश दिया, एक शब्द से शुरू उप-वाक्यांश उत्पन्न करते हैं। अब प्रत्येक वाक्यांश के लिए, उन्हें टीएसटी (टर्नरी सर्च पेड़) में खिलाएं। टीएसटी में प्रत्येक नोड अब तक टाइप किए गए वाक्यांश के उपसर्ग का प्रतिनिधित्व करेगा। हम उस नोड में उस उपसर्ग के लिए सर्वोत्तम 10 (कहें) परिणाम संग्रहीत करेंगे। यदि नोड के लिए परिणामों की सीमित मात्रा (10 यहां) से अधिक उम्मीदवार हैं, तो दो परिणामों के बीच प्रतिस्पर्धा को हल करने के लिए रैंकिंग फ़ंक्शन होना चाहिए।
पेड़ डेटा की गतिशीलता के आधार पर, हर कुछ घंटों में एक बार बनाया जा सकता है।यदि डेटा वास्तविक समय में है, तो मुझे लगता है कि कुछ अन्य एल्गोरिदम बेहतर संतुलन देंगे। इस मामले में, पूर्ण आवश्यकता प्रत्येक कुंजीस्ट्रोक टाइप के परिणामों के बिजली-तेज़ पुनर्प्राप्ति है जो यह बहुत अच्छी तरह से करता है।
वर्तनी सुधारों का सुझाव शामिल होने पर अधिक जटिलताएं उत्पन्न होंगी। उस स्थिति में, संपादन दूरी एल्गोरिदम को भी माना जाना चाहिए।
देशों की सूची जैसे छोटे डेटासेट के लिए, ट्री का एक सरल कार्यान्वयन करेगा। यदि आप किसी वेब एप्लिकेशन में ऐसे स्वत: पूर्ण ड्रॉप-डाउन को लागू करने जा रहे हैं, तो सूची में डेटा प्रदान करने के बाद YUI3 का स्वत: पूर्ण विजेट आपके लिए सबकुछ करेगा। यदि आप बड़े डेटा द्वारा समर्थित स्वत: पूर्णता के लिए केवल यूआईआई 3 का उपयोग करते हैं, तो टीएसटी आधारित वेब सेवाओं को सी ++ में बनाएं, और फिर सरल सूची के बजाय वेब सेवा से डेटा लाने के लिए स्वत: पूर्ण विजेट के स्क्रिप्ट नोड डेटा स्रोत का उपयोग करें।
आप सबसे लोकप्रिय प्राप्तियां, एक एक अच्छा विकल्प "ट्री का सुझाव दें" हो सकता है का सुझाव देना चाहते हैं: Suggest Tree
Segment trees कुशलतापूर्वक auto complete
कुछ हद तक संबंधित लागू करने के लिए इस्तेमाल किया जा सकता का गूगल के पीटर Norvig का विवरण यहाँ है वर्तनी सुधार कैसे करें: http://norvig.com/spell-correct.html –
एक मानक ट्री बहुत स्मृति गहन है, बड़े सेट के लिए आप एक कॉम्पैक्टेड ट्री का उपयोग करना चाहते हैं जो स्मृति पदचिह्न को बहुत कम करता है। अतिरिक्त अनुकूलन में नोड मानों के आलसी प्रारंभिकरण और बच्चों/मूल्य सेट के लिए सही डेटा संरचनाएं शामिल हैं। कुछ समय पहले मैंने एक [स्वतः पूर्ण लाइब्रेरी] (https://github.com/fmmfonseca/completely) बहुत बड़े डेटा सेट (10,000,000+) को संभालने में सक्षम बनाया और कुशलतापूर्वक सटीक और अनुमानित खोजों का उत्तर दिया। –