✖

LogLog: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ

Linear Counting और Min Value वाले पिछले भागों के बाद अब हम आख़िरकार आँकड़ा-समूह में भिन्न मानों की संख्या का अनुमान लगाने वाले लगभग सबसे बढ़िया प्रायिकतात्मक एल्गोरिद्म, LogLog, तक पहुँचे हैं। इससे बेहतर केवल उसका छोटा भाई HyperLogLog है, जो LogLog पर आधारित है, पर उसकी बात अगली बार।

आइए, समस्या दोहरा लें। इनपुट पर कोई आँकड़ा-समूह/बहुसमुच्चय (multiset) है, उदाहरण के लिए पहचानकर्ताओं की कोई सरणी/जनरेटर। इस सरणी में कुछ मान कई बार आते हैं और हम इस सरणी में अद्वितीय मानों की संख्या गिनना चाहते हैं। इस संख्या को हम गणनसंख्या (कार्डिनैलिटी) कहेंगे। हम अपेक्षा करते हैं कि यह गणनसंख्या सचमुच बड़ी होगी, अन्यथा हम पारंपरिक एल्गोरिद्म का प्रयोग कर सकते हैं।

LogLog एल्गोरिद्म का विचार

मान लीजिए हमारे पास द्विआधारी सदिशों (binary vectors) का एक समूह है। घबराइए नहीं, उदाहरण के लिए 0001011001001100 लंबाई 16 का एक द्विआधारी सदिश है। मान लीजिए हमारे पास लंबाई 32 के द्विआधारी सदिश हैं, कुल दस लाख, और सभी पूरी तरह यादृच्छिक रूप से जनित हैं। कितने सदिश शून्य पर समाप्त होंगे?

स्वाभाविक है कि यह हम सटीक रूप से नहीं जान सकते, परंतु यदि हमने सदिश सचमुच यादृच्छिक रूप से जनित किए हैं, तो लगभग आधे, यानी 5 लाख, शून्य पर समाप्त होने चाहिए। कितने सदिश 00 पर समाप्त होंगे? एक चौथाई। 000 पर? आठवाँ भाग। और इसी तरह आगे। इसे हम मोटे तौर पर ऐसे दिखा सकते हैं:

सदिश का पैटर्न     सभी सदिशों में हिस्सा
...xxxxxx0        50%
...xxxxx00        25%
...xxxx000        12.5%
...xxx0000        6.25%
     ...          ...

यदि हम लंबाई d का कोई प्रत्यय (suffix) लें (प्रत्यय वह स्ट्रिंग है, जिस पर कोई दूसरी स्ट्रिंग समाप्त होती है — उपसर्ग (prefix) का उलटा), तो हम अपेक्षा करते हैं कि v सदिश इस प्रत्यय पर समाप्त होंगे। मान v हम इस प्रकार परिकलित करते हैं:

v=12d⋅N

जहाँ N समूह में सभी सदिशों की संख्या है। लंबाई 3 का प्रत्यय (उदाहरण के लिए …010) 1/2^3 N = 1/8 N सदिशों में आना चाहिए, यानी सभी सदिशों के 12.5% में।

अब एक छोटी-सी दिमाग़ घुमा देने वाली बात। मान लीजिए 1024 अद्वितीय सदिशों का एक बहुसमुच्चय है। कितने सदिश प्रत्यय 0000000000 (दस शून्य) पर समाप्त होने चाहिए? सूत्र में मान रखने पर हमें मिलता है

v=1210⋅1024=11024⋅1024=1

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

व्यापकीकरण और एल्गोरिद्म की रचना

लक्ष्य ऐसा प्रत्यय ढूँढना होना चाहिए, जो केवल एक सदिश में हो और साथ ही यथासंभव छोटा हो। परंतु यह बहुत कठिन है, क्योंकि ऐसा सदिश सचमुच ढूँढने के लिए हमें सभी प्रत्यय सहेजने पड़ते, जो हम नहीं चाहते, क्योंकि इसमें बहुत अधिक मेमोरी लगेगी। इसके बजाय हम इतने से संतोष कर लेंगे कि सदिश के अंत में शून्यों का सबसे लंबा अनुक्रम ढूँढें।

