چکیدهتمرکز این پایاننامه روی جستجوی شباهتهای مبتنی بر گراف، در متون مربوط به زبانهای طبیعی است. نیاز به یک روش قوی برای ارائه متون، مسئله مهمی در زمینه تشخیص پلاگاریسم است، ما در این پروژه با توجه به این نیاز، روشی قدرتمند را برای ارائه زبان طبیعی معرفی نموده و از آن در تشخیص پلاگاریسم بهره بردهایم. برای این منظور مفهوم "فاصله اصلاح گراف" را بیان نموده و از آن برای محاسبه فاصلهی بین دو گراف استفاده کردهایم. جملات توسط گرافهای وابستگی ارائه شدهاند که در آنها کلمات توسط وابستگیهایشان به هم متصل شدهاند. گراف وابستگی ساختار گرامری جملات را استخراج میکند. روش شباهت مبتنی بر گراف در مسئله تشخیص پلاگاریسم به کار برده شده است. مزیت اصلی ارائه مبتنی بر گراف، مربوط به توانایی این روش در تشخیص شباهتهای بین کلمات است.ارزیابیها نشان دادند که نتایج حاصل از گراف وابستگی نسبت به روشهای مقایسه مستقیم گرافها نتایج بهتری دارند. استفاده از فاصله اصلاح گراف برای مقایسه دو گراف منجر به بهبود نتایج گراف وابستگی میشود و کارایی آن را بالا میبرد. کلیدواژه: فاصله اصلاح گراف، پردازش زبان طبیعی، گرافهای وابستگی، تشخیص پلاگاریسمفهرست مطالبمقدمه21-1 توضیح مسئله51-2 راه حلها61-3 مشکلات موجود در پیادهسازی الگوریتم61-4 ساختار پایاننامه7پیشینهی تحقیق92-1 تشخیص پلاگاریسم92-2 ابعاد تشخیص پلاگاریسم122-2-1 روش مبتنی بر گرامر122-2-2 روشهای مبتنی بر معنا132-2-3 روشهای ترکیبی142-2-4 روش تشخیص پلاگاریسم خارجی142-3 روشهای محاسبه میزان شباهت گرافها152-3-1 روش بزرگترین زیرگراف مشترک - کوچکترین سوپرگراف مشترک152-3-2 روش مبتنی بر جستجوی فضای حالت172-3-3 روشهای احتمالی183-1 تشخیص پلاگاریسم233-1-1 تطبیق n گرام233-1-2 وزندهی عبارت233-1-3 تعمیم عبارت243-2 گرافهای وابستگی253-2-1 وابستگیها263-3 فاصله ویرایش گراف263-3-1 عملیات ویرایش263-3-2 مسئلهی انتساب273-3-3 ماتریس هزینه283-3-4 الگوریتمهای انتساب294-1 معماری324-2 پیشپردازش متن324-2-1 پیدا کردن جملات334-2-2 ریشهیابی کلمات344-2-3 تشکیل گراف وابستگی404-3 استخراج کاندیدا444-3-1 شاخصگذاری جمله454-3-2 استخراج جملات کاندیدا454-4 تحلیل جزئیات454-4-1 الگوریتم فاصله ویرایش دو گراف484-4-2 تشخیص پلاگاریسم مبتنی بر GEDارائه شده در این پروژه495-1 تشخیص پلاگاریسم جابجایی کلمات و تغییر ساختار جملات555-1-1 تغییرات ساختاری 10 درصدی565-1-2 تغییرات ساختاری 50 درصدی575-2-2 تغییرات ساختاری 100 درصدی595-2 تشخیص پلاگاریسم معنایی605-2-1 تغییرات معنایی 10 درصدی60نتیجه گیری و پیشنهادات64مراجع67 جدول 4 - 1 : ساخت‌های زمان حال و امر [26]39جدول 4 - 2 : ساخت‌های زمان گذشته و مستقبل [26]39جدول 4 - 3 : عملیات ویرایش برای تبدیل جمله 1 به جمله 247 شکل 1- 1 : توپ توسط پسری به خارج از استادیوم شوت شد4شکل 1- 2 : بازیکن توپ را به خارج از زمین شوت کرد4شکل 3- 1 : مثال عملیات ویرایش برای دو گراف27شکل 3- 2 : مسئله انتساب28شکل 4-1 : مروری بر ماژولهای اصلی سیستم32شکل 4-2 : فاز پیشپردازش متن33شکل 4-3 : پیدا کردن جملات در متن34شکل 4-4 : نمایش نودها در جملات و استخراج مفاهیم از جملات و وزن بین نودها که میزان شباهت بین جملات را مشخص میکند. T1، T2، ...، Tn نشان دهندهی عبارات است [11].42شکل 4- 5 : ساختار نود شاخص برای مفاهیم جمله در گراف[11]44شکل 4- 6 : فاز بازیابی کاندیدا44شکل 4- 7 : فاز تحلیل جزئیات45شکل 4- 8 : گرافهای وابستگی برای جملات 1 و 246شکل 4- 9 : دو گراف همریخت48شکل 4- 10 : الگوریتم بررسی شباهت دو جملهای که تشخیص داده شده است که ممکن است شبیه یکدیگر باشند50شکل 5- 1 : مقایسه دو متن توسط الگوریتم اولیه54شکل 5- 2 : مقایسه دو متن توسط الگوریتم بهبودیافته55شکل 5- 3 : نمودار مقایسه تغییرات ساختاری 10 درصدی متون56شکل 5- 4 : میانگین خروجی نرم افزار برای ساختاری 10 درصد57شکل 5- 5 : نمودار مقایسه تغییرات ساختاری 20 درصدی متون58شکل 5- 6 : میانگین خروجی نرم افزار برای ساختاری 20 درصد58شکل 5- 7 : نمودار مقایسه تغییرات معنایی 100 درصد59شکل 5- 8 : میانگین خروجی نرم افزار برای جابجایی 100 درصد60شکل 5- 9 : نمودار مقایسه تغییرات معنایی 10 درصد61شکل 5- 10 : میانگین خروجی نرم افزار برای معنایی 10 درصد61 فصل اولمقدمهبرخی افراد ممکن است خواسته یا ناخواسته از کارهای محققان استفاده کنند در حالیکه حتی نامی از نویسندهی اصلی اثر ذکر نکرده باشند، این عمل پلاگاریسم نامیده میشود. پلاگاریسم عمل عمدی یا غیرعمدی کپی کردن یا استفاده از ایدهها و کارهای دیگران است بدون آنکه اطلاعاتی درباره منبع اصلی ذکر شده باشد. بر اساس بررسیهای صورت گرفته بر روی موضوع پلاگاریسم و تعداد مقالات بیشمار مندرج در وب و انعکاس نگرانی از وقوع آن مشخص است که اکثر مراکز آموزشی و پژوهشی در صفحات الکترونیکی خود در اقصی نقاط جهان چه در کشورهای در حال رشد آسیا و افریقا، تحت تاثیر ناشران با سابقه مجلات پژوهشی و نیز حفظ حیثیت علمی مراکز خود به معرفی همه جانبه این پدیده ضد اخلاقی و ضد اجتماعی به عنوان یک جرم مبادرت کردهاند. پلاگاریسم یک مشکلی در انجمن علمی است و به سرعت در حال رشد است، بدلیل آنکه داده و اطلاعات از بین اسناد الکترونیکی و اینترنت سریع و آسان از طریق کپی و درج از آن منابع بدست میآید. این مشکل زمانی رخ میدهد که محتوای اسناد غیرقانونی و بدون اجازه و بدون نقل قول پیدا شود که این مشکل به عنوان پلاگاریسم شناخته شده است و پلاگاریسم می تواند شامل طیف وسیعی از دستبردهای آگاهانه تا کپی کردن اتفاقی مطالب دیگران باشد. هدف اصلی این پایاننامه بیان روش مبتنی بر گراف برای ارائه متن و استفاده از آن در تشخیص پلاگاریسم است. بخشهایی که در ادامه این فصل میآیند دلایل استفاده از این روش را بیان نموده و به شرح مسئلهی تشخیص پلاگاریسم میپردازند. به علاوه یک راه حل برای این مسئله ارائه میدهند. در نهایت ساختار پایان نامه معرفی و مطالبی که در فصلهای بعدی به آنها پرداخته خواهد شد، مرور خواهند شد.مسئلهی پیدا کردن شباهت بین دو متن، یک مسئله معمول در زمینهی پردازش زبانهای طبیعی است. به منظور ارزیابی شباهتها بین دو متن، هر متن نیاز به روشی برای ارائه دارد. یک روش متن ساده است، که در آن یک لیست از کلمات، یک جمله را شکل میدهند. متنِ ساده معمولا به دلیل سادگی مورد استفاده قرار میگیرد، اما فاقد اطلاعات واضح راجع به ساختار گرامری است.بعضی از جنبههای زبان با استفاده از روشهای ارائهی ساختاری از قبیل گرافهای وابستگی که شامل کلمات متصل به هم است، بهتر ارائه میشوند.گرافهای وابستگی ساختار گرامری یک جمله را استخراج نموده، و به گسترهی همان جمله محدود میشوند. یکی از مزایای اصلی ارائهی مبتنی بر گراف این است که گرافهای وابستگی در بیشتر موارد حساس به ترتیب کلمات نیستند. این مزیت باعث میشود که شباهت بین جملاتی که ترتیب کلمات در آنها به هم ریخته شده است، پیدا شود.یک ارائهی قویتر پایههای بهتری را برای مشخص کردن شباهتها در وضعیتهای پیچیده فراهم میکند. دو جملهی ارائه شده در گراف وابستگی شکلهای 1-1 و 1-2 را در نظر بگیرید. انسان باید بتواند مشخص کند که این جملات دارای معانی یکسانی هستند. با این حال، تشخیص اتوماتیک شباهت این دو جمله به دلیل جایگزینی کلمات دچار مشکل خواهد شد. اگر از ارائه متن ساده استفاده شود، تنها کلمات مشترک "به"، "خارج"، "از"، "شوت" و "توپ" خواهند بود. کلمهی "شوت" و "توپ" تنها کلماتی هستند که منظور جمله را میرسانند. با دقت در گرافهای وابستگی، واضح است که شباهت ساختاری بین جملات وجود دارد.شکل 1- 1 : توپ توسط پسری به خارج از استادیوم شوت شدشکل 1- 2 : بازیکن توپ را به خارج از زمین شوت کردبا افزایش میزان دسترسی به متون موجود در وب، پلاگاریسم ساده و سادهتر شده است. میزان زیادی از متون پلاگاریسم در زمینهی درسی و تحصیلی سال به سال افزایش پیدا میکنند. در نتیجه، نیاز شدیدی به تشخیص خودکار پلاگاریسم احساس میشود. 1-1 توضیح مسئلهمهمترین بخش این پایاننامه پیادهسازی یک الگوریتم برای محاسبه فاصلهی اصلاح گراف است، که شباهت بین دو گراف را محاسبه میکند. الگوریتم مبتنی بر محاسبهی تعداد عملیات ویرایشی مورد نیاز برای تبدیل یک گراف به گراف دیگر است[1]. هر عمل ویرایش یک هزینهی ویرایش دارد، که مشخص میکند یک عمل چقدر هزینه میبرد.تشخیص پلاگاریسم اتوماتیک یک زمینهی تحقیقاتی است که در اصل روی شباهت متنی بنا شده است. مسئلهی بکارگیری شباهت متن مبتنی بر گراف برای تشخیص پلاگاریسم در سوال تحقیقی 1 بیان شده است.سوال تحقیقی 1 : آیا شباهت مبتنی بر گراف، در یک فاصله اصلاح گراف مشخص، در تشخیص پلاگاریسم قابل بکارگیری و از لحاظ محاسباتی امکانپذیر هست؟سیستمهای تشخیص پلاگاریسم آزمایشی اغلب مبتنی بر ارائههای سادهتر متن، از قبیل تطبیق nگرام و مدل فضای بردار هستند [2 و 3]. در نتیجه، روش میتواند نسبتا منحصر به فرد باشد. به دلیل منحصر بودن روش، بعضی از جزئیات پیادهسازی تعریف شده نیستند. سوال تحقیقاتی 2 مسئلهای را بیان میکند که جزئیات الگوریتم را مشخص مینماید.سوال تحقیقی 2 : بهترین روش برای محاسبهی فاصله ویرایش گراف بین جملات، به ویژه از لحاظ هزینهی ویرایش و ارائه گراف در زمینه تشخیص پلاگاریسم چیست ؟به منظور ارزیابی کارایی الگوریتم محاسبه فاصلهی ویرایش گراف، کارایی آن در مقایسه با سیستمهای آزمایشی موجود مقایسه میشود. سوال تحقیقی 3 مسئلهی مقایسهی الگوریتم با روشهای موجود را مطرح میکند.سوال تحقیقی 3 : شباهت مبتنی بر گراف با سایر روشها در تشخیص پلاگاریسم، از قبیل بازیابی مبتنی بر اندیس و تطبیق nگرام، چگونه مقایسه میشود؟