फास्ट सबस्ट्रिंग सर्च एल्गोरिदम का उपयोग हजारों बहुत बड़ी फाइलों के साथ आईडीई के एक प्रकार द्वारा किया जा सकता है

Question

मैं एक आईडीई के समान कुछ विकसित कर रहा हूं जो हजारों बहुत बड़ी (टेक्स्ट) फ़ाइलों को संभाल लेगा और मैं इस विषय में कला की स्थिति का सर्वेक्षण करना क्या है।

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

धन्यवाद

Answer 1

वर्तमान में, इस परियोजना में IntelliJ विचार अनुक्रमणिका फ़ाइलें, और याद है जो 3-ग्राम (3 अक्षर या अंक के दृश्यों) जो फ़ाइलों में होते हैं। खोज करते समय, यह क्वेरी को 3-ग्राम में विभाजित करता है, उन सभी ट्रिग्राम वाले इंडेक्स से फ़ाइलें प्राप्त करता है, उन सेटों को छेड़छाड़ करता है और उन फ़ाइलों में से प्रत्येक में अपेक्षाकृत सरल पाठ खोज का उपयोग करता है ताकि यह जांच सके कि क्या वे वास्तव में पूरी खोज रखते हैं या नहीं स्ट्रिंग।

Answer 2

आप Apache Lucene पर एक नज़र ले सकता है। यह जावा में पूरी तरह से लिखा गया एक टेक्स्ट सर्च इंजन लाइब्रेरी है। यह आपके उपयोग के लिए थोड़ा अधिक भारी हो सकता है, लेकिन चूंकि यह खुला स्रोत है, इसलिए आप यह देख सकते हैं कि यह कैसे काम करता है।

इसमें demo है जो आपको एक इंडेक्स बनाने और लाइब्रेरी स्रोत कोड के माध्यम से खोजने की ओर ले जाता है, जो कि आप जो करना चाहते हैं, उतना ही लगता है।

इसके अलावा, Boyer-Moore स्ट्रिंग खोज एल्गोरिदम पर एक नज़र डालें। यह स्पष्ट रूप से आमतौर पर उन अनुप्रयोगों में उपयोग किया जाता है जो एक ctrl + f शैली दस्तावेज़ खोज प्रदान करते हैं। इसमें खोज शब्द को पूर्व-प्रोसेसिंग करना शामिल है ताकि यह यथासंभव कम तुलना में चला सके।

Answer 3

जैसा कि जेएस 441 ने इंगित किया है कि अपाचे ल्यूसीन एक अच्छा विकल्प है, लेकिन केवल तभी यदि आप टर्म आधारित खोज करने जा रहे हैं, तो Google कैसे काम करता है। यदि आपको मनमानी तारों की खोज करने की आवश्यकता है जो शब्दों को फैलाते हैं तो लुसीन आपकी मदद नहीं करेगा।

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

केवल संपादित फ़ाइलों को खोजने के मामले में मदद करने के लिए, आप दो इंडेक्स रख सकते हैं, एक बड़ी फाइलों के लिए और दूसरा हाल ही में संपादित फ़ाइलों के लिए। तो जब आप खोज करते हैं तो आप दोनों सूचकांक में खोज करेंगे। समय-समय पर आपको स्थायी फाइलों को नई फाइलों की सामग्री के साथ पुनर्निर्माण करना चाहिए और पुराने को प्रतिस्थापित करना चाहिए।

यहाँ के कुछ उदाहरण हैं जब Lucene अच्छा है और जब प्रत्यय पेड़ अच्छा है:

मान लें आप एक दस्तावेज़ है जिसमें निम्न शामिल है:

एक त्वरित भूरे कुत्ते आलसी लोमड़ी लांघ गया है।

• त्वरित
• जल्दी भूरी
• क्ष *

• क्ष * ख

  कुछ चाल के साथ आप निम्नलिखित कर सकते हैं:

Lucene निम्न खोज के लिए अच्छा है खोजें अच्छी तरह से काम:

'* ick * खुद'

इस प्रकार की खोज बहुत धीमी गति से

'क्यू * ick भूरे रंग d * जी'

और खोज के इस प्रकार चलेंगे कुछ भी

कभी नहीं मिलेगा

"ick brown d"

लुसीन भी अच्छा है जब आप अपने दस्तावेज़ों को शब्दों के बैग के रूप में देखते हैं। तो आप इस

त्वरित लोमड़ी

जो तुम सभी दस्तावेजों कोई बात नहीं क्या बीच में है जल्दी शब्द और लोमड़ी है कि मिल जाएगा इस तरह की खोजों को आसानी से कर सकते हैं।

दूसरी ओर प्रत्यय पेड़ दस्तावेज़ के भीतर सबस्ट्रिंग के सटीक मिलानों की खोज के साथ अच्छी तरह से काम करते हैं, यहां तक ​​कि उन मामलों में जब आपकी खोज शब्द को फैलती है और शब्द के मध्य में शुरू होती है और समाप्त होती है।

बड़े सरणियों के प्रत्यय के पेड़ के निर्माण के लिए बहुत अच्छा एल्गोरिथ्म here वर्णन किया गया है (Warnign paywalled)।