इसलिए हम सभी सदिशों से गुज़रते हैं, प्रत्येक सदिश के लिए गिनते हैं कि उसके अंत में कितने शून्य हैं और एक चर में इन मानों का अधिकतम रखते हैं। सभी सदिशों से गुज़र जाने पर हमें केवल शून्यों से बने सबसे लंबे प्रत्यय की लंबाई पता होगी। इस लंबाई को हम अक्षर d से दर्शाते हैं। अब हम पिछले सूत्र को इस तरह बदलते हैं कि चर N को अलग कर लें, ताकि यह एल्गोरिद्म का आउटपुट हो, इनपुट नहीं। साथ ही v के स्थान पर हम एक रख सकते हैं, क्योंकि हम अपेक्षा करते हैं कि ऐसा एक ही सदिश मिलेगा, अर्थात् हम अपेक्षा करते हैं कि v=1 होगा।

v=N2dv⋅2d=N2d=N

इस प्रकार यदि हमें शून्यों के सबसे लंबे प्रत्यय की लंबाई d मिल जाए, तो हम सूत्र N=2d से गणनसंख्या का अनुमान लगाते हैं।

यादृच्छिक द्विआधारी सदिश कैसे प्राप्त करें?

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

अब हम अपना एल्गोरिद्म लिख सकते हैं:

def trailing_zeroes(number):
    if number == 0: 
        return 0

    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def count_unique(values):
    max_zero_suffix_length = 0
    for value in values:
        zeroes_length = trailing_zeroes(hash(value))
        max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
    return 2 ** max_zero_suffix_length

फलन trailing_zeroes संख्या के अंत में शून्यों की संख्या लौटाता है। यह ऐसा कैसे करता है? यदि आप कोड से नहीं समझे, तो बेहतर है कि पूछिए ही मत। और फलन कितना सफल है? एक लाख अद्वितीय अवयवों वाले समुच्चय के लिए फलन ने अनुमान 5,24,288 लौटाया।

ख़ैर…

यह बहुत अच्छा तो नहीं है, है न? पर कोई बात नहीं! हम एल्गोरिद्म को उसी तरह सुधारने का प्रयास करेंगे, जैसे पिछले Min Value को सुधारा था। हम इनपुट आँकड़ों को कुछ असंयुक्त समूहों में बाँटेंगे, प्रत्येक समूह के लिए शून्यों का अधिकतम प्रत्यय गिनेंगे, अंत में शून्यों वाले प्रत्यय की औसत लंबाई परिकलित करेंगे और उसी से अद्वितीय मानों की संख्या का अनुमान लगाएँगे।

उदाहरण के लिए, हम तय कर सकते हैं कि प्रत्येक सदिश के अंतिम दो बिट उस समूह की संख्या बताएँगे, जिसमें सदिश आता है। ये छह सदिश

1101110111111011     1110110010100101
1011001111110010     1111101100000011
1010101000100000     0110010110011000

हम उनके अंतिम दो बिटों के आधार पर चार समूहों में बाँट सकते हैं:

00                   01              
1010101000100000     1110110010100101
0110010110011000                     

10                   11
1011001111110010     1101110111111011
                     1111101100000011

आगे हम प्रत्येक सदिश में शून्यों के सबसे लंबे प्रत्यय की लंबाई गिनते हैं, परंतु उन बिटों को छोड़ देते हैं, जिनका प्रयोग हमने समूह की संख्या के रूप में किया। शून्यों वाले “प्रत्यय” हम हरे रंग से दिखाते हैं:

00                   01                     
1010101000100000     1110110010100101    
0110010110011000

10                   11
1011001111110010     1101110111111011
                     1111101100000011

00: 3                01: 0
10: 2                11: 6

सूची के अंत में प्रत्येक समूह के शून्यों वाले सबसे लंबे प्रत्यय की लंबाई दी गई है। इन प्रत्ययों से हम समांतर माध्य परिकलित कर सकते हैं, जो 2.75 है। इस मान को सूत्र में रखने पर हमें मिलता है

22.75≈6.727

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

