برخی انواع تجزیه واژگان
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 63315
- تاریخ دفاع
- ۱۹ بهمن ۱۳۹۲
- دانشجو
- پگاه مرادی حامد
- استاد راهنما
- مرتضی محمدنوری
- چکیده
- ترکیبیات واژگان شاخهای از علوم ریاضی است که در آن با بکارگیری روشهای ترکیبیاتی به حل برخی مسائل مطرح در خصوص واژهها پرداخته میشود. در این میان تجزیه واژگان یکی از مسائل مهمی است که در شاخه ترکیبیات واژگان مورد توجه واقع شده است. در ترکیبیات واژگان، واژه به دنبالهای متناهی یا نامتناهی روی یک مجموعه متناهی موسوم به الفبا اطلاق میگردد و فاکتور یک واژه به معنای یک زیردنباله بهم پیوسته از آن میباشد. هدف در تجزیه واژگان، شکستن یک واژه به فاکتورهای تشکیل دهنده آن براساس یک الگوریتم خاص است. برخی کاربردهای تجزیه واژگان عبارتند از فشردهسازی، یافتن زیرواژههای مربع یک واژه و یافتن تکرارهای مختلف یک زیرواژه. تاکنون روشهای مهمی در زمینه تجزیه واژگان از قبیل تجزیههای لمپل-زیو، کروشمور، لیندن، وینوت، گرامرمبنا و تعمیمیافته مطرح شده اند که این روشها در این پایاننامه معرفی و مطالعه شدهاند. همچنین نتیجه اعمال برخی از این روشها بر روی برخی واژههای مطرح در زمینه ترکیبیات واژگان، از قبیل واژههای فیبوناچی، تو-مورس و اشتورمی ارائه شده است. بهعلاوه خواص و ویژگیهای منحصربفرد روشهای ذکر شده مورد بررسی قرار گرفتهاست. از آنجاکه این روشها ماهیتاً بر پایههای متفاوتی بنا شدهاند، لذا مقایسه هر دو روش تجزیه دلخواه الزاماً امکانپذیر نمیباشد بنابراین در انتها به مقایسه و جمعبندی روشهای همسو با یکدیگر پرداخته شده است. واژههای کلیدی: تجزیه واژه، فاکتور، لمپل-زیو، کروشمور، لیندن، وینوت، گرامرمبنا، تعمیمیافته
- Abstract
- Combinatorics of words is a branch of mathematics in which Combinatorial methods are utilized to tackle some words related issues. Factorization of Words is an important subject in combinatorics of words. Objective of word factorization is to extract different factors of words based on a specific algorithm. Main application of factorization of words is data compression, in a way that by extracting all factors of a word and their repetitions, the word can be compressed. By now, important methods in factorization of words such as Lempel-Ziv, Crochemore, Lyndon, Viennot, Grammar-based, and Generalized factorization are introduced that are investigated in this dissertation. Results of applying these methods on some words discussed in combinatorics of words including Fibonacci, Thue-Morse, and Sturmian words are presented. In addition, unique properties and characteristics of these methods are studied. Since some of the methods are fundamentally different, comparison among all of them is not possible. Consequently, related methods care compared separately. keywords: factorization of word, Lempel-Ziv, Crochemore, Lyndon, Viennot, Grammar-based, Generalized factorization