Document

Combined syntactical structures and sequence alignment approach to document similarity calculation for copy detection

Publisher
Sultan Qaboos University
Gregorian
2008
Language
English
English abstract
Abstract Calculating similarities between text documents has always received special interest as it has been utilized in many fields such as copy detection, plagiarism detection, and information retrieval etc. This problem has drawn the attention of researchers in a wide range of areas and applications. This project looks at this problem through a new approach. This approach combines the use of a given text's structure, namely Part-Of-Speech (POS), and sequence aligning techniques, such as Longest Common Subsequence (LCS), to analyze and calculate similarity between text documents. It proposes creating better representations based on the syntactic structure of written text that preserves some of the semantics expressed as order and style. A prototype of the proposed approach has been implemented to investigate the idea's potential, applicability and utility. Experiments have been conducted to validate this approach using different sets of data from different domains. The text's structures (POS) were used as a representation for the calculation of similarities between related documents. Clustering methods and sequence alignment techniques, such as the Longest Common Subsequence (LCS) algorithm, were used to cluster together and rank documents according to their similarity measure. Similarity between two documents was measured by computing a normalized score of the length of their Longest Common Subsequence (LCS). The effect of the Part-Of-Speech (POS) tags-set size on the accuracy of the obtained results is investigated. Also experiments were conducted to find a real-life application for this approach in detecting duplicate and near-duplicate documents within a corpus, and in filtering search engine results. Experiments have shown the utility of the approach in finding similarities between written documents, demonstrating the capability of this approach in capturing duplicate and near-duplicate documents and the ability to group similar documents. An important contribution of this work was the development of two extensions for the Longest Common Subsequence (LCS) algorithm. These two extensions have improved the original LCS's efficiency. Experiments demonstrating these improvements in the LCS have been performed and the results have been discussed.
Arabic abstract
الخلاصة
حازت قضية إيجاد وحساب أوجه التشابه بين الوثائق النصية على اهتمام خاص ومتزايد في كثير من المجالات، مثل كشف وحماية النسخ، وكشف السرقات الأدبية والعمل على حمايتها، وإدارة وتحليل الملفات، تصفية وتنقيح نتائج محركات البحث وغيرها، كما أنها لفتت انتباه أعداد كبيرة من الباحثين في مجالات مختلفة لما لها من تطبيقات متعددة.
يطمح هذا المشروع إلى استخدام نهج جديد يجمع في عمله بين استخدام بنية النص و تراكيب الجمل في النصوص والمعروفة بأجزاء الكلام. مع بعض تقنيات موافقة و مماثلة السلاسل النصية، كإيجاد السلسلة الثانوية الأطول، لتحليل وحساب التشابه بين الوثائق النصية؛ حيث يهدف هذا النهج إلى تمثيل أفضل للوثائق النصية، ويعمل هذا التمثيل على المحافظة على بعض معاني الكلمات والمتبدي في المحافظة على الترتيب والنمط لتراكيب هذه النصوص.
يعد النموذج الأولي، والذي تم بناءه في هذا المشروع، تطبيقا لهذا النهج المقترح، بغرض تقصي إمكانية تحقيق هذه الفكرة المقترحة، ودراسة جدوى وفائدة تطبيقها. ومن أجل ذلك، تم إعداد وإجراء عددا من التجارب المصادقة على فعالية هذا النهج. حيث استعمل في هذه التجارب مجموعات متنوعة من البيانات ومن مجالات مختلفة؛ حيث تم استخدام بنياتها النصية و تراكيب جملها لحساب التشابه فيما بينها باستخدام تقنية موافقة و مماثلة السلاسل النصية، وبالأخص إيجاد السلسلة الثانوية الأطول. وتجدر الإشارة إلى أن عملية قياس التشابه بين الوثائق المقارنة قد تمت على أساس حساب وتبسيط حجم أطول سلسلة ثانوية مشتركة بينها. هدف هذا المشروع إلى تقصي تأثير اختلاف أحجام المجموعات المكونة لعلامات أجزاء الكلام والمستخدمة في تكوين السلاسل الممثلة الوثائق النصية على دقة النتائج المرجوة من هذا النظام. كما أنه قام بدراسة جدوى تطبيق هذا النهج في كشف النصوص المكررة وشبه المكررة بين مجموعة من الوثائق، وتصفية وتنقيح نتائج محرك البحث. أظهرت نتائج التجارب جدوى تطبيق هذا النهج في إيجاد وحساب التشابه بين الوثائق الكتابية، كما أنها أوضحت أن أسلوب كاتب النص يمكن اكتشافه باستخدام مجموعة صغيرة من العلامات المميزة الأجزاء الكلام. إضافة إلى ذلك، أثبتت هذه التجارب قدرة هذا النهج على إيجاد النصوص المكررة وشبه المكررة بين الوثائق، و قدرته على تجميع الوثائق المتشابهة على أساس حساب معيار التشابه بينها. وعلاوة على ذلك، بينت النتائج بديهية استخدام هذا النهج في تصفية نتائج محركات البحث. أخيرا، فإن لهذا المشروع مساهمة فاعلة، والمتمثلة في تطوير نسختين معدلتين لتقنية إيجاد السلسلة الثانوية المشتركة الأطول، حيث أثبتتا هاتين النسختين دقتهما وأدائهما الأفضل. كما أنه أبرز حقيقة أن هذا النهج ذا قيمة وجدوى مرجوة من حيث الدقة في المقارنة بين الوثائق النصية.
Category
Theses and Dissertations

Same Subject

Journal articles
0
0
Shvartz, Vladimir A.
Oman Medical Specialty Board.
2016-01
Theses and Dissertations
1
0
Al-Sedairy, Hamad Abdullah Ali.
Sultan Qaboos University
2004
Theses and Dissertations
0
0
Al-Badi, Mohamed Abdullah.
Sultan Qaboos University
2004
Theses and Dissertations
0
0
, .Raiya AmerAl-Hinayah
Sultan Qaboos University
2003
Journal articles
0
0
Kakaria, Anupam.
College of Medicine, Sultan Qaboos University.
2009-12