• روش ارائه متن: این روش امکاناتی را فراهم می­ کند که ویژگی­های ساختاری و معنایی متمایز کننده متن را استخراج کرده و بتوان از آن­ها به عنوان شاخص­ های متمایزکننده­ی متن و به اصلاح اثرانگشت متن استفاده کرد. هر چقدر ویژگی­های متمایز کننده متن در این مرحله بتوانند به طور کامل و درست استخراج شوند، تشخیص پلاگاریسم دقیق­تر و حقیقی­تر خواهد شد.

• • روش مقایسه­ متن ارائه شده در قالب روش ارائه شده در مرحله قبل: بعد از اینکه مطمئن شدیم متن در قالبی کارآمد ارائه شد، که علاوه بر حذف کردن بخش­های زائد و تکراری متن که تنها منجر به سربار حافظه­ای و محاسباتی می­شوند اطلاعات متمایز کننده را استخراج و بارز نموده است، نیاز به ارائه راهبردی برای مقایسه­ متون در این قالب کارآمد داریم. روش مقایسه باید بتواند با کمترین هزینه محاسباتی بیشترین بهره را از اطلاعات استخراج شده ببرد و قدرت تشخیص سیستم را در حد ممکن بالا ببرد.

هدف اصلی این فصل معرفی مفاهیم مورد نیاز در زمینه تشخیص پلاگاریسم و محاسبه فاصله ویرایش گراف است.
۳-۱ تشخیص پلاگاریسم
به منظور تشخیص پلاگاریسم، تکنیک­های بازیابی اطلاعات متعددی به کار برده شده ­اند. این بخش تکنیک­هایی را معرفی می­ کند که برای تطبیق متون مورد نیاز هستند.
۳-۱-۱ تطبیق n گرام
یک nگرام زیرمجموعه­ای از n جز یک متن است. هر جز در شکل پایه­ای آن توسط یک کلمه بیان می­ شود[۱۷]. n اندازه­ زیردنباله است. یک nگرام با اندازه­ ۱ یونیگرام نامیده می­ شود، با سایز ۲ ، بایگرام و با سایز ۳ ، ترایگرام. nگرام­های سایز بالاتر توسط اعدادشان مشخص می­شوند. اجزای nگرام اجزای دیگر را بیان می­ کنند، از قبیل کاراکتر در کلمه، که کاربردهای دیگری دارند. تمرکز این پایان نامه روی تطبیق سطح جمله است، بنابراین تنها nگرام­های سطح کلمه در نظر گرفته می­شوند.
تطبیق nگرام یک روش کاملا معمول در زمینه­ طبقه ­بندی متن است. مفهوم پایه­ای پشت تطبیق nگرام شامل شمارش تعداد تطبیق­های nگرام­ها در دو متن است. یک روش معمول شامل ترکیب تطبیق­های nگرام­ها با سایزهای مختلف است. کاربردهای مختلف از سایزهای مختلف nگرام­ها بهره می­برند و بهترین اندازه وابسته به مسئله و مجموعه داده ­های آن است.
۳-۱-۲ وزن­دهی عبارت
در طی بازیابی اطلاعات، اهمیت هر عبارت می ­تواند توسط یک وزن مشخص شود. هر عبارت بر اساس اینکه چقدر در حل یک مسئله تاثیر می­ گذارد، وزن­دهی می­ شود. زیربخش­هایی که در ادامه می­آیند روش­های معمول در وزن­دهی عبارات را ارائه می­ کنند، که در عین حال برای مسئله تشخیص پلاگاریسم قابل استفاده هستند.
حذف stop-wordها
Stop-wordها عباراتی هستند که در تمام متون وجود دارند همانند: مثل، از، به، ولی و غیره. این قبیل عبارات مستقل از محتوای متن هستند و اطلاعات معنایی کمی راجع به متن فراهم می­ کنند[۱۸]. حذف کننده stop-word برای این استفاده می­ شود که معنی یک متن بهتر استخراج شود، زیرا عبارات stop-word در تشخیص مفهوم متن تاثیر کمتری می­گذارند.
فرکانس عبارت- وزن­دهی فرکانسی داکیومنت معکوس
پیشرفته­ترین تکنیک وزن­دهی، وزن­دهی فرکانس عبارت-فرکانس داکیومنت معکوس (TF-IDF) است[۱۹]. تکنیک تعداد رخدادهای عبارات را در یک داکیومنت داده شده و تعداد آنها در کل داکیومنت­ها را با هم محاسبه می­ کند. به این ترتیب، عباراتی که کمتر تکرار شده ­اند و خاص­تر هستند دارای مقدار بزرگتری نسبت به عبارات تکراری­تر می­شوند. فرمول­های متعددی در این زمینه وجود دارند، اما یکی از مهم­ترین آنها به صورت زیر است (t عبارت، d داکیومنت و D مجموعه داکیومنت­ها است):
که تکرار عبارت t در داکیومنت d است. معمولا تکرار عبارت با محاسبه تعداد رخدادهای عبارت تقسیم بر تعداد عبارات در داکیومنت محاسبه می­ شود. فرکانس داکیومنت معکوس است و معمولا با محاسبه­ی لگاریتم تعداد داکیومنت­ها تقسیم بر تعداد داکیومنت­هایی که عبارت t را دارند محاسبه می­ شود.
قدرت وزن­دهی TF-IDF توانایی آن در وزن­دهی همه عبارات است. عبارات منحصر به فرد دارای بالاترین وزن می­شوند، در حالی که عبارات تکراری کمترین وزن را به خود اختصاص می­ دهند. وزن­دهی TF-IDF نیاز به جستجوی دیکشنری دارند، بنابراین این روش مستقل از زبان است. با این حال پیدا کردن مقادیر IDF برای هر عبارت نیاز به محاسبه دارد.
۳-۱-۳ تعمیم عبارت
زیربخش­هایی که در ادامه آمده­اند تکنیک­هایی را توصیف می­ کنند که به ما امکان بیان عبارات را در فرم عمومی­تری فراهم می­ کنند.
ریشه­یابی
ریشه­یابی فرایند بیان انواع شکل­های یک کلمه به صورت عمومی­تر است، که ریشه نامیده می­ شود. به عنوان نمونه، کلمه بود شامل فرم­های بودم، بودی، بودند، بوده­ایم و غیره است. با ارائه­ فرم­های مختلف آن توسط کلمه­ی بود، تطبیق کلمات خیلی پایدارتر می­ شود.
با این حال، بیان کلمات توسطِ ریشه­هایشان، در حالاتی که دو کلمه­ی متفاوت دارای یک ریشه هستند، می ­تواند منجر به اشتباه شود. کلمات خرید در دو جمله “او به خرید می­رود” و “او یک کتاب خرید” دارای ریشه مشترک خرید هستند که در یکی اسم و دیگری فعل است. هر دو کلمه دارای یک ریشه هستند و اگر فقط ریشه در نظر گرفته شود ممکن است یکسان در نظر گرفته شوند.
۳-۲ </st rong>گراف­های وابستگی
یک گراف وابستگی یک ارائه­ ساخت­یافته از یک جمله است. به منظور ایجاد گراف­های وابستگی، یک جمله توسط یک پارسر وابستگی پردازش می­ شود، که مبتنی بر یافته­های تئوریکی گرامر وابستگی است. گرامر وابستگی به صورت یک خانواده از تئوری­ها است که تعدادی فرضیه­ پایه­ای را درباره ساختار گرامری به اشتراک می­گذارند [۲۰].
ساختارهای گرامری می­توانند خیلی پیچیده باشند و اغلب ورژن­های گراف وابستگی ساده شده ساختارهای وابستگی تئوری هستند. گراف­های وابستگی پیچیده نیاز به الگوریتم­هایِ پیچیده دارند. گراف­های ساده وضوح کمتری دارند، ولی کار با آنها راحت­تر است، به خصوص اگر هدف تجزیه­ی وابستگی خودکار باشد. لبه­ها نمایانگر وابستگی بین نودها هستند. برچسب لبه نوع وابستگی را مشخص می­ کند. این ویژگی­ها با جزئیات کامل در بخش بعد توضیح داده خواهند شد.
۳-۲-۱ وابستگی­ها
یک وابستگی بین دو عبارت، شامل یک هدر و وابستگی است. به عبارت دیگر، وابستگی­ها جهت­دار هستند و گراف وابستگی را به گراف جهت­دار تبدیل می­ کنند. اغلب نیاز است که بین روابط وابستگی متعدد تمایز قائل شویم. برچسب­های لبه، روابط بین هدر و وابسته­ها را مشخص می­ کنند. روابط بین توپ و شوت شد را در شکل ۱-۱ در نظر بگیرید. در اینجا رابطه بین توپ و شوت شد، مفعول است، یعنی توپ مفعول فعل شوت شد است. به طور کلی، این وابستگی شامل یک رابطه بین عمل (شوت کردن) و موجودیتی (توپ) است که به طور مستقیم توسط این عمل تحت تاثیر واقع شده است.
۳-۳ فاصله ویرایش گراف
فاصله­ی ویرایش گراف معیاری برای سنجش اختلاف دو گراف است، که با محاسبه­ی مینیمم تعداد عملیاتی که لازم است در یک گراف انجام داده شود تا مشابه گراف دیگر شود، بدست می ­آید[۱]. یک عمل ویرایش می ­تواند روی نود یا لبه صورت گیرد، تعریف ۱ را دنبال کنید.
تعریف۱- عملیات ویرایش بین دو گراف و شامل یکی از سه عمل جایگزینی ، اضافه کردن یا حذف کردن است، که نودی در و نودی در است.
عمل جایگزینی در تعریف ۲ توضیح داده شده است.
تعریف۲- عمل جایگزینی شامل یک عمل اضافه کردن و یک عمل حذف کردن است.
۳-۳-۱ عملیات ویرایش
عملیات ویرایش نیاز به تبدیل گراف مبدا به گراف مقصد دارد، که یک مسیر ویرایش را شکل می­دهد. شکل ۳-۱ مسیر ویرایش مورد نیاز برای تبدیل جمله­ “کودک توسط مادر در آغوش گرفته شد"، به جمله “مادر کودک را در آغوش گرفت” را نشان می­دهد [۲۱].
شکل ۳- ۱ : مثال عملیات ویرایش برای دو گراف
هر عمل ویرایش دارای هزینه­ مربوط به خود است، که با عنوان تابع هزینه مشخص می­ شود. یک تابع هزینه برچسب نودها را با هم منطبق می­ کند و در عین حال اختلاف­ها را برطرف می­نماید. تابع هزینه ممکن است از یک کاربرد به کاربرد دیگر متفاوت باشد.
۳-۳-۲ مسئله­ انتساب
پیچیدگی زمانی برای تطبیق­ِ n نود به m نود، که n و m نودهای دو گراف هستند، برابر است، در نتیجه مسئله دارای پیچیدگی توانی روی تعداد نودها است. در نتیجه نیاز داریم از یک روش جایگزین استفاده نماییم.
یک راه حل سریع و نیمه­بهینه توسطِ [۲۱] معرفی شده است. راه حلِ آنها مبتنی بر مسئله­ انتساب است، که n عامل را به m شغل منتسب می­ کند، که هر عامل دستمزد مختصِ خود را برای پذیرش یک شغل دارد. هدف پیدا کردن ارزان­ترین انتساب است و هزینه­ های عملیات ویرایش در اینجا نقش هزینه­ های کارهایِ مختلف را بازی می­ کند.
شکل ۳- ۲ : مسئله انتساب
شکل ۳-۲ مسئله انتساب را برای دو جمله­ شکل ۳-۱ نشان می­دهد. از آنجایی که دو جمله دارای تعداد نابرابری کلمه هستند، دو عمل حذف و دو عمل اضافه انجام می­ شود. هزینه­ ویرایش معادل کل هزینه­ ویرایش است.
۳-۳-۳ ماتریس هزینه
زمانی که فاصله ویرایش را برای دو گراف محاسبه می­کنیم، یک ماتریس هزینه­ دوبعدی می­توان تشکیل داد که هزینه را برای هر کدام از عملیات ویرایش برای هر نود در خود دارد. با ایجاد این ماتریس هزینه، مسئله­ فاصله­ی ویرایش به یک مسئله انتساب تقلیل می­یابد، که ساده­تر می­توان آن را حل کرد.
کمترین هزینه­ ویرایش برابر با فاصله ویرایش تقریبی محاسبه شده برای دو گراف است. تابع هزینه به صورت زیر ایجاد می­ شود:
ماتریس دارای سایز است، که و نشان­دهنده تعداد نودها در هر گراف هستند. هر سلول هزینه­ عملیات ویرایش را بین نودهای و نشان می­دهد. هر نود تنها حق دارد یک عمل ویرایش انجام دهد. ناحیه­ی سمت چپ بالای ماتریس هزینه­ های جایگزینی نودها را مشخص می­ کند، در حالی­که ناحیه­ی سمت چپ پایین هزینه­ اضافه کردن نود را مشخص می­ کند. ناحیه­ی سمت راست بالا هزینه­ حذف نود و ناحیه پایین سمت راست هزینه­ جایگزینی­هایی به فرم است که هیچ هزینه­ای ندارد.
۳-۳-۴ الگوریتم­های انتساب
الگوریتم­های متعددی وجود دارند که مسئله­ انتساب را حل می­ کنند، که از لحاظ سرعت عملیات متفاوت هستند. Fankhauser سه الگوریتم را برای حل مسئله­ انتساب معرفی کرده است[۱]. الگوریتم دوره­گرد، الگوریتم مانکرس و الگوریتم Volgenant-Jonker. او در مقاله خود نشان داد که الگوریتم Volgenant-Jonker از همه سریع­تر است و دارای پیچیدگی زمانی است.
فصل چهارم
روش پیشنهادی و پیاده­سازی