एक साधारण उलटा इंडेक्स कैसे बनाया जाए?

Question

मैं ल्यूसीन जैसे किसी एपीआई के बिना सर्च इंजन का एक सरल इंडेक्सिंग फ़ंक्शन बनाना चाहता हूं। उलटा इंडेक्स में, मुझे बस प्रत्येक शब्द की बुनियादी जानकारी रिकॉर्ड करने की आवश्यकता है, उदा। डॉकिड, स्थिति, और freqence।

1. डेटा संरचना किस तरह अक्सर उल्टे सूचकांक के निर्माण के लिए प्रयोग किया जाता है:

   अब, मैं कई प्रश्न हैं? बहुआयामी सूची?

2. इंडेक्स बनाने के बाद, इसे फाइलों में कैसे लिखना है? फ़ाइल में किस तरह का प्रारूप? एक टेबल की तरह? कागज पर एक सूचकांक तालिका ड्राइंग की तरह?

Answer 1

आप उलटा इंडेक्स का एक बहुत ही सरल कार्यान्वयन देख सकते हैं और TinySearchEngine में खोज सकते हैं।

val invertedIndex = new collection.mutable.HashMap[String, List[Posting]] 

या एक जावा-esque:

HashMap<String, List<Posting>> invertedIndex = new HashMap<String, List<Postring>>(); 

अपने पहले प्रश्न के लिए, यदि आप एक सरल (स्मृति में) उल्टा सूचकांक का निर्माण करना चाहते सीधा डेटा संरचना इस तरह की एक हैश नक्शा है

हैश पोस्टिंग की सूची में प्रत्येक शब्द/शब्द/टोकन को मानचित्र करता है।

case class Posting(docId:Int, var termFrequency:Int) 

एक नया दस्तावेज़ अनुक्रमण यह tokenizing (टोकन/शब्दों में अलग करने) का मामला है और प्रत्येक टोकन के लिए एक नई पोस्ट डालने: एक Posting सिर्फ एक उद्देश्य यह है कि एक दस्तावेज के अंदर एक शब्द का एक घटना का प्रतिनिधित्व करता है हैश मानचित्र की सही सूची में। बेशक, यदि उस विशिष्ट दस्तावेज़ में उस शब्द के लिए एक पोस्टिंग पहले से मौजूद है, तो आप शब्द आवृत्ति बढ़ाते हैं। ऐसा करने के अन्य तरीके हैं। मेमोरी इनवर्टेड इंडेक्स में यह ठीक है, लेकिन ऑन-डिस्क इंडेक्स के लिए आप शायद Postings को सही termFrequency के साथ हर बार अपडेट करने के बजाय डालना चाहते हैं।

अपने दूसरे प्रश्न के बारे में, वहाँ आम तौर पर दो मामले हैं:

(1) आप एक (लगभग) अपरिवर्तनीय सूचकांक है। आप एक बार अपने सभी डेटा इंडेक्स करते हैं और यदि आपके पास नया डेटा है तो आप केवल रीइंडेक्स कर सकते हैं। उदाहरण के लिए, एक घंटे में कई बार वास्तविक समय या अनुक्रमण की आवश्यकता नहीं है।

(2) नए दस्तावेज़ हर समय आते हैं, और आपको जितनी जल्दी हो सके नए आगमन दस्तावेजों की खोज करने की आवश्यकता है। - उल्टे सूचकांक फ़ाइल

1:

मामले के लिए (1), आप कम से कम 2 फ़ाइलें हो सकता है। यह प्रत्येक शब्द के लिए सभी Postings (docId/termFrequency जोड़े) के लिए सूचीबद्ध करता है। यहां सादे पाठ में दर्शाया गया है, लेकिन आमतौर पर बाइनरी डेटा के रूप में संग्रहीत किया जाता है।

Term1<docId1,termFreq><docId2,termFreq><docId3,termFreq><docId4,termFreq><docId5,termFreq><docId6,termFreq><docId7,termFreq> 
Term2<docId3,termFreq><docId5,termFreq><docId9,termFreq><docId10,termFreq><docId11,termFreq> 
Term3<docId1,termFreq><docId3,termFreq><docId10,termFreq> 
Term4<docId5,termFreq><docId7,termFreq><docId10,termFreq><docId12,termFreq> 
... 
TermN<docId5,termFreq><docId7,termFreq> 

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

Term1 -> 0 
Term2 -> 126 
Term3 -> 222 
.... 

इस 2 फ़ाइलें आप (और आमतौर पर होगा) फ़ाइल (फ़ाइलें) प्रत्येक शब्द के IDF और प्रत्येक दस्तावेज़ के आदर्श स्टोर करने के लिए हो सकता है के साथ साथ

।

मामले के लिए (2), मैं संक्षेप में यह बताने की कोशिश करूंगा कि Lucene (और इसके परिणामस्वरूप Solr और ElasticSearch) ऐसा करें।

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

इस "विभाजित" इंडेक्स में एक क्वेरी करने के लिए आप प्रत्येक अलग इंडेक्स (समानांतर में) के खिलाफ क्वेरी चला सकते हैं और उपयोगकर्ता को लौटने से पहले परिणामों को एक साथ मर्ज कर सकते हैं।

लुसेन इस "छोटी" इंडेक्स segments पर कॉल करता है।

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