ल्यूसीन की खोज की जटिलता

Question

यदि मैं लिखता हूं और एल्गोरिदम जो ल्यूसीन का उपयोग करके खोज करता है तो मैं इसकी कम्प्यूटेशनल जटिलता कैसे कह सकता हूं? मुझे पता है कि लुसीन टीएफ * आईडीएफ स्कोरिंग का उपयोग करता है लेकिन मुझे नहीं पता कि यह कैसे कार्यान्वित किया जाता है। मैंने पाया tf * आईडीएफ निम्नलिखित जटिलता है कि:

O(|D|+|T|) 

जहां डी दस्तावेजों और टी सभी नियमों के सेट का सेट है।

हालांकि, मुझे किसी ऐसे व्यक्ति की आवश्यकता है जो यह जांच सके कि यह सही है और मुझे क्यों समझाएं।

आप

Answer 1

Lucene मूल रूप से एक tf-idf योजना के साथ एक Vector Space Model (वीएसएम) का उपयोग करता है धन्यवाद। तो, मानक स्थापित करने में हमने:

• दस्तावेजों का एक संग्रह प्रत्येक एक वेक्टर
• भी एक वेक्टर के रूप में प्रतिनिधित्व एक पाठ क्वेरी

हम साथ संग्रह की K दस्तावेजों का निर्धारण के रूप में प्रतिनिधित्व क्वेरी q पर उच्चतम वेक्टर स्पेस स्कोर। आम तौर पर, हम कम करने वाले क्रम में स्कोर द्वारा आदेशित इन के शीर्ष दस्तावेजों की तलाश करते हैं; उदाहरण के लिए कई खोज इंजन दस सर्वोत्तम परिणामों के पहले पृष्ठ को पुनर्प्राप्त करने और रैंक-ऑर्डर करने के लिए K = 10 का उपयोग करते हैं।

कंप्यूटिंग वेक्टर अंतरिक्ष स्कोर के लिए बुनियादी एल्गोरिथ्म है:

float Scores[N] = 0 
Initialize Length[N] 
for each query term t 
do calculate w(t,q) and fetch postings list for t (stored in the index) 
    for each pair d,tf(t,d) in postings list 
    do Scores[d] += wf(t,d) X w(t,q) (dot product) 
Read the array Length[d] 
for each d 
do Scored[d] = Scores[d]/Length[d] 
return Top K components of Scores[] 

कहाँ

• सरणी LengthN दस्तावेजों से प्रत्येक के लिए लंबाई (सामान्य कारकों) रखती है, सरणी Scores जबकि प्रत्येक दस्तावेज़ के लिए स्कोर रखता है।
• tf एक दस्तावेज़ में एक शब्द की अवधि आवृत्ति है।
• w(t,q) किसी दिए गए अवधि के लिए सबमिट की गई क्वेरी का भार है। ध्यान दें कि क्वेरी को bag of words के रूप में माना जाता है और वजन के वेक्टर को माना जा सकता है (जैसे कि यह एक और दस्तावेज़ था)। Complexity of vector dot-product, वेक्टर डॉट उत्पाद O(n) है:
• wf(d,q) क्वेरी और दस्तावेज़

के रूप में यहाँ वर्णित के लिए लघुगणक अवधि भार है। यहां आयाम हमारी शब्दावली में शब्दों की संख्या है: |T|, जहां T शर्तों का सेट है।

तो, यह एल्गोरिथ्म के समय जटिलता है:

O(|Q|· |D| · |T|) = O(|D| · |T|) 

हम इस पर विचार | क्यू | निश्चित, जहां Q क्वेरी में शब्दों का सेट है (जो औसत आकार कम है, औसत में 2 और 3 शब्दों के बीच एक क्वेरी होती है) और D सभी दस्तावेज़ों का सेट है।

हालांकि, एक खोज के लिए, ये सेट बाध्य हैं और इंडेक्स अक्सर बढ़ने की प्रवृत्ति नहीं करते हैं।इसलिए, नतीजतन, वीएसएम का उपयोग करके खोज वास्तव में तेज़ हैं (जब T और D बड़ी हैं तो खोज वास्तव में धीमी है और किसी को वैकल्पिक दृष्टिकोण मिलना है)।