पूरे समुच्चय की गणनसंख्या का अनुमान लगाने के लिए हमें इस मान को समूहों की संख्या से गुणा करना होगा: 6.727 · 4 = 26.908। एल्गोरिद्म ने परिकलित किया कि आँकड़ा-समूह में लगभग 27 अद्वितीय मान हैं। वास्तव में छह थे, इसलिए यह पूरी तरह गलत है, पर अभी इससे सचमुच फ़र्क नहीं पड़ता।

एल्गोरिद्म का कार्यान्वयन

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets

प्राचल k बताता है कि कितने बिट समूह (bucket) के सूचकांक के रूप में लिए जाएँगे। यह प्राचल एल्गोरिद्म की सटीकता तय करता है — k जितना अधिक, सटीकता उतनी अधिक। चर bucket_index में समूह की संख्या रखी जाती है। बराबर के चिह्न के दाईं ओर वाला जादू कैसे काम करता है?

चर num_buckets में समूहों की संख्या है, जो हमेशा दो की कोई घात होती है। उदाहरण के लिए, यदि k = 3 है, तो num_buckets=8। द्विआधारी पद्धति में संख्या 8 का रूप 1000 है। एक घटाने पर हमें संख्या 7 मिलती है, जिसका रूप 0111 है। num_buckets में से एक घटाने पर हमें हमेशा ऐसी संख्या मिलती है, जिसके अंत में k इकाइयाँ (1) और उससे पहले केवल शून्य होते हैं। फिर हम बिटवाइज़ AND संक्रिया (operator &) करते हैं। सदिश 1110110010100101 के लिए यह संक्रिया ऐसी दिखेगी:

  1110110010100101
& 0000000000000111
------------------
  0000000000000101

इस पूरे जादू का उद्देश्य ऐसी संख्या प्राप्त करना है, जिसकी शुरुआत में केवल शून्य हों और जिसके अंतिम k बिट दिए गए हैश h जैसे ही हों।

आगे हम bucket_hash परिकलित करते हैं, यानी हैश h, जिसमें से हम अंतिम k बिट इस तरह हटाते हैं कि पूरे हैश को k बिट दाईं ओर खिसका देते हैं (बिट शिफ़्ट)। शिफ़्ट संख्या के सभी बिटों को बस k बिट दाईं ओर खिसका देता है और बाईं ओर से संख्या में शून्य भर दिए जाते हैं। (एक बिट दाईं ओर शिफ़्ट करना वैसा ही है, जैसे संख्या को दो से भाग देकर शेषफल छोड़ देना।) सदिश 1110110010100101 को तीन बिट शिफ़्ट करने पर हमें 0001110110010100 मिलता। यह सदिश चर bucket_hash में सहेजा जाता।

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

अंत में केवल सभी समूहों में शून्यों की औसत संख्या परिकलित करते हैं और ज्ञात करते हैं कि प्रत्येक समूह में अद्वितीय अवयवों की औसत संख्या कितनी है (2 ** average_max_zeros)। कुल num_buckets समूह हैं, इसलिए हम इस मान को समूहों की संख्या से गुणा करते हैं, जिससे हमें अद्वितीय अवयवों की संख्या का अंतिम अनुमान मिलता है। उफ़, और दर्द भी नहीं हुआ। 2,50,000 अद्वितीय मानों वाले कुछ आँकड़ा-समूहों और k=10 के लिए परिणाम:

331774.56203
323349.39265
307343.444439
309430.914045
294512.379123

