Linear counting: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ
यदि किसी आँकड़ा-समूह में आँकड़े सचमुच बहुत अधिक हों, तो उसमें भिन्न (अद्वितीय) मानों की संख्या हम कैसे गिनें? उदाहरण के लिए, हमारे पास कोई ऐसी सेवा हो सकती है, जो किसी बड़ी वेबसाइट पर, या पूरे .in/.com/.whatever डोमेन पर, अद्वितीय उपयोगकर्ताओं की संख्या मापती है।
सहज विधि
ठीक है, इसमें सोचने को क्या है: हम आँकड़ों से गुज़रते हैं और प्रत्येक मान को किसी उपयुक्त डेटा संरचना में केवल एक बार सहेज लेते हैं। Python में हम इसे लगभग ऐसे लिख सकते हैं (कोड जानबूझकर ज़रूरत से ज़्यादा लंबा है):
nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]
def count_unique(values):
found = set()
for item in values:
if item not in found:
found.add(item)
return len(found)
print count_unique(nonunique_values) # 5
यह काम करता है। अच्छा, पर यदि आँकड़े 36 अक्षरों वाले अद्वितीय v4 पहचानकर्ता हों और ऐसे अद्वितीय पहचानकर्ता, मान लीजिए, एक करोड़ हों, तब? प्रोग्राम फिर भी सही मान परिकलित करेगा, परंतु वह कितनी मेमोरी लेगा? आइए, इसकी गणना करें। सरलता के लिए हम मानेंगे कि uuid को हम सचमुच 36 अक्षरों की स्ट्रिंग के रूप में सहेजते हैं। तब एक uuid 36 बाइट लेता है और एक करोड़ पहचानकर्ता 360 MB लेते हैं।
मानना होगा कि यह बहुत कम नहीं है। यदि अद्वितीय पहचानकर्ता दस करोड़ होते, तो प्रयुक्त मेमोरी गीगाबाइट के स्तर तक पहुँच जाती। और यह तो हम केवल आँकड़ों की जगह गिन रहे हैं। इसमें Python/JavaScript का कुछ ओवरहेड (अतिरिक्त मेमोरी) जोड़ दीजिए, तो एक करोड़ पहचानकर्ताओं के साथ भी आप गीगाबाइट के स्तर तक पहुँच सकते हैं:
यह आप नहीं चाहेंगे। इससे कैसे निकलें?
हम पहचानकर्ताओं को किसी अधिक कुशल ढंग से सहेजने का प्रयास कर सकते हैं, Python के बजाय C का प्रयोग कर सकते हैं, जिससे मेमोरी की आवश्यकता काफ़ी घट जाएगी, परंतु फिर भी बात नहीं बनेगी और ऐसा प्रोग्राम फिर भी बहुत अधिक जगह लेगा। अब स्वयं से यह प्रश्न पूछना बाकी है: क्या हमें सचमुच बिल्कुल सटीक जानना है कि अद्वितीय मान 95,63,618 ही हैं? यदि हम 95,47,666 की संख्या से काम चलाएँ, तो क्या कुछ बिगड़ जाएगा? यदि आपका उत्तर है कि बिगड़ जाएगा और आपको सटीक संख्या चाहिए, तो आपकी मर्ज़ी। अन्यथा आइए, ऐसी विधियाँ देखें, जिनसे किसी आँकड़ा-समूह में भिन्न मानों की संख्या का यथासंभव सटीक, तेज़ और न्यूनतम मेमोरी के साथ अनुमान लगाया जा सके।
हैश फलन — हमारा सहारा
हम एक ऐसा हैश फलन लेंगे, जो इनपुट में स्ट्रिंग लेता है और आउटपुट में कोई n-बिट संख्या लौटाता है। यदि आप ऐसे हैश फलनों के आदी हैं, जो “स्ट्रिंग लौटाते हैं”, तो बस मान लीजिए कि वह स्ट्रिंग फिर से संख्या में बदल दी जाती है, इसमें कोई कठिनाई नहीं है। बिटों की संख्या बताती है कि संख्या कितनी बड़ी है। 8-बिट फलन ऐसी संख्या लौटाता है, जो आठ बिट लेती है, और आठ बिट में 28 भिन्न मान सहेजे जा सकते हैं, सामान्यतः 0 से 255 तक के पूर्णांक। आगे हम 24-बिट हैश फलन के साथ काम करेंगे। ऐसा फलन 224 भिन्न मान लौटाता है, यानी 1,67,77,216।
मानों को स्वयं सहेजने के बजाय हम उनके 24-बिट हैश मान सहेजेंगे। एक करोड़ 24-बिट हैश मान सहेजने के लिए हमें 30 MB चाहिए। यह पिछले 360 MB से दस गुना बेहतर है। कोड ऐसा दिख सकता है:
def nhash(item, n):
return hash(item) % (2 ** n)
nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]
def count_unique_using_nhash(values):
found = set()
for item in values:
checksum = nhash(item, 24)
if checksum not in found:
found.add(checksum)
return len(found)
print count_unique_using_nhash(nonunique_values) # 5
फलन hash Python का अंतर्निहित फलन है और एक पूर्णांक लौटाता है। फलन nhash n-बिट हैश फलन का एक सहज कार्यान्वयन दिखाता है; यह समझना ज़रूरी नहीं कि यह कैसे काम करता है, क्योंकि वैसे भी यह ठीक से काम नहीं करता — इस फलन का परिणाम 24 बिट नहीं लेता, परंतु अभी इससे फ़र्क नहीं पड़ता, मुझे सिद्धांत दिखाना है।
इसके बाद फलन count_unique_using_nhash आता है, जो अद्वितीय मान गिनता है। यह सभी मानों से गुज़रता है, उनका हैश मान परिकलित करता है और यदि वह मान चर found में पहले से नहीं है, तो उसे वहाँ सहेज देता है।
इस विधि की समस्या यह है कि हैश फलन भिन्न स्ट्रिंगों के लिए एक ही चेकसम (checksum) लौटा सकता है — हैश टकराव (collision) हो सकता है। जितने अधिक टकराव होंगे, परिणाम उतना ही कम सटीक होगा। फलन count_unique_using_nhash लगभग हमेशा अद्वितीय मानों की वास्तविक संख्या से कम संख्या लौटाता है।
और कौन-सा हैश फलन चुनें? इससे बहुत फ़र्क नहीं पड़ता, परंतु सामान्यतः MurmurHash का कोई रूप सुझाया जाता है।
बिटमैप
क्या आपने C प्रोग्रामिंग की बुनियादी कक्षा में ध्यान दिया था? यदि हाँ, तो आप बिटमैप जानते हैं। उनका उपयोग कैसे किया जा सकता है?
विचार को हम एक सरणी (array) पर समझाएँगे। हमें परिकलित चेकसम सहेजने की ज़रूरत ही नहीं है: हम 224 लंबाई की एक सरणी बना सकते हैं और उसके सभी अवयवों को शून्य पर आरंभ कर सकते हैं। फिर जैसे ही हमें कोई चेकसम मिलता है — जो एक संख्या है! — हम इस सरणी में सूचकांक checksum पर 1 लिख देते हैं, जिससे यह दर्ज हो जाता है कि यह चेकसम हमें मिल चुका है। तब अद्वितीय अवयवों की संख्या लगभग इस सरणी में इकाइयों (1) की संख्या के बराबर होगी। कोड ऐसा दिख सकता है:
def count_unique_using_array(values):
# 2^24 लंबाई की सूची, जिसके सभी अवयव शून्य पर आरंभ किए गए हैं
array = [0] * (2 ** 24)
for item in values:
array[nhash(item, 24)] = 1
return sum(array)
print count_unique_using_array(nonunique_values)
फिर भी इस स्थिति में सरणी का प्रयोग मेमोरी के लिहाज़ से बहुत महँगा है, क्योंकि प्रत्येक खाने में हमें केवल 1 या 0 सहेजना है। इसके बजाय हम बिट सरणी (bit array) का प्रयोग कर सकते हैं। समझने के लिए: एक पूर्णांक (integer) को, उदाहरण के लिए, 32 बिट में सहेजा जा सकता है। संख्या 354 को द्विआधारी पद्धति में बदलें, तो हमें 101100010 मिलता है। इसलिए संख्या 354 कंप्यूटर में 32-बिट integer के रूप में इस प्रकार सहेजी जाती (बारीकियों को छोड़ दें, ठीक है?):
00000000 00000000 00000001 01100010
यह काफ़ी अच्छा प्रारूप है, जिसका हम उपयोग कर सकते हैं, है न? अपने फलन में हम केवल इकाइयाँ और शून्य सहेजना चाहते हैं, और हमने अभी पाया कि साधारण संख्या वास्तव में शून्यों और इकाइयों के ढेर के अलावा कुछ नहीं है (जैसे कंप्यूटर में सब कुछ…)। संक्षेप में, बिटवाइज़ संक्रियाओं की सहायता से हम 1 को इस तरह सहेज सकते हैं कि वह सचमुच केवल एक बिट ले।
आइए, सरणी वाले अपने फलन पर लौटें। यदि हम इसे बिट सरणियों में दोबारा लिखें, तो 24-बिट हैश फलन के लिए हमें 224 बिट आकार की बिट सरणी पर्याप्त होगी, यानी 2 MiB। यह अच्छा सुधार है!
32-बिट हैश फलन के साथ, जिसके 232, यानी 4,29,49,67,296, भिन्न आउटपुट मान होते हैं, हमें आधे गीगाबाइट की बिट सरणी चाहिए होती। यह बुरा नहीं है, क्योंकि इससे हम सैकड़ों करोड़ तक के अद्वितीय मान गिन सकते हैं।
Linear Counting
मैं बता चुका हूँ कि हैश फलन का प्रयोग करने पर हमें अद्वितीय मानों की संख्या का केवल अनुमान मिलता है। यह अनुमान उतना ही कम सटीक होता है, जितना अद्वितीय मानों की संख्या हैश फलन के भिन्न आउटपुट मानों की संख्या के निकट पहुँचती है। स्वाभाविक है कि यदि हमारे आँकड़ा-समूह में 500 करोड़ अद्वितीय मान हों, तो 24-बिट हैश फलन से हम उन्हें गिन ही नहीं पाएँगे।
फिर भी हैश फलनों से परिकलित अनुमान को और सटीक बनाया जा सकता है। इसके लिए एक सरल विचार का प्रयोग होता है — आँकड़ा-समूह में जितने अधिक अद्वितीय मान होंगे, समय के साथ टकराव होने की प्रायिकता उतनी ही अधिक होगी। (टकराव = दो भिन्न इनपुट का हैश फलन से एक ही आउटपुट, एक ही चेकसम।) अब हम थोड़ी गणना करेंगे, इसलिए कुछ चर परिभाषित करते हैं:
- हम
n-बिट हैश फलनhके साथ काम करेंगे। - इसलिए फलन
hके सभी संभव आउटपुट की संख्या2nके बराबर है। इस संख्या को हम अक्षरmसे दर्शाएँगे, अर्थात्m=2n। - जिस बिट सरणी में हम दर्ज करेंगे कि कौन-से चेकसम मिल चुके हैं, उसे हम बड़े अक्षर
Aसे दर्शाएँगे। सरणीAकी लंबाईmहै। - जब हमारा एल्गोरिद्म पूरे आँकड़ा-समूह से गुज़र चुका होगा, तो बिट सरणी के कुछ मान शून्य होंगे और कुछ 1। हमारी रुचि मुख्यतः अनुपात “शून्यों की संख्या भाग सरणी की लंबाई” में होगी, जो बिट सरणी में शून्यों का आपेक्षिक हिस्सा बताता है। शुरुआत में यह अनुपात 1 होता है, क्योंकि सरणी सभी शून्यों पर आरंभ की जाती है। यदि आधा-आधा हो, तो अनुपात एक बटा दो होगा, आदि। इस मान को हम
Zसे दर्शाएँगे औरZ = शून्यों की संख्या / mसे परिकलित करेंगे।
इस समय यह सत्य है कि Z का मान जितना अधिक होगा, हमें उतना अधिक भरोसा होगा कि अद्वितीय मानों की संख्या का हमारा अनुमान सटीक है। उदाहरण के लिए, यदि हम एक रिक्त आँकड़ा-समूह से गुज़रें, तो बिट सरणी में सभी शून्य रहेंगे और Z का मान एक होगा — इसलिए हमें पूरा भरोसा है कि हमारे आँकड़ा-समूह में उतने ही अद्वितीय अवयव हैं, जितने बिट सरणी में 1 हैं — यानी शून्य।
यदि Z का मान 0.99 है, तो इसका अर्थ है कि बिट सरणी का सौवाँ भाग 1 से भरा है। 99% सरणी में शून्य हैं। यह अभी ठीक है; अधिक प्रायिकता इसी की है कि अभिकलन के दौरान बहुत टकराव नहीं हुए और शायद कोई संशोधन नहीं या बहुत छोटा संशोधन ही चाहिए होगा। परंतु यदि Z का मान 0.05 है, तो सरणी का केवल 5% भाग शून्य बचा है और अभिकलन के दौरान शायद हमें बहुत, बहुत टकराव मिले — बड़े संशोधन की ज़रूरत होगी।
पर यह संशोधन परिकलित कैसे करें? इसमें लघुगणक हमारी सहायता करेगा, जो ऐसा फलन है:
हमारी रुचि अंतराल (0, 1] पर लाल भाग में होगी। यदि हम x-अक्ष पर Z का मान रखें, तो Z जितना अधिक होगा, y का मान शून्य के उतना ही निकट होगा। और इसके विपरीत — Z जितना कम होगा, y का मान उतना ही कम होगा। परिणामी अनुमान हम इस संख्या को -m से गुणा करके परिकलित करते हैं। ध्यान दीजिए कि Z के पर्याप्त कम मान के लिए हमें ऐसी संख्या मिलती है, जो -1 से भी कम है, और यदि हम इस मान को -m से गुणा करें, तो हमें m से बड़ा अनुमान मिलता है: हमने अनुमान लगाया कि अद्वितीय मानों की संख्या उन सभी संभव चेकसमों की संख्या से अधिक है, जो हैश फलन h से निकल सकते हैं।
अद्वितीय मानों की संख्या p परिकलित करने का पूरा सूत्र ऐसा होगा:
कार्यान्वयन (बिट सरणियों के बिना, केवल सामान्य सरणियों के साथ) ऐसा दिख सकता है:
from uuid import uuid4
from math import log
number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values
def nhash(item, n):
return hash(item) % (2 ** n)
def count_unique_using_array(values, n):
array = [0] * (2 ** n)
for item in values:
array[nhash(item, n)] = 1
return sum(array)
def linear_counting(values, n):
estimate = count_unique_using_array(values, n)
m = 2 ** n
number_of_zeros = m - estimate
Z = float(number_of_zeros) / m
# यहाँ log आधार e वाला प्राकृतिक लघुगणक है
p = (-m) * log(Z)
p = int(round(p))
print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
(estimate, m, number_of_zeros, Z, p)
return p
print "Cardinality: %s" % linear_counting(nonunique_values, 16)
फलन linear_counting में हम पहले पिछले एल्गोरिद्म से पहला अनुमान परिकलित करते हैं, जो n-बिट हैश फलन का प्रयोग करता है। फिर हम सरणी में शून्यों का अनुपात परिकलित करते हैं और सूत्र के अनुसार संशोधन करते हैं। कोड में लघुगणक प्राकृतिक लघुगणक है। चर nonunique_values में number_of_unique_values अद्वितीय स्ट्रिंगें हैं, इसलिए इस उदाहरण में सूची nonunique_values में दस हज़ार अद्वितीय मान हैं। छठी पंक्ति का अजीब-सा कोड यह सुनिश्चित करता है कि सरणी में एक ही मान कई बार आए: हम सूची के अंत में वही सूची जोड़ देते हैं, जिससे प्रत्येक मान सरणी में दो बार आता है। और फिर गणना करते हैं। आदर्श रूप से फलन को लौटाना चाहिए कि सूची में दस हज़ार अद्वितीय मान हैं। आउटपुट:
Debug info: estimate=9289, m=65536, number_of_zeros=56247,
Z=0.858261108398, p=10017
Cardinality: 10017
सूची nonunique_values हर बार नई बनती है, इसलिए हर कॉल पर परिणाम भिन्न होंगे। हमने 16-बिट हैश फलन का प्रयोग किया। हम देखते हैं कि फलन count_unique_using_array का पहला अनुमान यह था कि सूची में 9289 अद्वितीय मान हैं। संशोधन से हमने इस अनुमान को 10,017 तक सटीक किया, जो काफ़ी अच्छा है: हमारा अनुमान केवल 0.17% अधिक है, जबकि पहले वाला 7.11% कम था — जो काफ़ी ज़्यादा है।
यदि हम “बड़ा” हैश फलन लेते, उदाहरण के लिए 24-बिट, तो हमें अधिक सटीक परिणाम मिलता:
Debug info: estimate=9997, m=16777216, number_of_zeros=16767219,
Z=0.999404132366, p=10000
Cardinality: 10000
यहाँ पहला अनुमान ही ठीक था, संशोधन से हम पूरे दस हज़ार पर पहुँच गए। उदाहरण के लिए, हम दस लाख अद्वितीय पहचानकर्ता भी आज़मा सकते हैं, अर्थात् number_of_unique_values = 1000000। 24-बिट हैश फलन के साथ हमें ये परिणाम मिलते हैं:
Debug info: estimate=971033, m=16777216, number_of_zeros=15806183,
Z=0.94212192297, p=1000267
Cardinality: 1000267
यह ठीक है। और यदि हम इसे बिट सरणी के रूप में लागू करें, तो सरणी केवल ऊपर बताए गए दो मेगाबाइट लेगी (+ जितना प्रोग्रामिंग भाषा स्वयं ले)। मेरे हिसाब से काफ़ी अच्छा। But we can do better! Much better. पर यह अगली बार।
तब तक आप लेख A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF] पढ़ सकते हैं। या आप शृंखला के अगले भाग पर जा सकते हैं: min-value एल्गोरिद्म।
विषय-सूची: Linear counting: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, Min Value: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, LogLog: भिन्न मानों की संख्या का अनुमान कैसे लगाएँ, HyperLogLog: भिन्न मानों की संख्या का बहुत सटीक अनुमान कैसे लगाएँ