वेबपृष्ठ में शब्दों को खोजने के लिए ब्राउज़र द्वारा उपयोग किए जाने वाले एल्गोरिदम

Question

किसी शब्द की खोज करने के लिए ब्राउज़र में कौन सी डेटा संरचना या एल्गोरिदम का उपयोग किया जाता है? क्या ब्राउज़र एक त्रिभुज या प्रत्यय पेड़ का निर्माण करेगा?

धन्यवाद
बाला

Answer 1

एक त्रिभुज/प्रत्यय पेड़ के साथ खोज तेजी से है - लेकिन शुरू करने के लिए त्रिभुज का निर्माण काफी धीमा है। इसका मतलब है कि वे केवल की अपेक्षा करते हैं, ताकि वे उसी डेटा पर बड़ी संख्या में खोज कर सकें, ताकि आप कई खोजों पर ट्राई बनाने के लिए समय को बढ़ा सकें।

वेब पेज के अंदर खोजों की औसत संख्या शायद आंशिक है (यानी आप उम्मीद करते हैं कि उपयोगकर्ता एक बार भी खोज करने से पहले कई पेज लोड करे)। यहां तक ​​कि जब आप एक पृष्ठ खोजते हैं, उसी पृष्ठ में बहुत सी खोज करना शायद दुर्लभ है।

इसका मतलब है कि एक रैखिक खोज लगभग हमेशा अधिक एक त्रिभुज या प्रत्यय पेड़ से अधिक कुशलता से प्रभावी होगी। मेरा अनुमान है कि अगर वे इसे strstr() पर एक साधारण कॉल से ऑप्टिमाइज़ करने से परेशान करते हैं, तो वे केवल स्ट्रिंग खोज के बॉयर-मूर परिवार में कुछ भी जाते हैं। वेब पेज में आप जिन खोजों की अपेक्षा करते हैं, उन्हें देखते हुए, यह आमतौर पर खत्म हो जाएगा, इससे पहले कि आप केवल त्रिभुज के शुरुआती निर्माण कर सकें, ताकि आप से इसकी खोज कर सकें।

इंटरैक्टिव उपयोग के लिए, आपकी प्राथमिक चिंता तात्कालिक दिखाई देने के लिए पर्याप्त तेज़ी से परिणाम दे रही है। इसका मतलब आम तौर पर 100ms या उससे भी कम के भीतर होता है। बोयर-मूर-Horspool का एक अच्छा कार्यान्वयन के साथ, कि पाठ की राशि है कि हो सकता है पागल एक वेब पेज (मेगाबाइट या गीगाबाइट के सैकड़ों के आदेश पर) में शामिल करने के लिए खोज करने के लिए पर्याप्त समय है।

यदि आप इसे परीक्षण में रखना चाहते हैं, तो मैं बॉय स्टउट की Snippets साइट से बॉयर-मूर-हॉर्सपूल (Bmhsrch.C) के रे गार्डनर के कार्यान्वयन की सिफारिश करता हूं। मैं वास्तव में से नफरत करता हूं ताकि वेब पेज को 20 एमएस तक कब्जा रखने के लिए काफी बड़ा हो, 100 का उल्लेख न करें (हालांकि मैं इस विशेष कार्यान्वयन को स्वीकार करने वाला पहला व्यक्ति असाधारण रूप से तेज़ हूं)।

Answer 2

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

कुल मिलाकर, मुझे नहीं लगता कि यह ब्राउज़र एल्गोरिदम में बड़े मुद्दों में से एक है।

Answer 3

को समझने के लिए क्यों एक रेखीय स्कैन काफी तेजी से है, पर विचार कितना अधिक जटिल पृष्ठ प्रतिपादन है और कितनी तेजी से यह हो गया है (जो स्पष्ट रूप से कम से कम HTML की एक रैखिक स्कैन की आवश्यकता है)। मुझे लगता है कि ब्राउज़र अवसरों को हाइलाइट करने में बहुत अधिक समय बिताएगा, वैसे भी।

इसके अलावा, खोज को क्रमशः किया जा सकता है। कहो, मैं "एल्गोरिदम" खोज रहा हूं। जब मैं "एक" टाइप करें, ब्राउज़र पर मिले (या असमकालिक की तलाश शुरू) पत्र "एक" और बाद में प्रतीकों केवल वर्तमान निष्कर्षों को निखारने की आवृत्तियां।

Answer 4

नियमित अभिव्यक्ति की सरल उपयोग सिर्फ पर्याप्त से अधिक है। विभिन्न ऑनलाइन उपकरणों पर एक नज़र डालें।