Linear counting: ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে আনুমানিক নির্ণয় করা যায়
কোনো ডেটাসেটে ডেটা যদি সত্যিই অনেক বেশি হয়, তাহলে তাতে ভিন্ন ভিন্ন মানের সংখ্যা আমরা কীভাবে গুনব? যেমন, আমাদের এমন একটি সেবা থাকতে পারে, যা কোনো বড় ওয়েবসাইটের, এমনকি পুরো .bd/.com/.যেকোনো ডোমেইনের ভিন্ন ভিন্ন ব্যবহারকারীর সংখ্যা মাপে।
সরল পদ্ধতি
ঠিক আছে, এখানে ভাবার কিছু নেই: ডেটাগুলো একে একে দেখে যাই এবং প্রত্যেক মান কোনো উপযুক্ত ডেটা স্ট্রাকচারে একবারই রাখি। পাইথনে এটি মোটামুটি এভাবে লেখা যায় (কোডটি ইচ্ছা করেই অকারণে লম্বা):
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 আইডেন্টিফায়ার, আর এমন অনন্য আইডির সংখ্যা যদি হয় ধরা যাক 1 কোটি? প্রোগ্রামটি তখনো সঠিক মানই নির্ণয় করবে, কিন্তু মেমোরি লাগবে কতটা? হিসাব করে দেখা যাক। সরলতার জন্য ধরে নিই, uuid আমরা সত্যিই 36 অক্ষরের স্ট্রিং হিসেবে রাখি। তাহলে একটি uuid নেয় 36 বাইট, আর 1 কোটি আইডি নেয় 360 MB।
স্বীকার করতেই হবে, এটি খুব কম নয়। অনন্য আইডি 10 কোটি হলে দখল করা মেমোরি পৌঁছাত কয়েক গিগাবাইটে। আর এখনো আমরা শুধু ডেটার জায়গাটুকুই হিসাব করছি। এর সঙ্গে যোগ কর পাইথন বা জাভাস্ক্রিপ্টের বাড়তি ব্যয় (ওভারহেড), তাহলে 1 কোটি আইডিতেই কয়েক গিগাবাইটে পৌঁছে যেতে পার:
এটি কেউ চায় না। তাহলে উপায় কী?
আইডিগুলো আরও দক্ষভাবে রাখার চেষ্টা করা যায়, পাইথনের বদলে সি ভাষা ব্যবহার করা যায়, তাতে মেমোরির চাহিদা অনেক কমবে। তবু তা যথেষ্ট হবে না, এমন প্রোগ্রাম তখনো বিপুল জায়গা নেবে। তাই নিজেকে প্রশ্ন করা দরকার: অনন্য মান যে হুবহু 95,63,618 টি, তা কি আমাদের চুল পরিমাণ নিখুঁতভাবে জানতেই হবে? 95,47,666 সংখ্যাটি নিয়ে কাজ করলে কি কোনো ক্ষতি হতো? যদি তোমার উত্তর হয় “হ্যাঁ, হতো, আমার নিখুঁত মানই চাই”, তাহলে তোমার ইচ্ছা। নইলে চল দেখি, ডেটাসেটে ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে যথাসম্ভব নির্ভুলভাবে, দ্রুত এবং সবচেয়ে কম মেমোরিতে আনুমানিক নির্ণয় করা যায়।
হ্যাশ ফাংশন: আমাদের উদ্ধারকর্তা
আমরা এমন একটি হ্যাশ ফাংশন (hash function) বিবেচনা করব, যা ইনপুটে একটি স্ট্রিং নেয় এবং আউটপুটে একটি n-বিট সংখ্যা দেয়। “স্ট্রিং দেয়” এমন হ্যাশ ফাংশনে অভ্যস্ত হলে সহজভাবে কল্পনা কর যে সেই স্ট্রিংকে আবার সংখ্যায় রূপান্তর করা হয়, এতে কঠিন কিছু নেই। বিটের সংখ্যা বলে দেয় সংখ্যাটি কত বড়। 8-বিট ফাংশন এমন সংখ্যা দেয়, যা আট বিট জায়গা নেয়, আর আট বিটে রাখা যায় 28 টি ভিন্ন মান, সাধারণত 0 থেকে 255 পর্যন্ত পূর্ণ সংখ্যা। এরপর আমরা কাজ করব 24-বিট হ্যাশ ফাংশন নিয়ে। এমন ফাংশন দেয় 224 টি ভিন্ন মান, অর্থাৎ 1,67,77,216 টি।
মানগুলো নিজেরা না রেখে আমরা রাখব এদের 24-বিট হ্যাশ মান। 24-বিটের 1 কোটি হ্যাশ মান রাখতে লাগে 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 পাইথনের নিজস্ব ফাংশন, এটি একটি পূর্ণ সংখ্যা দেয়। ফাংশন nhash হলো n-বিট হ্যাশ ফাংশনের একটি সরল বাস্তবায়ন। এটি কীভাবে কাজ করে তা বোঝা জরুরি নয়, কারণ এটি এমনিতেও ঠিকভাবে কাজ করে না: এর ফল 24 বিট জায়গা নেয় না। তবে এখন তাতে কিছু যায় আসে না, আমি শুধু মূলনীতিটি দেখাতে চাই।
এরপর আছে ফাংশন count_unique_using_nhash, যা ভিন্ন ভিন্ন মান গোনে। এটি সব মান একে একে দেখে, প্রত্যেকটির হ্যাশ মান নির্ণয় করে এবং তা চলক found এ রাখে, যদি মানটি সেখানে আগে থেকে না থাকে।
এই পদ্ধতির সমস্যা হলো, হ্যাশ ফাংশন ভিন্ন ভিন্ন স্ট্রিংয়ের জন্য একই চেকসাম দিতে পারে, অর্থাৎ সংঘর্ষ (collision) ঘটতে পারে। এমন সংঘর্ষ যত বেশি ঘটে, ফল তত কম নির্ভুল হয়। ফাংশন count_unique_using_nhash প্রায় সবসময় ভিন্ন ভিন্ন মানের প্রকৃত সংখ্যার চেয়ে কম সংখ্যা দেয়।
আর কোন হ্যাশ ফাংশন বেছে নেব? তাতে খুব একটা কিছু আসে যায় না, তবে সাধারণত MurmurHash এর কোনো একটি রূপের পরামর্শ দেওয়া হয়।
বিটম্যাপ
সি প্রোগ্রামিংয়ের প্রাথমিক কোর্সে মনোযোগ দিয়েছিলে? তাহলে বিটম্যাপ (bitmap) তোমার চেনা। এটিকে কীভাবে কাজে লাগানো যায়?
ভাবনাটি একটি অ্যারে দিয়ে দেখাই। আসলে নির্ণয় করা চেকসামগুলো রেখে দেওয়ার দরকার নেই। আমরা 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)
তবে এখানে অ্যারে ব্যবহার করলে মেমোরি অনেক বেশি লাগে, কারণ প্রত্যেক ঘরে আমাদের রাখতে হয় শুধু একটি এক বা একটি শূন্য। এর বদলে আমরা বিট অ্যারে ব্যবহার করতে পারি। বিষয়টি বোঝার জন্য: একটি পূর্ণ সংখ্যা (integer) রাখা যায় যেমন 32 বিটে। সংখ্যা 354 কে দ্বিমিক পদ্ধতিতে রূপান্তর করলে পাই 101100010। তাই কম্পিউটারে 32-বিট integer হিসেবে সংখ্যা 354 রাখা থাকত (খুঁটিনাটি বাদ দিচ্ছি) এভাবে:
00000000 00000000 00000001 01100010
বেশ সুবিধাজনক একটি রূপ, যা আমরা কাজে লাগাতে পারি, তাই না? আমাদের ফাংশনে তো আমরা শুধু এক আর শূন্য রাখতে চাই, আর এইমাত্র দেখলাম যে সাধারণ একটি সংখ্যা আসলে শূন্য ও একের স্তূপ ছাড়া আর কিছু নয় (কম্পিউটারের সবকিছুর মতোই…)। সহজ কথায়, বিটওয়াইজ অপারেটর দিয়ে একটি এক এমনভাবে রাখা যায়, যেন তা সত্যিই এক বিট জায়গা নেয়।
অ্যারেওয়ালা আমাদের ফাংশনে ফিরে যাই। একে বিট অ্যারেতে লিখলে 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, কারণ অ্যারে শুরু হয় শুধু শূন্য দিয়ে। আধাআধি হলে অনুপাত হতো অর্ধেক, ইত্যাদি। এই মানকে লিখি
Z, আর নির্ণয় করিZ = শূন্যের সংখ্যা / mহিসেবে।
এখন কথা হলো, Z এর মান যত বেশি, অনন্য মানের সংখ্যার আমাদের আনুমানিক মান নির্ভুল হওয়ার ব্যাপারে তত বেশি নিশ্চিত হতে পারি। যেমন, একটি ফাঁকা ডেটাসেট দেখলে বিট অ্যারেতে শুধু শূন্যই থাকবে এবং Z এর মান হবে এক। তখন আমরা সম্পূর্ণ নিশ্চিত যে আমাদের ডেটাসেটে অনন্য উপাদান ততগুলোই, বিট অ্যারেতে যতগুলো এক আছে, অর্থাৎ একটিও নয়।
Z এর মান 0.99 হলে বোঝায় বিট অ্যারের একশো ভাগের এক ভাগ এক দিয়ে ভরা। অ্যারের 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
প্রথম অনুমানটিই ঠিকঠাক ছিল, সংশোধনে পৌঁছানো গেল পুরো দশ হাজারে। দেখানোর জন্য 10 লাখ অনন্য আইডি দিয়েও চেষ্টা করা যায়, অর্থাৎ 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: ভিন্ন ভিন্ন মানের সংখ্যা খুব নির্ভুলভাবে কীভাবে আনুমানিক নির্ণয় করা যায়