17420

17420

ارائه روشي جديد در تشخيص اسناد تقريبا تكراري

كارشناسي ارشد

نرم‌افزار

آبان ماه 1392

دكتر حسن نادري

كامپيوتر

چكيده با گسترش استفاده از سايت‌هايي نظير سايت‌هاي خبري، وبلاگ‌ها، شبكه‌هاي اجتماعي و سيستم‌هاي پرسش و پاسخ، توليد محتوا در وب روز به روز رو به افزايش است. محتواي توليد شده در بسياري از اين سايت‌ها، بسيار شبيه به هم مي‌باشد كه منجر به توليد صفحات تقريبا تكراري در اينترنت شده است. وجود اين گونه صفحات منجر به وجود اطلاعات تقريبا تكراري در نتايج موتورهاي جستجو شده است كه كارايي اين سيستم‌ها را كاهش مي‌دهد. در نتيجه نياز به روشي كه بتواند اسناد تقريبا تكراري را شناسايي نمايد ضروري به نظر مي‌رسد. مساله‌ي مطرح آن است كه شناسايي اسناد تقريبا تكراري از بين حجم بسيار زياد اسناد وب وقت‌گير و هزينه‌بر مي‌باشد. هدف از اين پروژه ارائه‌ي روشي است كه بتواند با دقت و سرعت بالا اسناد تقريبا تكراري را شناسايي نمايد. روش پيشنهادي بر مبناي دو تابع مشابهت عمل مي‌نمايد: تابع مشابهت كم‌هزينه و پرهزينه. بر اساس معيار مشابهت كم‌هزينه، ابتدا اسناد به گروه‌هايي تقسيم‌بندي مي‌شوند به طوري كه احتمال آن‌كه اسناد متعلق به گروه‌هاي متفاوت تقريبا تكراري يكديگر باشند، بسيار كم باشد. از آنجا كه براي بخش‌بندي از تابع مشابهت كم‌هزينه استفاده مي‌شود، حجم بسيار زياد اسناد با سرعت بالايي به بخش‌هاي كوچكي تقسيم‌بندي مي‌شود. سپس معيار مشابهت پرهزينه بر روي اسناد هر بخش به طور مجزا اعمال مي‌گردد. از آنجا كه تعداد اسناد قرار گرفته در هر بخش كم مي‌باشد، لذا شناسايي اسناد تقريبا تكراري در هر بخش نيز با سرعت بالايي انجام خواهد پذيرفت. كلماتي كه تنها در يك سند ظاهر شده‌اند (كلمات يكتا) و همچنين كلماتي كه در تعداد كمي از اسناد رخ داده‌اند (كلمات كم‌تكرار) به ترتيب به عنوان معيار مشابهت كم‌هزينه و پرهزينه مورد استفاده قرار گرفته‌اند. اين ايده كاملا متضاد با رهيافت‌هاي پيشين مي‌باشد. در روش‌هاي پيشين از كلماتي كه در درصد قابل توجهي از اسناد ظاهر شده‌اند به عنوان معيار مشابهت استفاده شده است. نتايج حاصل از ارزيابي روش پيشنهادي بر روي دو مجموعه داده نشان داد كه كلمات كم‏تكرار در يك سند خصوصيت‌هاي خوبي از سند براي تشخيص محتواي آن مي‌باشند. اين كلمات مي‌توانند با دقت بالايي اسناد با شباهت بالاي محتوايي را تشخيص دهند. از طرفي از آنجا كه تعداد كلمات كم‏تكرار نسبت به كلمات پرتكرار كمتر مي‌باشند، ميزان حافظه‌ي مورد نياز روش پيشنهادي به منظور نگهداري اطلاعات اين كلمات كم مي‌باشد. اين نتايج همچنين نشان داد كه استفاده از ايده‌ي بخش‌بندي اسناد به طور قابل ملاحظه‌اي سرعت روش پيشنهادي را بدون كاهش دقت افزايش مي‌دهد. واژه‌هاي كليدي: اسناد تقريباً تكراري، كم‌تكرار، يكتا، معيار مشابهت كم‌هزينه و پرهزينه، بخش‌بندي

1396/03/20

1/1/1900 12:00:00 AM

Abstract With the widespread use of news websites, blogs, social networks and question-answering systems, web-based content generation is increasing. Generated contents of these websites are very similar which is the reason of why near duplicated pages have been existed on the Internet. The appearance of such near duplicated pages in the results of search engines has reduced the efficiency of these systems. Therefore, it is necessary to have a mechanism that can detect near duplicated documents. Identifying near duplicates from the massive number of documents is a time-consume and expensive task. The goal of this thesis is to propose a method that can detect near duplicated documents rapidly and accurately. The proposed method operates based on two similarity functions: low-cost and expensive. Initially, based on the low-cost function, documents are partitioned into groups such that the probability that documents of different groups are being near duplicates will be very low. Since the low-cost similarity measure is used, the massive number of documents is partitioned to small parts quickly. Then, the expensive similarity measure is applied to documents of each part separately. Because of the small size of each partition, identification of near duplicated documents in each part is performed rapidly, too. We use words which have appeared only in one document (unique words) and have occurred in small number of documents (less-frequent words) as low-cost and expensive similarity measures respectively. This idea is in contrast with previous methods that were used frequent-words as their similarity measures. Evaluation of the proposed method over two datasets showed that less-frequent words are rich features of a document for detection of near duplicates. In addition, since the frequency of these words in the corpus is lesser than frequent words; the amount of memory that is required is very low. The results also showed that the document partitioning function can significantly increase speed of the proposed method without degrading of the accuracy. Keywords: near duplicated documents, less-frequent, unique, low-cost and expensive similarity measure, partitioning