नहीं-नहीं, अब भी गलत :-(। पर चिंता न करें, हम काफ़ी निकट हैं। ध्यान दीजिए कि सभी परिणाम सही परिणाम से बड़े हैं। एल्गोरिद्म के दौरान अलग-अलग त्रुटियाँ जमा हो जाती हैं, इसलिए अनुमान सही परिणाम से काफ़ी बड़ा होता है। फिर भी ये त्रुटियाँ काफ़ी स्थिर हैं और अनुमान लगाया जा सकता है कि त्रुटि कितनी बड़ी हुई। यदि हम अनुमान को संशोधन अचर 0.79402 से गुणा करें, तो हमें कहीं बेहतर परिणाम मिलते हैं:

263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445

मैंने दस लाख गणनसंख्या वाला एक बहुसमुच्चय भी आज़माया, परिणाम:

परिणाम                अनुपात (परिणाम / सही मान)
1017297.17411         1.01729717411
1022820.99717         1.02282099717
984108.725487         0.984108725487
1018675.32683         1.01867532683
1007020.2853          1.0070202853

बहुत बढ़िया! त्रुटि 2.5% से कम रहती है, जो अच्छा प्रदर्शन है। और देवियो और सज्जनो, यही है एल्गोरिद्म LogLog। संशोधन अचर सहित अंतिम कार्यान्वयन ऐसा दिखता है:

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets * 0.79402

इस एल्गोरिद्म को बदलकर वह प्रसिद्ध और सबसे बढ़िया HyperLogLog कैसे बनाएँ, यह हम अगली बार देखेंगे। अभी हम यह देखेंगे कि एल्गोरिद्म को कितनी मेमोरी चाहिए।

मेमोरी की आवश्यकता

प्रयुक्त मेमोरी के मामले में एल्गोरिद्म बहुत कुशल है। हमें केवल अधिकतम मानों वाली सरणी याद रखनी है। इस सरणी की लंबाई k के मान पर निर्भर करती है, अर्थात् सदिश के उन बिटों की संख्या पर, जिन्हें हम समूह के सूचकांक के रूप में लेते हैं। दिए गए k के लिए कुल 2k भिन्न समूह होते हैं, इसलिए अधिकतम मानों की सरणी की लंबाई 2k है। कार्यान्वयन में इस मान को हमने num_buckets कहा था।

सरणी का एक खाना कितना बड़ा होना चाहिए? इसमें हम शून्यों वाले प्रत्ययों की लंबाइयाँ सहेजेंगे। मैं पहले ही बता दूँ कि 64-बिट हैश शायद दुनिया के सभी कल्पनीय बहुसमुच्चयों के लिए पर्याप्त है, इसलिए इस सरणी में हमें 0 (केवल इकाइयों वाला सदिश) से 64 (केवल शून्यों वाला सदिश) तक की संख्याएँ सहेज पाने चाहिए। इसके अलावा, यदि हम मानें कि k हमेशा शून्य से बड़ा होगा, तो 0 से 63 तक की संख्याएँ सहेजना पर्याप्त है। इसके लिए, ज़रा ध्यान दीजिए, 6 बिट पर्याप्त हैं, क्योंकि 26 = 64।

हाँ, हमें ऐसी “सरणी” पर्याप्त है, जिसके एक खाने का आकार 6 बिट है। आगे मैं यह भी बता सकता हूँ कि k=10 का मान दसियों करोड़ तक की गणनसंख्या का काफ़ी अच्छा अनुमान लगाने के लिए पर्याप्त है। इस तरह सेट किया गया एल्गोरिद्म 210 = 1024 आकार की सरणी बनाएगा, जिसका प्रत्येक खाना 6 बिट लेता है। कुल मिलाकर यह सरणी 6144 बिट लेगी, यानी 768 बाइट। एक किलोबाइट भी नहीं।

और बस इतना ही।

हमें और कुछ सहेजने की ज़रूरत नहीं है, परिकलित हैश मान हम तुरंत फेंक सकते हैं, हमें केवल सदिश के अंत में शून्यों की संख्या जाननी है।

ध्यान दीजिए कि यदि आप बड़ा हैश फलन लेते, जो, उदाहरण के लिए, 128 बिट लौटाता, तो मेमोरी की आवश्यकता बहुत नहीं बदलती। तब हमें 0 से 127 तक की संख्याएँ सहेजनी होतीं, जिसके लिए 7 बिट पर्याप्त हैं। इसलिए मेमोरी की आवश्यकता मुख्यतः प्राचल k, यानी समूहों की संख्या, से तय होती है।

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

स्रोत:

विषय-सूची: Linear counting: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, Min Value: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, LogLog: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, HyperLogLog: भिन्न मानों की संख्या का बहुत सटीक अनुमान कैसे लगाएँ