MinHash
کمپیوٹر سائنس اور ڈیٹا مائننگ میں، من ہاش (یا منٹ کے لحاظ سے آزاد تعدد لوکیٹی حساس ہیشنگ اسکیم) یہ اندازہ لگانے کی ایک تکنیک ہے کہ دو سیٹ کتنے ملتے جلتے ہیں۔ اس اسکیم کی ایجاد، اور ابتدائی طور پر الٹا وسٹا سرچ انجن میں نقل شدہ ویب صفحات کا پتہ لگانے اور انہیں تلاش کے نتائج سے ختم کرنے کے لیے کی گئی تھی۔ اس کا اطلاق بڑے پیمانے پر کلسٹرنگ کے مسائل میں بھی کیا گیا ہے، جیسے کہ کلسٹرنگ دستاویزات ان کے الفاظ کے سیٹوں کی مماثلت سے۔ جیکارڈ مماثلت اور کم از کم ہیش اقدار جیکارڈ مماثلت گتانک دو سیٹوں کے درمیان مماثلت کا عام طور پر استعمال ہونے والا اشارے ہے۔ ایک سیٹ اور اس کے ذیلی سیٹ ہونے دیں، پھر جیکارڈ انڈیکس کو ان کے چوراہے کے عناصر کی تعداد اور ان کے اتحاد کے عناصر کی تعداد کے تناسب کے طور پر بیان کیا جاتا ہے: یہ قدر 0 ہے جب دونوں سیٹ جداگانہ ہوتے ہیں، 1 جب وہ برابر ہوتے ہیں، اور بصورت دیگر سختی سے 0 اور 1 کے درمیان ہوتا ہے۔ دو سیٹ زیادہ ملتے جلتے ہیں (یعنی۔ نسبتا زیادہ اراکین مشترک ہوں) جب ان کا جیکارڈ انڈیکس 1 کے قریب ہو۔ من ہاش کا مقصد چوراہے اور اتحاد کو واضح طور پر شمار کیے بغیر تیزی سے اندازہ لگانا ہے۔ ایک ہیش فنکشن ہونے دیں جو ممبروں کو الگ الگ انٹیجرز میں نقشہ بناتا ہے، سیٹ کے عناصر کا بے ترتیب ترتیب ہونا چاہیے، اور تعریف کے کسی بھی ذیلی سیٹ کے لیے-یعنی کم سے کم ممبر کے حوالے سے کم سے کم ممبر ہونا چاہیے۔ (ایسے معاملات میں جہاں استعمال شدہ ہیش فنکشن کو فرضی بے ترتیب خصوصیات کا حامل سمجھا جاتا ہے، بے ترتیب ترتیب کا استعمال نہیں کیا جائے گا۔) اب، اور دونوں پر لاگو کرتے ہوئے، اور یہ فرض کرتے ہوئے کہ کوئی ہیش تصادم نہیں ہے، ہم دیکھتے ہیں کہ اقدار برابر ہیں () اگر اور صرف اس صورت میں جب تمام عناصر کے درمیان، کم سے کم ہیش ویلیو والا عنصر چوراہے میں ہو۔ اس کے درست ہونے کا امکان بالکل جیکارڈ انڈیکس ہے، لہذا: یعنی، جو امکان درست ہے وہ مماثلت کے برابر ہے، یہ فرض کرتے ہوئے کہ یکساں تقسیم سے لیا گیا ہے۔ دوسرے لفظوں میں، اگر بے ترتیب متغیر ہے جو ایک ہے جب اور صفر بصورت دیگر، تو اس کا غیر جانبدار تخمینہ ہے۔ جیکارڈ کی مماثلت کے لیے خود مفید تخمینہ لگانے کے لیے اس میں بہت زیادہ تغیر ہے، کیونکہ یہ ہمیشہ صفر یا ایک ہوتا ہے۔ من ہاش اسکیم کا خیال یہ ہے کہ اسی طرح بنائے گئے کئی متغیرات کو ایک ساتھ اوسط کرکے اس تغیر کو کم کیا جائے۔ بہت سے ہیش افعال کے ساتھ الگورتھم متغیر منہاش اسکیم کا سب سے آسان ورژن مختلف ہیش افعال کا استعمال کرتا ہے، جہاں ایک فکسڈ انٹیجر پیرامیٹر ہوتا ہے، اور ان افعال کے لیے ہر سیٹ کی نمائندگی کرتا ہے۔ اسکیم کے اس ورژن کا استعمال کرتے ہوئے اندازہ لگانے کے لیے، آئیے ہیش افعال کی تعداد جس کے لیے، اور تخمینے کے طور پر استعمال کریں۔ یہ تخمینہ مختلف 0-1 بے ترتیب متغیرات کی اوسط ہے، جن میں سے ہر ایک ایک ہے جب اور صفر بصورت دیگر، اور جن میں سے ہر ایک کا غیر جانبدار تخمینہ ہے۔ لہذا، ان کا اوسط بھی ایک غیر جانبدار تخمینہ ہے، اور 0-1 بے ترتیب متغیرات کے مجموعے کے لیے معیاری انحراف سے، اس کی متوقع غلطی ہے۔ لہذا، کسی بھی مستقل کے لیے ایک مستقل اس طرح ہوتا ہے کہ تخمینہ کی متوقع غلطی زیادہ سے زیادہ ہو۔ مثال کے طور پر، 0.05 سے کم یا اس کے برابر متوقع غلطی کا اندازہ لگانے کے لیے 400 ہیش کی ضرورت ہوگی۔ ایک ہیش فنکشن کے ساتھ متغیر ایک سے زیادہ ہیش فنکشن کا حساب لگانا کمپیوٹیشنل طور پر مہنگا ہو سکتا ہے، لیکن من ہیش اسکیم کا ایک متعلقہ ورژن صرف ایک ہیش فنکشن کا استعمال کرکے اس جرمانے سے بچتا ہے اور اسے ہر سیٹ سے متعدد اقدار کو منتخب کرنے کے لیے استعمال کرتا ہے بجائے اس کے کہ فی ہیش فنکشن میں صرف ایک کم از کم قیمت کو منتخب کیا جائے۔ ایک ہیش فنکشن ہونے دیں، اور ایک فکسڈ انٹیجر ہونے دیں۔ اگر ڈومین میں اقدار کا کوئی سیٹ یا اس سے زیادہ ہے، تو اس کی تعریف اس اراکین کے ذیلی سیٹ کے طور پر کریں جس کی سب سے چھوٹی اقدار ہیں۔ یہ ذیلی سیٹ سیٹ کے لیے دستخط کے طور پر استعمال ہوتا ہے، اور کسی بھی دو سیٹوں کی مماثلت کا اندازہ ان کے دستخطوں کا موازنہ کرکے لگایا جاتا ہے۔ خاص طور پر، A اور B کو کوئی بھی دو سیٹ ہونے دیں۔ پھر کے عناصر کا ایک مجموعہ ہے، اور اگر ایچ ایک بے ترتیب فنکشن ہے تو کے عناصر کا کوئی بھی ذیلی مجموعہ یکساں طور پر منتخب ہونے کا امکان ہے۔ یعنی، کا ایک سادہ بے ترتیب نمونہ ہے۔ سب سیٹ ان اراکین کا مجموعہ ہے جن کا تعلق چوراہے سے ہے۔ لہذا، | |/ایک غیر جانبدار تخمینہ کار ہے۔ اس تخمینہ کار اور متعدد ہیش افعال کے ذریعہ تیار کردہ تخمینہ کار کے درمیان فرق یہ ہے کہ ہمیشہ بالکل اراکین ہوتے ہیں، جبکہ متعدد ہیش افعال نمونے لینے والے عناصر کی ایک چھوٹی تعداد کا باعث بن سکتے ہیں اس امکان کی وجہ سے کہ دو مختلف ہیش افعال میں ایک ہی منیما ہو سکتا ہے۔ تاہم، جب سیٹ کے سائز کے مقابلے میں چھوٹا ہوتا ہے، تو یہ فرق نہ ہونے کے برابر ہوتا ہے۔ بغیر کسی تبدیلی کے نمونے لینے کے لیے معیاری چرنوف حدود کے مطابق، اس تخمینہ کار نے غلطی کی توقع کی ہے، جو ملٹی پل-ہیش فنکشن اسکیم کی کارکردگی سے میل کھاتی ہے۔ وقت کا تجزیہ تخمینہ کار کو اسکیم کے کسی بھی قسم میں، دیئے گئے سیٹوں کے دو دستخطوں سے وقت پر شمار کیا جا سکتا ہے۔ لہذا، کب اور کب مستقل ہیں، دستخطوں سے تخمینہ شدہ مماثلت کا حساب لگانے کا وقت بھی مستقل ہے۔ ہر سیٹ کے دستخط کو سیٹ کے سائز پر لکیری وقت میں شمار کیا جا سکتا ہے، لہذا جب بہت سی جوڑی کے لحاظ سے مماثلتوں کا اندازہ لگانے کی ضرورت ہوتی ہے تو یہ طریقہ ہر سیٹ کے ممبروں کا مکمل موازنہ کرنے کے مقابلے میں رننگ ٹائم میں کافی بچت کا باعث بن سکتا ہے۔ خاص طور پر، سیٹ سائز کے لیے بہت سے ہیش ورژن میں وقت لگتا ہے۔ سنگل ہیش ویرینٹ عام طور پر تیز ہوتا ہے، یہ فرض کرتے ہوئے کہ کم از کم ہیش ویلیوز کی قطار کو برقرار رکھنے کے لیے وقت درکار ہوتا ہے۔ وزن کو شامل کرنا من ہیش کے حساب میں وزن کو متعارف کرانے کے لیے مختلف تکنیکیں تیار کی گئی ہیں۔ سب سے آسان اسے انٹیجر وزن تک بڑھا دیتا ہے۔ سیٹ ممبر اور انٹیجر دونوں کو قبول کرنے کے لیے اپنے ہیش فنکشن کو بڑھائیں، پھر ہر آئٹم کے لیے اس کے وزن کے مطابق متعدد ہیش بنائیں۔ اگر آئٹم بار بار آتا ہے، تو ہیش بنائیں۔ ہیش کے اس توسیعی سیٹ پر اصل الگورتھم چلائیں۔ ایسا کرنے سے ٹکرانے کے امکان کے طور پر وزنی جیکارڈ انڈیکس حاصل ہوتا ہے۔ مزید توسیعات جو بہتر رن ٹائم کے ساتھ حقیقی وزن پر اس تصادم کے امکان کو حاصل کرتی ہیں، تیار کی گئی ہیں، ایک گھنے ڈیٹا کے لیے، اور دوسرا کم ڈیٹا کے لیے۔ توسیعات کا ایک اور خاندان تیزی سے تقسیم شدہ ہیش استعمال کرتا ہے۔ 0 اور 1 کے درمیان یکساں طور پر بے ترتیب ہیش کو سی ڈی ایف الٹ کے ذریعے ایکسپونینشیل ڈسٹری بیوشن کی پیروی کرنے کے لیے تبدیل کیا جا سکتا ہے۔ یہ طریقہ کم از کم ایکسپونینشیل متغیرات کے سیٹ کی بہت سی خوبصورت خصوصیات کا استحصال کرتا ہے۔ جیسا کہ اوپر بیان کیا گیا ہے، من ہیش اسکیم کو نافذ کرنے کے لیے عناصر پر بے ترتیب تعدد کی وضاحت کرنے کے لیے ہیش فنکشن کی ضرورت ہوتی ہے، جہاں موازنہ کیے جانے والے تمام سیٹوں کے اتحاد میں مختلف عناصر کی کل تعداد ہے۔ لیکن چونکہ مختلف ترتیبات ہیں، اس لیے اسے صرف صحیح معنوں میں بے ترتیب ترتیب کی وضاحت کے لیے بٹس کی ضرورت ہوگی، یہاں تک کہ اس کی اعتدال پسند اقدار کے لیے ایک ناقابل عمل حد تک بڑی تعداد۔ اس حقیقت کی وجہ سے، عالمگیر ہیشنگ کے نظریہ سے مشابہت کے لحاظ سے، ترتیبات کے ایک ایسے خاندان کو تلاش کرنے پر اہم کام ہوا ہے جو "کم از کم آزاد" ہے، جس کا مطلب ہے کہ ڈومین کے کسی بھی ذیلی سیٹ کے لیے، کسی بھی عنصر کے کم از کم ہونے کا امکان یکساں ہے۔ یہ قائم کیا گیا ہے کہ تعدد کے ایک منٹ کے لحاظ سے آزاد خاندان میں کم از کم مختلف تعدد شامل ہونا ضروری ہے، اور اس وجہ سے اسے ایک واحد تعدد کی وضاحت کے لیے بٹس کی ضرورت ہے، جو اب بھی ناقابل عمل حد تک بڑا ہے۔ عملی کم از کم لحاظ سے آزاد ہیش افعال مذکورہ بالا ناقابل عملیت کی وجہ سے، کم از کم لحاظ سے آزادی کے دو مختلف تصورات متعارف کرائے گئے ہیں: محدود کم از کم لحاظ سے آزاد تغیرات والے خاندان، اور تقریبا کم از کم لحاظ سے آزاد خاندان۔ محدود منٹ کے لحاظ سے آزادی منٹ کے لحاظ سے آزادی کی خاصیت ہے جو زیادہ سے زیادہ کارڈینالیٹی کے کچھ سیٹوں تک محدود ہے۔ تقریبا کم سے کم لحاظ سے آزادی میں زیادہ سے زیادہ مکمل آزادی سے مختلف ہونے کا ایک مقررہ امکان ہوتا ہے۔ 1999 میں پیوٹر انڈیک نے ثابت کیا کہ ہیش افعال کا کوئی بھی کے کے لحاظ سے آزاد خاندان بھی کافی بڑے کے لیے تقریبا کم سے کم لحاظ سے آزاد ہے۔ خاص طور پر، ایسے مستقل ہوتے ہیں کہ اگر، تو تمام سیٹوں کے لیے اور۔ (نوٹ، یہاں اس کا مطلب ہے کہ امکان زیادہ سے زیادہ ایک عنصر ہے جو بہت بڑا ہے، اور زیادہ سے زیادہ بہت چھوٹا ہے۔) یہ ضمانت، دوسری چیزوں کے علاوہ، من ہیش الگورتھم کے ذریعہ درکار جیکارڈ باؤنڈ دینے کے لیے کافی ہے۔ یعنی، اگر اور سیٹ ہیں، تو چونکہ کے کے لحاظ سے آزاد ہیش افعال کو صرف بٹس کا استعمال کرتے ہوئے متعین کیا جا سکتا ہے، یہ نقطہ نظر مکمل طور پر کم سے کم لحاظ سے آزاد ترتیبات کا استعمال کرنے سے کہیں زیادہ عملی ہے۔ ہیش افعال کا ایک اور عملی خاندان جو کم از کم لحاظ سے تقریبا آزادی دیتا ہے ٹیبولیشن ہیشنگ ہے۔ ایپلی کیشنز من ہیش کے لیے اصل ایپلی کیشنز میں کلسٹرنگ اور ویب دستاویزات کے درمیان قریب ڈپلیکیٹ کو ختم کرنا شامل تھا، جو ان دستاویزات میں پائے جانے والے الفاظ کے سیٹ کے طور پر پیش کیے جاتے ہیں۔ اسی طرح کی تکنیکوں کو دیگر اقسام کے ڈیٹا کے لیے کلسٹرنگ اور قریب ڈپلیکیٹ خاتمے کے لیے بھی استعمال کیا گیا ہے، جیسے کہ تصاویر: تصویری ڈیٹا کے معاملے میں، کسی تصویر کو اس سے تیار کردہ چھوٹی ذیلی تصاویر کے سیٹ کے طور پر، یا زیادہ پیچیدہ تصویری خصوصیت کی وضاحت کے سیٹ کے طور پر پیش کیا جا سکتا ہے۔ ڈیٹا مائننگ میں، ایسوسی ایشن رول لرننگ کے آلے کے طور پر من ہاش کا استعمال کریں۔ ایک ڈیٹا بیس کو دیکھتے ہوئے جس میں ہر اندراج میں متعدد صفات ہوتی ہیں (فی ڈیٹا بیس اندراج کی ایک قطار اور فی خاصیت کے کالم کے ساتھ 0-1 میٹرکس کے طور پر دیکھا جاتا ہے) وہ جیکارڈ انڈیکس کے لیے من ہاش پر مبنی تخمینوں کا استعمال کرتے ہیں تاکہ ان صفات کے امیدوار جوڑوں کی شناخت کی جا سکے جو اکثر ایک ساتھ ہوتے ہیں، اور پھر صرف ان جوڑوں کے لیے انڈیکس کی صحیح قیمت کا حساب لگائیں تاکہ ان کا تعین کیا جا سکے جن کی تعدد ایک دی گئی سخت حد سے نیچے ہے۔ من ہیش الگورتھم کو بائیو انفارمیٹکس کے لیے ڈھال لیا گیا ہے، جہاں جینوم کے ترتیبات کا موازنہ کرنے کا مسئلہ ویب پر دستاویزات کا موازنہ کرنے کی طرح نظریاتی بنیاد رکھتا ہے۔ من ہیش پر مبنی ٹولز حوالہ جینومز کے ساتھ پورے جینوم کی ترتیب کے اعداد و شمار کا تیزی سے موازنہ کرنے کی اجازت دیتے ہیں (ریفسیک میں 90000 حوالہ جینومز کے ساتھ ایک جینوم کا موازنہ کرنے کے لیے تقریبا 3 منٹ)، اور قیاس آرائی کے لیے موزوں ہیں اور شاید محدود حد تک مائکروبیل ذیلی ٹائپنگ کے لیے موزوں ہیں۔ میٹا جینومکس اور جینوم صف بندی اور جینوم اسمبلی کے لیے من ہاش سے ماخوذ الگورتھم کے استعمال کے لیے بھی ایپلی کیشنز ہیں۔ درست اوسط نیوکلیوٹائڈ شناخت (اے این آئی) اقدار کو من ہاش پر مبنی الگورتھم کے ساتھ بہت مؤثر طریقے سے تیار کیا جا سکتا ہے۔ دیگر استعمال من ہیش اسکیم کو لوکیٹی حساس ہیشنگ کی ایک مثال کے طور پر دیکھا جا سکتا ہے، جو ہیش افعال کو استعمال کرنے کی تکنیکوں کا مجموعہ ہے تاکہ اشیاء کے بڑے سیٹوں کو چھوٹے ہیش ویلیوز تک اس طرح سے نقشہ بنایا جا سکے کہ جب دو اشیاء ایک دوسرے سے تھوڑا سا فاصلہ رکھتی ہیں تو ان کی ہیش ویلیوز کا امکان ایک جیسا ہوتا ہے۔ اس مثال میں، کسی سیٹ کے دستخط کو اس کی ہیش ویلیو کے طور پر دیکھا جا سکتا ہے۔ سیٹوں کے درمیان ہیمنگ فاصلے اور ویکٹروں کے درمیان کوسین فاصلے کے لیے مقامی حساس ہیشنگ کی دیگر تکنیکیں موجود ہیں۔ مقامی حساس ہیشنگ کے قریبی پڑوسی سرچ الگورتھم میں اہم استعمال ہوتے ہیں۔ بڑے تقسیم شدہ نظاموں کے لیے، اور خاص طور پر میپ ریڈیس کے لیے، پوائنٹ طول و عرض پر انحصار کے بغیر مماثلتوں کا حساب لگانے میں مدد کے لیے من ہاش کے ترمیم شدہ ورژن موجود ہیں۔ تشخیص اور معیارات گوگل کی طرف سے 2006 میں مینہاش اور سمہاش الگورتھم کی کارکردگی کا موازنہ کرنے کے لیے بڑے پیمانے پر تشخیص کی گئی تھی۔ 2007 میں گوگل نے ویب کرالنگ کے لیے ڈپلیکیٹ ڈٹیکشن کے لیے سمہاش کا استعمال کرنے اور گوگل نیوز پرسنلائزیشن کے لیے منہش اور ایل ایس ایچ کا استعمال کرنے کی اطلاع دی۔ یہ بھی دیکھیں حوالہ جات ہیش افعال کلسٹرنگ معیار ہیشنگ ممکنہ ڈیٹا ڈھانچے