در [۹] متون را به دنباله­هایی با طول کلمه آن کد کرده و از معیار فاصله­ی nگرام مبتنی بر بردار برای انتخاب­های کاندیداها استفاده کردند.

۲-۲-۴ روش تشخیص پلاگاریسم خارجی
تشخیص پلاگاریسم خارجی مبتنی بر مجموعه نوشته­ های خارجی است که متون آن­ها ممکن است پلاگاریسم شده باشند. یک متن می ­تواند شامل پاراگراف، یک بلاک از کلمات با سایز ثابت، یک بلاک از جملات و غیره باشد. پلاگاریسم در یک داکیومنت مشکوک با جستجوی متن­هایی که تکراری یا نزدیک به تکراری با متن مجموعه هستند صورت می­گیرد. یک سیستم پلاگاریسم خارجی، این یافته­ ها را به کنترل­ کننده­ های انسانی گزارش می­دهد و آنها هستند که تصمیم می­گیرند که آیا متن­های یافته شده دزدی هستند یا نه. این قبیل سیستم­ها در مرجع [۱۰] برای پیدا کردن داکیومنت­های تکراری یا نزدیک به تکراری استفاده شده است.
روش دیگر برای پیدا کردن تکرارها براساس درهم­سازی شاخص ­ها است. چنین روش­هایی یک یا چند شاخص را ایجاد می­ کنند، که محتوای داکیومنت یا متن را در خود حمل می­ کنند. اولین سیستم تولید کننده­ شاخص که از این روش استفاده می­ کند در مرجع [۲] آمده است. تشخیص پلاگاریسم خارجی، می ­تواند به عنوان مسئله­ نزدیک­ترین همسایه در فضای برداری نیز در نظر گرفته شود.
۲-۳ روش­های محاسبه میزان شباهت گراف­ها
از آنجایی که در ادامه این پایان نامه هدف ما ارائه و پیاده­سازی راهکاری در زمینه­ تشخیص متن با بهره گرفتن از گراف است، بنابراین همانطور که در بخش “توضیح مسئله” گفته شد، مقایسه متون در قالب گراف از اهمیت ویژه­ای برخوردار است. مفاهیم شباهت گراف، فاصله­ی گراف و تطبیق گراف پایه­ های اصلی روش­های تشخیص پلاگاریسم مبتنی بر گراف هستند. ما در این بخش به ارائه روش­های موجود در زمینه­ مشخص کردن شباهت­ها، فاصله­ها و انطباق گراف­ها می­پردازیم.
۲-۳-۱ روش بزرگترین زیرگراف مشترک - کوچکترین سوپرگراف مشترک
در [۱۲] نشان داده شده است که یک رابطه­ مستقیم بین فاصله­ی ویرایش گراف و بزرگترین زیرگراف مشترک دو گراف وجود دارد. به طور ویژه، هر دو تحت محدودیت­های خاصی روی تابع هزینه معادل هم هستند. یک گراف g ، یک بزرگترین زیرگراف مشترک (mcs) گراف­های و است و توسط عبارت مشخص می­ شود، اگر:

1. 1. هیچ زیرگراف با شرایط g وجود نداشته باشد به طوری که .

به طور مشابه، بخش دوم کامل کننده­ این ایده یعنی کوچکترین سوپرگراف مشترک که توسط عبارت مشخص می­ شود، باید در شرایط زیر صدق کند:

1. 1. هیچ سوپرگراف دیگری وجود ندارد که در شرایط ۱ و ۲ صدق کند اما .

راهبرد کلی شامل ایجاد یک گراف تطبیقی برای دو گراف مورد مقایسه و پیدا کردن بزرگترین دسته در آن است. آنچه [۱۲] نشان داده این است که زمانی که تابع تطبیق ویرایش را بر اساس فاصله ویرایش گراف محاسبه می­کنیم، تحت شرایط خاصی روی ضرایب هزینه، تابع با کمترین هزینه معادل بزرگترین زیرگراف مشترک بین دو گراف است. این اثبات بسیار خوشایند است، زیرا بزرگترین زیرگراف مشترک بخشی از دو گراف است که تحت عملیات ویرایشی حذف و اضافه نودها و لبه­ها بدون تغییر مانده است. برای ویرایش گراف برای تبدیل آن به گراف تنها باید مراحل زیر طی شوند:

