تطبيق رشته اي براي شناسايي ساختاري الگو

توضیحات

تطبيق رشته اي براي شناسايي ساختاري الگو
چكيده ..........1
مقدمه .................................................................................... 2
فصل اول : كليات
1-1 ) هدف ............................................................... 6
2-1 ) پيشينه تطبيق رشته .............................................. 6
3-1 ) روش كار و تحقيق .............................................. 7
فصل دوم : فاصله ويرايشي رشته و تطبيق گراف
1-2 ) تبديل گراف به رشته ....................................... 10
2-2 ) تطبيق گراف ........................................................ 10
3-2 ) فاصله ويرايشي رشته ........................................... 13
4-2 ) جمع بندي .................................................................. 15
فصل سوم : تقريب سريع تطبيق رشته
1-3 ) تطبيق رشته اي تقريبي ........................................ 18
2-3 ) اصول كلي كار ............................................... 19
1-2-3 ) فهرست براي تطابق رشت هاي تقريبي ................................ 20
2-2-3 ) جستجوي آنلاين .............................................................. 22
3-2-3 ) جستجو در فواصل انداز هاي كلي .................................. 23
3-3 ) لغت به عنوان يك فاصله اندازه اي ..................................................... 26
4-3 ) جمع بندي .................................................................. 28
فصل چهارم : تطبيق رشته اي براي تشخيص ساختاري الگو
1-4 ) الگوريتم ابتدايي ............................................................... 31
2-4 ) مفاهيم تشخيص الگو بر اساس فاصله هاي رشته اي ................. 40
فصل پنجم : الگوريتم بهينه شده براي تطبيق رشته اي
1-5 ) اصلاحاتي در الگوريتم پايه ................................................. 46
1-1-5 ) يك روش ساده شده ............................................. 46
2-1-5 ) شباهت جمل هها در زير دنباله هاي مشترك ........................ 47
3-1-5 ) مطابقت دهي كشساني و درهم پيچشي ............................ 48
4-1-5 ) فاصله رشته بر اساس جايگزين يهاي تعميم يافته ................................ 50
5-1-5 ) هزين ههاي وابسته به متن .............................................. 54
6-1-5 ) يك روش سريعتر ................................................... 57
2-5 ) تطبيق رشته هاي خاص ................................................ 58
فصل ششم : نتيجه گيري و پيشنهادات
1-6 ) نتيجه گيري ........................................................................... 62
2-6 ) پيشنهادات ..................................................................... 62
فصل هفتم : منابع و ماخذ
65 ............................................... REFRENCES (1-7
2-7 ) آدرس چند سايت و مقاله مرتبط .......................................... 66
1-2-7 ) آدرس چند سايت مرتبط ................................................ 66
2-2-7 ) آدرس چند مقاله مرتبط ............................................. 66
68 ........................................................................ ABSTRACT
چكيده :
روشهاي تشخيص الگو بصورت آماري ، نحوي و ساختاري مطرح م يشوند. در روشهاي ساختاري تشخيص الگو ، از يك مجموعه نمادهاي اوليه (سمبول ها) براي شناسايي الگوها استفاده مي شود. كه اين سمبول ها ، خود نيز از الگوها استخراج مي شوند. پس از آن مجموعه نمادهاي اوليه با رشته مورد نظر مقايسه شده و فاصله ويرايشي بين آنها بدست مي آيد ، آنگاه سمبولي كه كمترين فاصله را با الگوي اصلي داشته باشد برنده اين تطبيق است. ساختارهاي داده اي كه براي تشخيص ساختاري الگو مورد استفاده قرار مي گيرند ، رشته ها ، درختها و گرافها را شامل م يشوند. كاربردهاي تشخيص الگوي ساختاري در شناسائي ش ئهاي دو بعدي ، سه بعدي ، كاراكترها ، تشخيص گفتار ، شناسايي
لغات مشابه در بانك اطلاعاتي لغت نامه و شناخت اجزاي ماشين مطرح مي شود
مقدمه :
اين مطلب يك ايده متعارف براي تعداد متفاوتي از روشهايي است كه جهت تشخيص الگو بكار مي روند و اهميت ندارد كه آن الگوها آماري ، تركيبي يا ساختاري باشند. اين يك مقايسه از الگويي ناشناخته با يك عدد بطور نمونه يا با نمونه الگوي اوليه با استفاده از فاصله يا ( ميزان ) شباهت يا تفاوت است. يعني هر الگوي ناشناخته را بصورت نمونه با يك رشته عددي تقريب زده و آن رشته را با رشته عددي الگوي اوليه مقايسه مي كنيم. ابتدا ارائه يك عدد از نمونه هاي اوليه كه به كلاس مربوط به آن نمون ههاي اوليه شناخته شده مرتبط است ، و سپس دسته بندي يك الگوي ناشناخته بوسيله تعيين كردن بيشترين شباهت الگوي تصميم گيري براي آن كلاس است كه دست يافتني است. پس براي هر
نمونه اوليه يك عدد در نظر م يگيريم كه آن عدد با كلاسهاي اين نمونه هاي شناخته شده در ارتباط است و دسته بندي الگوهاي ناشناخته بوسيله تعيين كردن بيشترين شباهت الگو و تصميم گيري درباره كلاس آن حاصل مي شود. در دسته بندي آماري ، نمونه ها به وسيله عامل مشترك از يك تابع تصميم گيري ارزيابي شده اند. پارامترها از يك احتمال توزيع شده نقاط ، در يك فضاي ويژگي تعريف شده ، و مفهوم شباهت بعدي از اعداد حقيقي كار n نيز بر اساس فاصله تعريف شده است. و توابع تصميم گيري در فضاي مي كنند. اگر ساختار الگو لازم باشد ، گرامرهاي رسمي (قراردادي) يك مفهوم مفيد هستند. تابع متداول بصورت دستي يا بصورت اتوماتيك يك گرامر از يك بسته نمونه را نتيجه مي دهد. بنابراين يك الگوي ورودي ناشناخته به يك تجزيه كننده تحويل داده شده و مطابق با اين گرامر تحليل مي شود. در اين روش نه فقط يك دسته بندي ، بلكه همچنين يك شرح ساختاري از الگوي ناشناخته مي توان فراهم كرد. تحليل گر نحوي م يتواند مانند يك تابع ويژه براي تصميم گيري شباهت ساختاري تفسير شود. مطابق ساختارهاي داد هاي متفاوت كه براي تشخيص الگو مورد استفاده قرار م يگيرند ، فقط رشته گرامرها بررسي نمي شود ، بلكه درخت ، گراف و آرايه گرامرها در يك قاعده مهم تشخيص الگو فعاليت
دارند.
اينها مواردي از تعدادي از مثالهاي آماده بسيار كوچك هستند كه كاربردشان براي نتيجه گيري دستوري است ، يا در جايي است كه تمام توان يك پيشروي دستوري نياز نيست. يعني كاربرد اين مثالهاي آماده بسيار كوچك براي استنتاجي بر اساس قواعد ، و يا استنتاجي در مكاني كه نيازي نيست از تمام توان قواعد استنتاجي استفاده كرد م يباشد. اگر ساختار الگو مورد نياز باشد ، با اين حال ، شايد تكنيك تطبيق ساختاري مفيد باشد.
ايده پايه اي تطبيق ساختاري ، به سوي بازنمايي مستقيم نمونه هاي اوليه است ، بخوبي الگوهاي ورودي ناشناخته ، كه بوسيله معاني يك ساختار داده مناسب و بسوي مقايسه اين ساختارها در ترتيبي براي يافتن شباهت نمونه اوليه با يك الگوي ناشناخته ورودي حركت مي كند. اين حركت به جلو نيازمند يك عدد قراردادي از شباهت بين دو ساختار ارائه شده است. تعدادي از برخي اعداد در برخي از نوشته ها پيشنهاد شده است. آنها مي توانند به گروه هاي بزرگي طبق ساختارهاي داد هاي تقسيم بشوند
كه براي تشخيص الگو استفاده شد هاند. بيشتر ساختارهاي داد هاي مهم ، رشته اي ، درختي ، گراف و آرايه اي هستند. وابستگي به دامنه مسائل خاص براي همه اين ساختارهاي داد هاي م يتواند بوسيله ويژگي هايشان افزايش يابد.
با يك محاسبه پيچيده ، رشت هها خيلي كارآمد هستند ، از آنجائيكه بررسي ميزان شباهت بين رشته ها مي تواند كاملا سريع انجام شود ، اگر چه رشته ها به تعداد نماي ششان محدود هستند. در موارد خيلي زياد گراف ها بيشترين قدرت رسيدن به بازنمايي الگوي ساختاري را دارند. اگر چه تطبيق گراف بطور مفهومي نسبتا پيچيده است ، و به نسبت قيمت محاسبات ، گران است. بنابراين يك تعادلي بين تعداد نمايه ها و تعداد تكرارهايمان براي تطبيق نياز است. اگر ما براي بازنمايي كلاس الگو از يك گرامر استفاده كنيم ، يك تعادل ساده رعايت مي شود.در اين بخش ما مهمترين راه رسيدن به تطبيق رشته را بررسي مي كنيم. از نقطه نظر نمايش ، تطبيق ساختاري ، مي تواند به عنوان يك مورد خاص نحوي ( تركيبي ) در حركت بر اساس گرامر مطرح بشود.