LogLog: ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে আনুমানিক নির্ণয় করা যায়
Linear Counting ও Min Value নিয়ে আগের পর্বগুলোর পর অবশেষে আমরা পৌঁছালাম ডেটাসেটে ভিন্ন ভিন্ন মানের সংখ্যা আনুমানিক নির্ণয়ের প্রায় সবচেয়ে সেরা সম্ভাবনাভিত্তিক অ্যালগরিদমে: LogLog। এর চেয়ে ভালো শুধু এর ছোট ভাই HyperLogLog, যা LogLog থেকেই এসেছে, তবে সেটি নিয়ে কথা হবে পরের বার।
সমস্যাটি আবার বলে নিই। ইনপুটে আছে একটি ডেটাসেট বা মাল্টিসেট, যেমন আইডির একটি অ্যারে বা জেনারেটর। এই অ্যারেতে কিছু মান একাধিকবার আছে, আর আমরা অ্যারেতে ভিন্ন ভিন্ন মানের সংখ্যা গুনতে চাই। এই সংখ্যাকে আমরা বলব কার্ডিনালিটি (cardinality)। আমরা ধরে নিচ্ছি, এই কার্ডিনালিটি সত্যিই বড় হবে, নইলে প্রচলিত অ্যালগরিদম ব্যবহার করা যায়।
LogLog অ্যালগরিদমের মূল ভাবনা
কল্পনা কর, আমাদের কাছে দ্বিমিক ভেক্টরের একটি সংগ্রহ আছে। ভয়ের কিছু নেই, যেমন 0001011001001100 হলো 16 দৈর্ঘ্যের একটি দ্বিমিক ভেক্টর। ধরা যাক, আমাদের কাছে 32 দৈর্ঘ্যের দ্বিমিক ভেক্টর আছে মোট 10 লাখটি, সবগুলো সম্পূর্ণ এলোমেলোভাবে তৈরি। কতগুলো ভেক্টর শূন্য দিয়ে শেষ হবে?
অবশ্যই তা নিখুঁতভাবে জানা সম্ভব নয়, কিন্তু ভেক্টরগুলো সত্যিই এলোমেলোভাবে তৈরি হলে প্রায় অর্ধেক শূন্য দিয়ে শেষ হওয়ার কথা, অর্থাৎ 5 লাখ। কতগুলো ভেক্টর 00 দিয়ে শেষ হবে? এক-চতুর্থাংশ। 000 দিয়ে? এক-অষ্টমাংশ। এভাবে চলতে থাকে। মোটামুটি এভাবে দেখানো যায়:
ভেক্টরের নমুনা সব ভেক্টরের মধ্যে অংশ
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12.5%
...xxx0000 6.25%
... ...
d দৈর্ঘ্যের একটি সাফিক্স (suffix হলো সেই স্ট্রিং, যা দিয়ে অন্য একটি স্ট্রিং শেষ হয়, প্রিফিক্সের বিপরীত) নিয়ে জিজ্ঞেস করলে আমরা আশা করি, এই সাফিক্স দিয়ে শেষ হওয়া v টি ভেক্টর পাব। মান v নির্ণয় করি এভাবে:
যেখানে N হলো সংগ্রহের সব ভেক্টরের সংখ্যা। 3 দৈর্ঘ্যের সাফিক্স (যেমন …010) থাকার কথা 1/2^3 N = 1/8 N টি ভেক্টরে, অর্থাৎ সব ভেক্টরের 12.5% এ।
এবার মাথা ঘুরিয়ে দেওয়ার মতো একটি ছোট খেলা। ধরি 1024 টি অনন্য ভেক্টরের একটি মাল্টিসেট আছে। কতগুলো ভেক্টর সাফিক্স 0000000000 (দশটি শূন্য) দিয়ে শেষ হওয়ার কথা? সূত্রে বসালে পাই
আরে, একটি! এলোমেলোভাবে তৈরি এক হাজার দ্বিমিক ভেক্টরে দশটি শূন্য দিয়ে শেষ হওয়া ভেক্টর থাকার কথা ঠিক একটি। এই তথ্য দিয়ে অনন্য উপাদানের সংখ্যা আনুমানিক নির্ণয় করব কীভাবে? আমরা উল্টো দিক থেকে এগোতে পারি। ধরা যাক, ইনপুটের সব দ্বিমিক ভেক্টর দেখে জানলাম, সংগ্রহে দশটি শূন্য দিয়ে শেষ হওয়া ভেক্টর মাত্র একটি। তাহলে তো অনুমান করতে পারি যে সংগ্রহে 1024 টি ভেক্টর ছিল!
সাধারণীকরণ ও অ্যালগরিদম গঠন
লক্ষ্য হওয়া উচিত এমন একটি সাফিক্স খুঁজে বের করা, যা শুধু একটি ভেক্টরে আছে এবং যা যথাসম্ভব ছোট। কিন্তু তা খুবই কঠিন, কারণ এমন ভেক্টর সত্যিই খুঁজে পেতে হলে সব সাফিক্স রেখে দিতে হতো, যা আমরা চাই না, কারণ তাতে অনেক বেশি মেমোরি লাগত। এর বদলে আমরা সন্তুষ্ট থাকব ভেক্টরের শেষে শূন্যের দীর্ঘতম অনুক্রম খুঁজে।
তাই সব ভেক্টর একে একে দেখি, প্রত্যেক ভেক্টরের শেষে কয়টি শূন্য আছে তা গুনি, আর একটি চলকে এই মানগুলোর বৃহত্তমটি রাখি। সব ভেক্টর দেখা শেষ হলে জানব, শুধু শূন্য দিয়ে গঠিত দীর্ঘতম সাফিক্সের দৈর্ঘ্য কত। এই দৈর্ঘ্যকে বর্ণ d দিয়ে লিখি। এবার আগের সূত্রটিকে এমনভাবে বদলাই, যেন চলক N আলাদা হয়ে যায়, অর্থাৎ এটি হয় অ্যালগরিদমের আউটপুট, ইনপুট নয়। সেই সঙ্গে v এর জায়গায় বসাতে পারি এক, কারণ আমরা আশা করি এমন ভেক্টর পাব ঠিক একটি, অর্থাৎ আশা করি v=1 হবে।
তাই দীর্ঘতম শূন্য সাফিক্সের দৈর্ঘ্য 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 দেয় সংখ্যার শেষে থাকা শূন্যের সংখ্যা। এটি কীভাবে কাজ করে? কোড দেখে না বুঝে থাকলে বরং জিজ্ঞেস না করাই ভালো। আর ফাংশনটি কতটা সফল? 1 লাখ অনন্য উপাদানের একটি সেটের জন্য ফাংশনটির অনুমান ছিল 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। মানটি সূত্রে বসালে পাই
এতে পাই প্রত্যেক গুচ্ছে অনন্য উপাদানের গড় সংখ্যা। অবশ্যই এটি একেবারেই মেলে না, কিন্তু তা নিয়ে মন খারাপ করার কিছু নেই, ছোট সেটের জন্য 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 ঠিক করে, কয়টি বিট গুচ্ছের সূচক হিসেবে নেওয়া হবে। এই প্যারামিটারই অ্যালগরিদমের নির্ভুলতা ঠিক করে: k যত বেশি, নির্ভুলতা তত বেশি। চলক bucket_index এ রাখা হয় গুচ্ছের নম্বর। সমান চিহ্নের ডানপাশের জাদুটি কীভাবে কাজ করে?
চলক num_buckets এ আছে গুচ্ছের সংখ্যা, যা সবসময় দুই এর একটি ঘাত। যেমন k = 3 হলে num_buckets=8। দ্বিমিক পদ্ধতিতে সংখ্যা 8 দেখতে 1000। এক বিয়োগ করলে পাই সংখ্যা 7, যা দেখতে 0111। num_buckets থেকে এক বিয়োগ করলে সবসময় এমন সংখ্যা পাই, যার শেষে k টি এক এবং তার আগে শুধু শূন্য। এরপর বিটওয়াইজ AND করি (এটিই অপারেটর &)। ভেক্টর 1110110010100101 এর জন্য এই প্রক্রিয়াটি দেখতে এমন হতো:
1110110010100101
& 0000000000000111
------------------
0000000000000101
এই পুরো জাদুর উদ্দেশ্য হলো এমন একটি সংখ্যা পাওয়া, যার শুরুতে শুধু শূন্য, আর শেষ k টি বিট প্রদত্ত হ্যাশ মান h এর মতোই।
এরপর নির্ণয় করি bucket_hash, অর্থাৎ মূল হ্যাশ মান থেকে শেষ 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
আমি 10 লাখ কার্ডিনালিটির একটি মাল্টিসেট দিয়েও চেষ্টা করেছি, ফল:
ফল ত্রুটি
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। এ নিয়েও কথা হবে পরের বার।
তথ্যসূত্র:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (LogLog এর কোড মোটামুটি এখান থেকেই নেওয়া)
সূচিপত্র: Linear counting: ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে আনুমানিক নির্ণয় করা যায়, Min Value: ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে আনুমানিক নির্ণয় করা যায়, LogLog: ভিন্ন ভিন্ন মানের সংখ্যা কীভাবে আনুমানিক নির্ণয় করা যায়, HyperLogLog: ভিন্ন ভিন্ন মানের সংখ্যা খুব নির্ভুলভাবে কীভাবে আনুমানিক নির্ণয় করা যায়