1. 1. حذف نودها و لبه­هایی از که در ظاهر نمی­شوند.

1. 1. انجام هرگونه جایگزینی نود یا لبه.

1. 1. اضافه کردن نودها و لبه­هایی از که در ظاهر نمی­شوند.

با در نظر گرفتن این نکته که سایز بزرگترین زیرگراف مشترک متناظر شباهت بین دو گراف است، در [۱۳] یک معیار فاصله براساس mcs معرفی شده است. این معیار در فرمول زیر نشان داده شده است:
که max(x,y) ماکزیمم دو عدد x و y، و نشان دهنده سایز یک گراف است. هر چه زیرگراف مشترک بزرگ­تر باشد، کوچکتر می­ شود و نشان­دهنده شباهت بیشتر و فاصله­ی کمتر است. اگر دو گراف یکی باشند اندازه زیرگراف مشترک برابر با سایز گراف­ها خواهد بود و در نتیجه کمترین مقدار ممکن خود را خواهد داشت و برابر صفر خواهد بود. در مقابل اگر دو گراف هیچ وجه اشتراکی نداشته باشند برابر صفر و یک خواهد بود. این معیار فاصله دارای چهار مزیت مهم است:

1. 1. محدود به تولید عدد در بازه [۰,۱] است.

1. 1. تنها زمانی که دو گراف یکی باشند فاصله صفر خواهد بود.

1. 1. فاصله­ی بین دو گراف متقارن است.

1. 1. از نامساوی مثلثی تبعیت کرده و تضمین می­ کند که معیار فاصله از لحاظ مفهومی درست عمل می­ کند.

