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

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

  (( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

هدف اصلی این فصل معرفی مفاهیم مورد نیاز در زمینه تشخیص پلاگاریسم و محاسبه فاصله ویرایش گراف است.
۳-۱ تشخیص پلاگاریسم
به منظور تشخیص پلاگاریسم، تکنیک­های بازیابی اطلاعات متعددی به کار برده شده ­اند. این بخش تکنیک­هایی را معرفی می­ کند که برای تطبیق متون مورد نیاز هستند.
۳-۱-۱ تطبیق 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 از همه سریع­تر است و دارای پیچیدگی زمانی است.
فصل چهارم
روش پیشنهادی و پیاده­سازی