تجربه هاي شخصي من

تکنیک Fingerprinting

هر گاه تعدادی فایل داشته باشیم که هر یک از آنها شامل میلیونها رکورد اطلاعاتی هستند به طوریکه برخی از این فایلها دارای محتوای یکسانی هستند و تنها ترتیب قرارگیری رکوردها در آنها متفاوت است، اما برخی دیگر از این فایلها هم به طور کل محتوایی متفاوت دارند. یکی از ساده‌ترین راهها برای یافتن فایلهای دارای رکوردهای یکسان، این است که در هر یک از فایلها، تمام رکوردها را بر اساس ترتیبی خاص مرتب کنیم و سپس برای تشخیص برابری هر دو فایل، مقایسه رکوردهایشان را از اولین رکورد آغاز کنیم تا به آخرین رکورد برسیم. این کار برای دو فایل ۸ مگابایتی، ۳۰ ثانیه طول می‌کشد و مسلماً وقتی اندازه فایلها بیشتر و تعدادشان زیادتر گردد، این زمان بسیار بالا می‌رود. روش دیگر برای مقایسه دو فایل که در پروژه درس الگوریتمهای تصادفی انجام دادم و این زمان را به ۲ ثانیه کاهش می‌دهد این است که هر یک از n رکورد داخل هر فایل را به یک عدد ۳۲ بیتی تبدیل کنیم و سپس با استفاده از این n عدد، برای هر فایل یک چند جمله‌ای درجه n بسازیم. حال می‌توان ادعا کرد که دو فایل دارای رکوردهای یکسانی هستند، اگر و تنها اگر دارای چندجمله‌ای‌های یکسانی باشند. اما مقایسه دو چند جمله‌ای نیز کار زمانبری است. در اینجا می‌توان از تکنیک Fingerprinting استفاده کرد که یکی از روشهای مهم برای مقایسه دو شئ (Object) می‌باشد به این صورت که هر گاه اندازه دو شئ بسیار بزرگ باشد، با استفاده از این روش می‌توان اندازه آنها را کوچک کرد و البته باید خطای این کار را هم به طور دقیق محاسبه کرد. به عنوان مثال برای اینکه بفهمیم آیا دو چند جمله‌ای P و Q با هم برابر هستند یا خیر، می‌توانیم مقدار (P(x و (Q(x را به ازای یک x خاص محاسبه کنیم و در صورت برابرای آنها، برابری P و Q را اعلام کنیم. مسلماً در این روش خطا وجود دارد. قضیه Schwartz-zippel ثابت می‌کند که اگر x به طور تصادفی و از یک مجموعه نسبتاً بزرگ انتخاب شود، میزان خطا بسیار کم می‌شود.
———————–
منابع:
- کتاب Randomized Algorithms نوشته Rajeev Motwani و Prabhakar Raghavan.
- تعریف پروژه درس الگوریتمهای تصادفی
- گزارش من برای پروژه