مزیت این روش در حیطه­ی فاصله­ی ویرایش گراف این است که این روش نیاز به مشخص کردن هیچ ضریب هزینه­ای و پارامتر دیگری ندارد. با این حال، این معیار در همه کاربردها مناسب نخواهد بود.
۲-۳-۲ روش مبتنی بر جستجوی فضای حالت
برای پیدا کردن فاصله در روش فاصله ویرایش گراف ما نیاز به یک تابع تطبیق ویرایش داریم که دارای کمترین هزینه بر اساس ضرایب هزینه موجود باشد. بسته به اندازه گراف­ها و هزینه­ های مرتبط با عملیات ویرایش، پیدا کردن کمترین هزینه­ نگاشت ممکن است نیاز به محاسبه تعداد بسیار زیادی از تمام تطبیق­های ممکن داشته باشد. اگر مجبور نباشیم که فاصله­ی دقیق ویرایش بین دو گراف را محاسبه کنیم، می­توانیم از روش­های جستجوی نیمه بهینه با فضای جستجوی کمتر استفاده کنیم. این جستجوها مینیمم سراسری تابع هزینه را پیدا نمی­کنند، ولی خیلی سریع­تر عمل کرده و پاس
خ­های قابل قبولی ارائه می­ دهند.
هر عمل تطبیق یک حالت در فضای جستجو است. هزینه­ آن حالت M مقداری در فضای جستجو است که ما می­خواهیم آن را کمینه کنیم. در حقیقت M یک همریختی گراف بین زیرگراف­های دو گرافی است که با هم تطبیق می­شوند و بیانگر عملیات مورد نیاز برای ویرایش یک گراف برای تبدیل آن به گراف دیگر است. روش­های متعددی برای انجام جستجو در این فضا وجود دارند، از قبیل تپه­نوردی، الگوریتم­های ژنتیک و خنک­سازی شبیه­سازی شده و بسیاری دیگر.
این جستجوها بهترین پاسخ را پیدا نخواهند کرد، اما برای بعضی کاربردها (از قبیل تطبیق گراف برای بازیابی تصاویر یا متون) مشکل­ساز نخواهند بود. این تکنیک­ها همچنین نسبت به وضعیت اولیه و مقادیر پارامترها حساس هستند[۱۴].
۲-۳-۳ روش­های احتمالی
در این بخش روش معرفی شده در [۱۵] را که بر پایه­ تئوری احتمال است، به طور خلاصه بیان می­کنیم. در روش احتمالی، سعی بر تطبیق گراف داده G_D و گراف مدل ذخیره ­شده­ G_M است. این گراف­ها، گراف­های ویژگی معین هستند. یک گراف ویژگی معین، یک گـراف است که A یک مجموعه از ویژگی­های متناظر هر نود است، .
ویژگی­ها در یک گراف معین باید با همان ویژگی­ها در گراف مدل منطبق شود، به طوری که نودهای منطبق شده یکسان یا دارای ویژگی­های مشابه باشند. لبه­ها نیز همچنین دارای ویژگی­های متناظر در گراف مدل هستند ولی در این روش در نظر گرفته نمی­شوند. سپس با مفهوم سوپرگروه یک نود مواجه می­شویم. یک سوپرگروه یک نود i در گراف G=(V,E) به صورت زیر تعریف می­ شود:
به عبارت دیگر، سوپرگروه یک نود i مجموعه نودهایی است که i و همه نودهای متصل شده به آن توسط لبه­ها را در بر دارد. ما سعی داریم که همه سوپرگروه­ها در گراف داده را با سوپرگروه­ها در گراف مدل تطبیق دهیم.
مجموعه­ همه تطبیق­های ممکن بین سوپرگروه C_i در گراف داده G_D و سوپرگروه S_j در گراف مدل G_M ، دیکشنری نامیده می­ شود و توسط مشخص می­ شود. برای حل مسئله­ اختلاف سایز بین سوپرگروه­های داده و مدل، امکان وجود نودهای خالی نیز هست که می­توانند به S_j اضافه شوند تا دو گراف دارای تعداد نودهای برابر شوند. تابعی که نود در C_i را با نودی در S_j منطبق می­ کند به صورت زیر تعریف می­ شود:
احتمال خطاهای تطبیق توسط و احتمال خطاهای ساختاری توسط مشخص می­ شود. با این تعاریف و در نظر گرفتن تعدادی فرض و با بهره گرفتن از قانون بیز و ساختارهای احتمالی دیگر در [۱۵] یک توصیف ریاضی برای احتمال انطباق یک سوپرگروه بین دو گراف ارائه نمودند:
که
فاصله همینگ بین سوپرگروه گراف داده تحت نگاشت f و سوپرگروه گراف مدل، ، و تعداد نودها در است به طوری که به نودهای خالی در نگاشته شده ­اند.
بعد از ارائه و تشریح این توصیف ریاضی به بیان قوانینی که می­توانند برای به روز کردن تابع انطباق استفاده شوند، پرداخته شده است. روش­ها شامل قوانین به روز رسانی به فرم زیر هستند:
P(u,v) احتمال اولیه­ متناظر بودن نود u در گراف داده با نود v در گراف مدل است، درحالی که سایر احتمال­ها در صورت کسر احتمال شرطی هستند که متناظر با ویژگی­های مرتبط با نود هستند. روش­های تعیین این احتمال­ها وابسته به کاربرد هستند.
این روش می ­تواند به عنوان تابع انرژی تطبیق گراف استفاده شود. روش دیگری از این فرمول برای جستجوی ژنتیک تطبیق گراف­ها استفاده کرده است. در [۱۶] این روش را اصلاح نموده و فاصله ویرایش گراف را به آن اضافه کرده است، روش جدید با رفع نیاز به اضافه کردن نود خالی باعث ساده­تر شدن مدل و ایجاد مدل بهتر شده است.
فصل سوم
تئوری پلاگاریسم
این فصل به بیان تئوری پلاگاریسم می ­پردازد. در مسئله تشخیص پلاگاریسم دو مرحله حائز اهمیت هستند: