2011-10-04 12 views
6

मैं टेक्स्ट फ़ाइलों में काम कर रहा हूं। मैं जावा में एक खोज एल्गोरिदम लागू करना चाहता हूँ। मेरे पास एक टेक्स्ट फाइल है जो मुझे खोजने की ज़रूरत है।टेक्स्ट फ़ाइल में एकाधिक स्ट्रिंग्स की खोज कैसे करें

यदि मैं एक शब्द खोजना चाहता हूं तो मैं इसे सभी पाठ को हैशैप में डालकर और प्रत्येक शब्द की घटना को संग्रहीत करके कर सकता हूं। लेकिन क्या कोई एल्गोरिदम है यदि मैं दो तारों (या अधिक हो सकता है) खोजना चाहता हूं? क्या मुझे दो की जोड़ी में तार है?

आप केवल या किसी सबस्ट्रिंग पूरे शब्द के लिए खोज रहे हैं:

उत्तर

3

यह टेक्स्ट फ़ाइल के आकार पर बहुत निर्भर करता है। आम तौर पर कई मामलों पर गौर करना चाहिए:

  1. लॉट के बहुत ही कम दस्तावेजों पर प्रश्नों (वेब ​​पृष्ठ, निबंध लंबाई आदि के ग्रंथों) की। सामान्य भाषा की तरह पाठ वितरण। एक साधारण ओ (एन^2) एल्गोरिदम ठीक है। लंबाई एन की एक क्वेरी के लिए बस लंबाई की खिड़की लें और इसे स्लाइड करें। जब तक आपको कोई मिलान न मिल जाए तब तक विंडो की तुलना करें और स्थानांतरित करें। यह एल्गोरिदम शब्दों के बारे में परवाह नहीं करता है, इसलिए आप पूरी खोज को एक बड़ी स्ट्रिंग (रिक्त स्थान समेत) के रूप में देखते हैं। शायद यह है कि अधिकांश ब्राउज़र क्या करता है। केएमपी या बॉयर मूर प्रयास के लायक नहीं है, क्योंकि ओ (एन^2) मामला बहुत दुर्लभ है।

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

  3. यदि आपके पास कई दस्तावेज हैं जहां आपके पास उच्च रिडंडेंसी है और आपके संग्रह अक्सर बदलते हैं, तो केएमपी या बॉयर मूर का उपयोग करें। उदाहरण के लिए यदि आप डीएनए डेटा में कुछ अनुक्रमों को ढूंढना चाहते हैं और आपको अक्सर प्रयोगों से नए डीएनए खोजने के लिए नए अनुक्रम मिलते हैं, तो बेवकूफ एल्गोरिदम के ओ (एन^2) भाग आपके समय को मार देंगे।

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

1

कुछ और अधिक विस्तार एक दृष्टिकोण का सुझाव से पहले की आवश्यकता है?

क्या आप एक ही अपरिवर्तित फ़ाइल में कई अलग-अलग शब्दों की खोज करने जा रहे हैं?

क्या आप उन शब्दों को जानते हैं जिन्हें आप एक ही बार में खोजना चाहते हैं?

तारों के लिए कई कुशल (रैखिक) खोज एल्गोरिदम हैं। यदि संभव हो तो मैं उस व्यक्ति का उपयोग करने का सुझाव दूंगा जो आपके लिए पहले से ही लिखा गया है।

http://en.wikipedia.org/wiki/String_searching_algorithm

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

+0

मैं एक ऐसा शब्द खोजना चाहता हूं जो सबस्ट्रिंग नहीं हो सकता है (मैं अभी तक जंगली पात्रों से निपटना नहीं चाहता हूं)। हां, मैं एक ही फाइल में कई अलग-अलग शब्दों की खोज करने जा रहा हूं। नहीं, मैं उन शब्दों को नहीं जानता जो मैं खोज खोजना चाहता हूं उपयोगकर्ता पर निर्भर करता है। हां, मुझे स्लाइडिंग विंडो का विचार मिला लेकिन समस्या स्लाइडिंग विंडो का आकार है क्योंकि मैं एक शब्द या दो शब्दों को एकसाथ खोज सकता हूं। पूर्व। अगर मैं इस वेब पेज में 1 के रूप में खोज सकता हूं। कई 2।कई अलग-अलग 3. कई अलग-अलग शब्द। यहां, स्लाइडिंग विंडो का आकार क्या हो सकता है? – Arjit

+0

राबिन कार्प कुछ विशेष परिस्थितियों में केवल केएमपी या बॉयर मूर के साथ तुलनात्मक रूप से तुलनीय है (मूल रूप से एक ही समय में एक से अधिक स्ट्रिंग खोजना), अन्यथा दूसरों में से एक के साथ जाना सर्वोत्तम है। यदि आप एक बार में शब्दों के बड़े सेट खोजना चाहते हैं, तो राबिन कार्प दिलचस्प हो जाता है और इसे लागू करने के लिए तुच्छ है। – Voo

+0

ब्राउज़र कैसे करता है? क्रोम की तरह? कौन सा अहंकार इसका उपयोग करता है। क्योंकि मैं प्रभाव प्राप्त करने की कोशिश कर रहा हूं कि ब्राउज़र में – Arjit

संबंधित मुद्दे