تطبیق الگو

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم کامپيوتر، تطبیق الگو چک کردن دنباله اي از نشانه ها به منظور حضور ترکيباتی از برخی الگو هاست. در مقایسه با شناسایی الگو، الگوی منطبق همیشه باید کاملا همان الگوی مقایسه شده باشد. الگوها عموماً به شکل رشته یا ساختار درخت هستند.کاربردهای تطبیق الگو شامل یافتن یک الگوی نشانه در یک توالی (در صورت وجود) و نمایش آن در خروجی، نمایش برخی از اجزای الگوی همسان در خروجی، و جایگزین کردن الگوی تطبیق با برخی رشته های دیگر است.(به عنوان مثال جست و جو و جایگزینی)

الگوهای رشته ای(مانند متنی از رشته ها)معمولاً با استفاده از regular expressions و تکنيک ها مانند عقب گرد تشريح ميشوند.

ساختار های درختی در برخی زبان های برنامه نويسی به عنوان يک ابزار کلی برای انجام فر آيند روی داده ها بر اساس ساخترشان، مانند ... استفاده شده اند و زبان سمبوليک رياضی به نام متمتيکا سينتکس مخصوص خود، برای نمايش الگو های درختی و ساختار زبانی برای اجرای شرطی و باز يابی ارزش بر اساس آن است.به منظور تامین سادگی و کارایی، این الگوهای درخت فاقد برخی از ویژگی هایی است که در عبارات منظم در دسترس هستند.

معمولاً ميتوان الگو های پيشنهادی که تک به تک امتحان شده، تا يک ساختار برنامه نویسی شرطی قوی را به دست دهد، پيشنهاد داده شود.

تاریخچه[ویرایش]

اولين برنامه های کامپيوتری که از تطبيق الگو استفاده کردند، ويراش گران متن هستند. در Ken Thompson ،Bell Labs برای پوشش regular expression ها ويژگی های جست و جو و جایگذاری در QED ها را گسترش دادند. زبان های برنامه نويسی اوليه با ساختار تطبيق الگو شامل SNOBOL در سال 1962، SASL در سال 1976، NPL در 1977، و KRC در 1981. زبان های برنامه نويسی اوليه که تطبيق الگو ی مبتنی بر درخت داشتند، گسترش LISP توسط Fred McBride، در سال 1970 هستند

الگوهای اولیه[ویرایش]

ساده ترين الگو در تطبيق الگو يک متغير يا مقدار صریح است. به عنوان مثال، يک تابع Haskell با سينتکس ساده را فرض کنيد( پارامتر های تابع در پرانتز نمی آيند، = به معنای مساوی نيست، بلکه به معنی تعريف است):

 f 0 = 1

در اينجا، 0 يک الگو ی تک مقداری است. اکنون، هروقت 0 به عنوان ورودی به f داده شود، الگو مطابقت ميکند و تابع 1 برميگرداند. با هر ورودی ديگری، تابع کار نمی کند. برای اینکه سينتکس الگو های پيشنهادی ديگر را در تعريف تابع پشتيبانی کند، ميتوانيم تعريف را به اين صورت گسترش دهيم:

 f n = n * f (n-1)

در اينجا، اولين n يک الگوی تک مقداری است، که قطعاً هر مقداری در آن صدق ميکند. در، الگوها به ترتيب امتحان ميشوند بنابراين اولين تعريف حتماً برای صفر صدق ميکند، همانطور که برای بقيه ورودی ها تابع به ازای هر ورودی، (n * f (n-1 را برميگردند. الگوی کلمات (معمولاً به شکل _ نوشته ميشوند)نیز ساده است: مانند نام متغير، که با هر مقداری تطبيق ميکند، اما هر مقداری را به هر اسمی اضافه نمی کند.

الگوهای درختی[ویرایش]

الگوهای پیچیده ی بیشتری می توانند از الگوهای اولیه ی بخش قبل ساخته شوند، معمولاً همانطور که مقادیر از ترکیب مقادیر دیگر بدست می آیند. تفاوت در اینجاست که برای کلمات و متغیرها، یک الگو به یک تک مقدار ساخته نمی شود، اما با گروهی از مقادیر که ترکیبی از المان های صریح اند و المان هایی که اجازه ی تمایز با ساختار الگو را دارند، مطابقت می کنند.

در Haskell، خطی که در ادامه آمده است یک نوع داده ی جبری را تعریف می کند Color که یک سازنده ی یکتای داده دارد ColorConstructor که یک رشته و یک عدد را پوشش می دهد.

 data Color = ColorConstructor Integer String

سازده راسی در درخت است و عدد و رشته برگ های روی شاخه ها هستند.

وقتی می خواهیم بنویسیم functions که یک abstract data type از Color بسازیم، می خواهیم تابع ها را در interface با نوع داده ها بنویسیمو، و بنابراین می خواهیم مقداری از نوع داده را از داده بیرون بکشیم، به عنوان مثال، فقط بخش عددی یا فقط بخش رشته ای از Color.

اگر یک متغیر را که از نوع color است را بدهیم، چگونه می توانیم داده را از این متغیر بیرون بکشیم؟ به عنوان مثالو برای یک تابع برای گرفتن قسمت عددی Color، می توانیم یک الگوی ساده ی درخت استفاده کنیم و بنویسیم:

 integerPart (ColorConstructor theInteger _) = theInteger

همین طور داریم:

 stringPart (ColorConstructor _ theString) = theString

ایجاد این تابع می تواند توسط سینتکس ضبط شده ی داده، اتوماتیک انجام شود.

فیلتر کردن داده ها با استفاده از الگوها[ویرایش]

تطبیق الگو در ریاضیات[ویرایش]

[ویرایش]

تطبیق الگو و رشته ها[ویرایش]

منابع[ویرایش]

مشارکت‌کنندگان ویکی‌پدیا، «pattern matching»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد.