بے نقصان ڈیٹا کمپریشن کیسے کام کرتا ہے | کوانٹا میگزین

انٹرنیٹ پر روزانہ 9 بلین گیگا بائٹس سے زیادہ معلومات کے سفر کے ساتھ، محققین ڈیٹا کو چھوٹے پیکجوں میں کمپریس کرنے کے لیے مسلسل نئے طریقے تلاش کر رہے ہیں۔ جدید ترین تکنیک نقصان دہ طریقوں پر توجہ مرکوز کرتی ہے، جو ٹرانسمیشن سے جان بوجھ کر "کھونے" والی معلومات کو کمپریشن حاصل کرتی ہے۔ مثال کے طور پر، گوگل نے حال ہی میں ایک نقصان دہ حکمت عملی کی نقاب کشائی کی ہے جہاں بھیجنے والا کمپیوٹر تصویر سے تفصیلات گرا دیتا ہے اور وصول کرنے والا کمپیوٹر گمشدہ حصوں کا اندازہ لگانے کے لیے مصنوعی ذہانت کا استعمال کرتا ہے۔ یہاں تک کہ Netflix ایک نقصان دہ نقطہ نظر کا استعمال کرتا ہے، جب بھی کمپنی کو پتہ چلتا ہے کہ صارف کم ریزولوشن والے ڈیوائس پر دیکھ رہا ہے تو ویڈیو کے معیار کو گھٹا دیتا ہے۔

بہت کم تحقیق، اس کے برعکس، فی الحال بے مقصد حکمت عملیوں پر چل رہی ہے، جہاں ترسیل کو چھوٹا بنایا جاتا ہے، لیکن کسی مادے کی قربانی نہیں دی جاتی ہے۔ وجہ؟ نقصان کے بغیر نقطہ نظر پہلے ہی قابل ذکر حد تک موثر ہیں۔ وہ JPEG امیج اسٹینڈرڈ سے لے کر ہر جگہ موجود سافٹ ویئر یوٹیلیٹی PKZip تک ہر چیز کو طاقت دیتے ہیں۔ اور یہ سب ایک گریجویٹ طالب علم کی وجہ سے ہے جو صرف ایک مشکل فائنل امتحان سے نکلنے کا راستہ تلاش کر رہا تھا۔

ستر سال پہلے، رابرٹ فانو نامی میساچوسٹس انسٹی ٹیوٹ آف ٹیکنالوجی کے پروفیسر نے اپنی انفارمیشن تھیوری کلاس میں طلباء کو ایک انتخاب پیش کیا: روایتی فائنل امتحان دیں، یا ڈیٹا کمپریشن کے لیے ایک سرکردہ الگورتھم کو بہتر بنائیں۔ ہو سکتا ہے کہ Fano نے اپنے طالب علموں کو مطلع کیا ہو یا نہ کیا ہو کہ وہ اس موجودہ الگورتھم کا مصنف تھا، یا وہ برسوں سے بہتری کی تلاش میں تھا۔ ہم کیا جانتے ہیں کہ فانو نے اپنے طلباء کو مندرجہ ذیل چیلنج پیش کیا۔

حروف، اعداد اور اوقاف سے بنے پیغام پر غور کریں۔ اس طرح کے پیغام کو انکوڈ کرنے کا ایک سیدھا طریقہ یہ ہوگا کہ ہر کردار کو ایک منفرد بائنری نمبر تفویض کیا جائے۔ مثال کے طور پر، ایک کمپیوٹر حرف A کو 01000001 اور ایک فجائیہ نقطہ 00100001 کے طور پر ظاہر کر سکتا ہے۔ اس کے نتیجے میں ایسے کوڈ ہوتے ہیں جن کا تجزیہ کرنا آسان ہوتا ہے — ہر آٹھ ہندسوں، یا بٹس، ایک منفرد کریکٹر کے مطابق ہوتے ہیں — لیکن انتہائی ناکارہ، کیونکہ ایک ہی نمبر بائنری ہندسوں کا استعمال عام اور غیر معمولی دونوں اندراجات کے لیے کیا جاتا ہے۔ ایک بہتر نقطہ نظر مورس کوڈ جیسا ہو گا، جہاں متواتر حرف E کو صرف ایک نقطے سے ظاہر کیا جاتا ہے، جب کہ کم عام Q کو طویل اور زیادہ محنتی ڈیش-ڈیش-ڈاٹ-ڈیش کی ضرورت ہوتی ہے۔

پھر بھی مورس کوڈ بھی ناکارہ ہے۔ یقینی طور پر، کچھ کوڈ مختصر ہیں اور کچھ لمبے ہیں۔ لیکن چونکہ کوڈ کی لمبائی مختلف ہوتی ہے، اس لیے مورس کوڈ میں پیغامات اس وقت تک نہیں سمجھے جا سکتے جب تک کہ ان میں ہر کریکٹر ٹرانسمیشن کے درمیان مختصر خاموشی شامل نہ ہو۔ درحقیقت، ان مہنگے توقف کے بغیر، وصول کنندگان کے پاس مورس پیغام ڈیش ڈاٹ ڈیش ڈاٹ ڈاٹ ڈاٹ ڈاٹ ڈاٹ ڈیش ڈاٹ ("ٹرائٹ") کو ڈیش ڈاٹ ڈیش ڈاٹ ڈاٹ ڈاٹ ڈاٹ ڈاٹ ڈیش ڈاٹ ("سچ" سے ممتاز کرنے کا کوئی طریقہ نہیں ہوگا۔ )۔

فانو نے مسئلے کا یہ حصہ حل کر دیا تھا۔ اس نے محسوس کیا کہ وہ مہنگی جگہوں کی ضرورت کے بغیر مختلف طوالت کے کوڈز استعمال کر سکتا ہے، جب تک کہ اس نے ہندسوں کے ایک جیسے پیٹرن کو مکمل کوڈ اور کسی دوسرے کوڈ کے آغاز کے طور پر استعمال نہیں کیا۔ مثال کے طور پر، اگر کسی خاص پیغام میں حرف S اتنا عام تھا کہ Fano نے اسے انتہائی مختصر کوڈ 01 تفویض کیا، تو اس پیغام میں کوئی دوسرا خط 01 سے شروع ہونے والی کسی بھی چیز کے ساتھ انکوڈ نہیں ہوگا۔ 010، 011 یا 0101 جیسے کوڈز سب ممنوع ہوں گے۔ نتیجے کے طور پر، کوڈ شدہ پیغام کو بغیر کسی ابہام کے بائیں سے دائیں پڑھا جا سکتا ہے۔ مثال کے طور پر، خط S تفویض کردہ 01، خط A تفویض کردہ 000، خط M تفویض کردہ 001، اور خط L تفویض کردہ 1، اچانک پیغام 0100100011 کا فوری طور پر لفظ "چھوٹا" میں ترجمہ کیا جا سکتا ہے حالانکہ L کی نمائندگی ایک سے ہوتی ہے۔ ہندسہ، S کو دو ہندسوں سے، اور دوسرے حروف کو تین سے تین۔

اصل میں کوڈز کا تعین کرنے کے لیے، فانو نے بائنری درخت بنائے، ہر ضروری خط کو بصری شاخ کے آخر میں رکھ کر۔ ہر حرف کے کوڈ کی وضاحت اوپر سے نیچے تک کے راستے سے ہوتی تھی۔ اگر راستہ بائیں طرف مڑ گیا تو، Fano نے 0 کا اضافہ کیا؛ دائیں شاخوں کو 1 ملا۔ درخت کی ساخت نے Fano کے لیے ان ناپسندیدہ اوورلیپس سے بچنا آسان بنا دیا: ایک بار جب Fano نے درخت میں ایک حرف رکھا تو وہ شاخ ختم ہو جائے گی، یعنی مستقبل کا کوئی کوڈ اسی طرح شروع نہیں ہو سکتا۔

یہ فیصلہ کرنے کے لیے کہ کون سے حروف کہاں جائیں گے، Fano زیادہ سے زیادہ کارکردگی کے لیے ہر ممکنہ پیٹرن کی مکمل جانچ کر سکتا تھا، لیکن یہ ناقابل عمل ہوتا۔ اس کے بجائے اس نے ایک تخمینہ تیار کیا: ہر پیغام کے لیے، وہ متعلقہ حروف کو فریکوئنسی کے لحاظ سے ترتیب دے گا اور پھر شاخوں کو حروف تفویض کرے گا تاکہ کسی بھی شاخ کے جوڑے میں بائیں طرف کے حروف پیغام میں تقریباً اتنی ہی بار استعمال کیے جائیں جیسے دائیں طرف حروف. اس طرح، اکثر استعمال ہونے والے حروف چھوٹی، کم گھنی شاخوں پر ختم ہو جائیں گے۔ اعلی تعدد والے حروف کی ایک چھوٹی تعداد ہمیشہ کم تعدد والے خطوط کی کچھ بڑی تعداد کو متوازن کرتی ہے۔

نتیجہ نمایاں طور پر موثر کمپریشن تھا۔ لیکن یہ صرف ایک تخمینہ تھا۔ ایک بہتر کمپریشن کی حکمت عملی موجود تھی. چنانچہ فانو نے اپنے طالب علموں کو چیلنج کیا کہ وہ اسے تلاش کریں۔

فانو نے اپنے درختوں کو اوپر سے نیچے بنایا تھا، جوڑی کی شاخوں کے درمیان زیادہ سے زیادہ ہم آہنگی کو برقرار رکھا تھا۔ اس کے طالب علم ڈیوڈ ہف مین نے اس عمل کو اپنے سر پر پلٹایا، اسی قسم کے درخت بنائے لیکن نیچے سے۔ ہف مین کی بصیرت یہ تھی کہ، اور کچھ بھی ہو، ایک موثر کوڈ میں دو کم سے کم عام حروف کے دو طویل ترین کوڈ ہونے چاہئیں۔ چنانچہ ہفمین نے دو کم سے کم مشترکہ کرداروں کی نشاندہی کی، انہیں ایک شاخ ساز جوڑے کے طور پر ایک ساتھ گروپ کیا، اور پھر اس عمل کو دہرایا، اس بار باقی کرداروں اور اس جوڑے میں سے دو سب سے کم مشترکہ اندراجات کی تلاش میں جو اس نے ابھی بنایا تھا۔

ایک ایسے پیغام پر غور کریں جہاں Fano اپروچ ناکام ہو جاتا ہے۔ "اسکول روم" میں O چار بار ظاہر ہوتا ہے، اور S/C/H/L/R/M ہر ایک ایک بار ظاہر ہوتا ہے۔ فانو کے توازن کا نقطہ نظر O اور ایک دوسرے خط کو بائیں شاخ کو تفویض کرنے سے شروع ہوتا ہے، ان حروف کے پانچ کل استعمال کے ساتھ باقی حروف کی پانچ ظاہری شکلوں کو متوازن کرتے ہیں۔ نتیجے میں آنے والے پیغام کے لیے 27 بٹس کی ضرورت ہے۔

ہف مین، اس کے برعکس، دو غیر معمولی حروف سے شروع ہوتا ہے - کہتے ہیں، R اور M - اور جوڑے کو ایک حرف کی طرح برتاؤ کرتے ہوئے، ان کو ایک ساتھ گروپ کرتا ہے۔

اس کا اپ ڈیٹ شدہ فریکوئنسی چارٹ پھر اسے چار انتخاب پیش کرتا ہے: O جو چار بار ظاہر ہوتا ہے، نیا مشترکہ RM نوڈ جو فعال طور پر دو بار استعمال ہوتا ہے، اور سنگل حروف S, C, H اور L۔ Huffman پھر سے دو کم سے کم عام اختیارات کو چنتا ہے، مماثل۔ (کہیں) ایچ کے ساتھ ایل۔

چارٹ دوبارہ اپ ڈیٹ ہوتا ہے: O کا اب بھی وزن 4 ہے، RM اور HL اب ہر ایک کا وزن 2 ہے، اور حروف S اور C اکیلے کھڑے ہیں۔ ہف مین وہاں سے آگے بڑھتا ہے، ہر مرحلے میں دو کم سے کم متواتر اختیارات کو گروپ کرتا ہے اور پھر درخت اور فریکوئنسی چارٹ دونوں کو اپ ڈیٹ کرتا ہے۔

بالآخر، "اسکول روم" 11101111110000110110000101 بن جاتا ہے، Fano ٹاپ-ڈاؤن اپروچ سے تھوڑا سا ہٹ کر۔

ہوسکتا ہے کہ تھوڑا سا زیادہ نہ لگے، لیکن جب اربوں گیگا بائٹس کی پیمائش کی جائے تو چھوٹی بچتیں بھی بہت زیادہ بڑھ جاتی ہیں۔

درحقیقت، ہفمین کا نقطہ نظر اتنا طاقتور نکلا ہے کہ، آج، تقریباً ہر بے نقصان کمپریشن حکمت عملی ہفمین کی بصیرت کو مکمل یا جزوی طور پر استعمال کرتی ہے۔ ورڈ دستاویز کو کمپریس کرنے کے لیے PKZip کی ضرورت ہے؟ پہلے مرحلے میں تکرار کی نشاندہی کرنے اور اس طرح پیغام کے سائز کو کمپریس کرنے کے لیے ایک اور ہوشیار حکمت عملی شامل ہے، لیکن دوسرا مرحلہ یہ ہے کہ نتیجے میں آنے والے کمپریسڈ پیغام کو لے کر اسے Huffman کے عمل کے ذریعے چلانا ہے۔ تصویر کو JPEG کے بطور اسٹور کریں؟ آپ کا کمپیوٹر پہلے تصویر کو متن پر مبنی نمائندگی میں ترجمہ کرتا ہے اور پھر، دوبارہ، اس متن کو کمپریس کرنے کے لیے Huffman انکوڈنگ کا استعمال کرتا ہے۔

کسی ایسے پروجیکٹ کے لیے برا نہیں جو اصل میں گریجویٹ طالب علم کی حتمی امتحان کو چھوڑنے کی خواہش سے محرک ہو۔