சுருங்குறித் தொடர்

கணினியியலில், சுருங்குறித் தொடர்கள் என்பவை, குறிப்பிட்ட எழுத்துக்குறிகள், சொற்கள் அல்லது எழுத்துக்குறித் தொகுதிகள் போன்ற உரை சர அம்சங்களை அடையாளங்காண்பதற்கான நெகிழ்தன்மையுள்ள மற்றும் துல்லியமான வசதியை வழங்குகின்றன. ஒரு சுருங்குறித் தொடர் (அவ்வப்போது ஆங்கிலத்தில் regex அல்லது regexp என்றும் சுருக்கமாகக் குறிப்பிடப்படுகிறது) முறைசார் மொழிகளில் எழுதப்படுகிறது, அம்மொழியானது ஒரு பாகுபடுத்தி உருவாக்கியாகச் செயல்படக்கூடிய அல்லது உரையை ஆய்வு செய்து கொடுக்கப்பட்ட குறிப்புவிவரத்திற்குப் பொருந்தக்கூடிய பகுதிகளைக் கண்டறியக்கூடிய நிரலான சுருங்குறித் தொடர் செயலாக்கியின் மூலம் புரிந்துகொள்ளப்படுகிறது.

பின்வரும் எடுத்துக்காட்டுகள் சுருங்குறித் தொடர் மூலம் குறிப்பிடப்படக்கூடிய சில குறிப்புவிவரங்களை விளக்குகின்றன:

"car", "cartoon" அல்லது "bicarbonate" போன்ற எந்த சூழலிலும் இடம்பெறும் "car" என்ற தொடர்
தனியான சொல்லாக இடம்பெறும் போது "car" என்ற இந்தச் சொல்
"blue" அல்லது "red" என்ற சொல் "car" என்ற சொல்லுக்கு முன்பாக வரும்போது
ஒன்று அல்லது மேற்பட்ட எண்களைத் தொடர்ந்து ஒரு டாலர் குறி, மேலும் அதனைத் தொடர்ந்து ஒரு புள்ளி இருக்க வாய்ப்புள்ளது, ஆனால் அப்புள்ளியைத் தொடர்ந்து இரண்டு எண்கள் கண்டிப்பாக இருக்கும்

சுருங்குறித் தொடர்கள் இந்த எடுத்துக்காட்டுகளைவிடவும் மிகவும் சிக்கலானவையாக இருக்கலாம்.

பல உரைத் திருத்திகள், பயன்பாடுகள் மற்றும் நிரலாக்க மொழிகள் ஆகியவற்றால் வகைகளைப் பொறுத்து உரையைக் கையாண்டு நிர்வகிக்க சுருங்குறித் தொடர்கள் பயன்படுத்தப்படுகின்றன. எடுத்துக்காட்டுக்கு மற்றும்Perl Ruby Tcl போன்ற நிரலாக்க மொழிகள் அவற்றின் தொடரியலுக்குளேயே அமைக்கப்பட்ட மிக ஆற்றல் மிக்க சுருங்குறித் தொடர் பொறிகளைக் கொண்டுள்ளன. Unix விநியோகங்களால் வழங்கப்படும் ed மற்றும் க்ரெப் வடிகட்டி உள்ளிட்ட பல பயன்பாடுகள் சுருங்குறித் தொடர்கள் எனும் கருத்தைப் பிரபலமாக்கின.

தொடரியலின் எடுத்துக்காட்டாக, \bex எனும் சுருங்குறித் தொடர், (\b மூலமாகக் குறிப்பிடப்படும்) "சொல் எல்லைகளுக்கு" அடுத்து வரும் "ex " எனும் சரத்தின் அனைத்து நேர்வுகளையும் தேடப் பயன்படுத்தப்படுகிறது. வல்லுநர்களின் கூற்றுப்படி, \bex எனும் சுருங்குறித் தொடரானது, பொருந்தும் "ex" சரத்தை சாத்தியமுள்ள இரண்டு இடங்களில் கண்டறியும் அவை, (1) சொற்களின் தொடக்கத்தில் மற்றும் (2) ஒரு சரத்தின் இரண்டு எழுத்துக்குறிகளுக்கு இடையில். இதில் ஒன்று சொல் எழுத்துக்குறி மற்றொன்று சொல் எழுத்துக்குறி அல்ல. இவ்வாறு, "Texts for experts," எனும் சரத்தில் \bex தொடரானது, "experts" எனும் சொல்லிலுள்ள "ex " ஐப் பொருத்தும், ஆனால் "Texts" இல் உள்ளதைப் பொருத்தாது, (ஏனெனில் இதில் "ex " ஒரு சொல்லுக்குள் வருகிறது, மேலும் ஒரு சொல் எல்லைக்கு அடுத்து உடனடியாக வரவில்லை).

பல நவீன கணினியியல் அமைப்புகள், ஒரு கோப்பமைப்பில் இருந்து கோப்புப்பெயர்களைப் பொருத்துவதற்கென வைல்ட் கார்டு எழுத்துக்குறிகளை வழங்குகின்றன. இதுவே பல கட்டளை-வரி ஷெல்களின் மையமாகும், மேலும் இதுவே குளோபிங் என்றும் அழைக்கப்படுகிறது. பொதுவாக மிகக் குறைந்த அளவிலான மாற்று வடிவங்களையே குறிப்பிடும் விதத்தினால் சுருங்குறித் தொடர்கள் வைல்ட் கார்டுகளிலிருந்து வேறுபடுகின்றன.

அடிப்படைக் கருத்துகள்

பெரும்பாலும் வகை என அழைக்கப்படும் ஒரு சுருங்குறித் தொடர், குறிப்பிட்ட குழுவிலுள்ள சரங்களை விவரிக்கும் தொடராகும். அவை வழக்கமாக ஒரு குழுவின் அனைத்து கூறுகளையும் பட்டியலிடும் அவசியம் இன்றி அதற்கான துல்லியமான விளக்கத்தை வழங்கப் பயன்படுத்தப்படுகின்றன. எடுத்துக்காட்டுக்கு, "Handel ", "Händel " மற்றும் "Haendel " என்ற மூன்று சரங்களைக் கொண்டுள்ள ஒரு குழுவை பின்வரும் வகையைக் கொண்டு விவரிக்கலாம், H(ä|ae?)ndel (அல்லது மாறாக, இந்த வகையானது மூன்று சரங்களுக்கும் பொருந்துகிறது எனவும் கூறலாம்). பெரும்பாலான குறிப்பியல்கள், ஏதேனும் ஒரு சுருங்குறித் தொடர் ஒரு குறிப்பிட்ட குழுவிற்குப் பொருந்தினால், அது போன்ற தொடர்கள் எண்ணற்ற அளவில் இருக்கும். பல குறிப்பியல்கள், சுருங்குறித் தொடர்களை அமைக்க பின்வரும் செயல்பாடுகளை வழங்குகின்றன.

பூலியன் "or"

இது மாற்றுகளைப் பிரிக்கும் ஒரு செங்குத்துப் பட்டையாகும். எடுத்துக்காட்டுக்கு, gray

|grey என்பது "gray " அல்லது "grey " என்பனவற்றுக்குப் பொருந்தலாம்.

குழுப்படுத்தல்

பருந்தடைப்புகள், (பிற பயன்பாடுகளுக்கிடையே) ஆப்பரேட்டர்களின் வரம்பு மற்றும் முன்னுரிமையை வரையறுக்கப் பயன்படுத்தப்படுகின்றன. எடுத்துக்காட்டுக்கு, gray

|grey மற்றும் gr(a|e)y ஆகியவை சமமான வகைகள், அவை இரண்டுமே "gray " மற்றும் "grey " ஆகியவற்றை விவரிக்கின்றன.

அளவிடுதல்

ஒரு (ஓர் எழுத்துக்குறி போன்ற) டோக்கன் அல்லது குழு ஆகியவற்றுக்கு அடுத்து வரும் ஒரு அளவீட்டுருவானது முன்னராக வரும் கூறு எவ்வளவு முறை இடம்பெற வேண்டும் என்பதை குறிப்பிடுகிறது. கேள்விக்குறி ?, நட்சத்திரக்குறி * (கிளீன் ஸ்டாரிலிருந்து வந்தது) மற்றும் கூட்டல் குறி + ஆகியவையே மிகவும் பொதுவான அளவீட்டுருக்களாகும்.

`?`	கேள்விக்குறியானது பூச்சியம் அல்லது ஒரு முன்வரும் கூறு உள்ளதைக் குறிக்கிறது. எடுத்துக்காட்டுக்கு, `colou?r` என்பது "color " மற்றும் "colour " ஆகிய இரண்டுக்கும் பொருந்தும்.
`*`	நட்சத்திரக்குறியானது பூச்சியம் அல்லது பல முன்வரும் கூறுகள் உள்ளதைக் குறிக்கிறது. எடுத்துக்காட்டுக்கு, `ab* c` என்பது "ac ", "abc ", "abbc ", "abbbc " அதே போல பலவற்றுக்குப் பொருந்தும்.
`+`	கூட்டல் குறியானது ஒன்று அல்லது பல முன்வரும் கூறுகள் உள்ளதைக் குறிக்கிறது. எடுத்துக்காட்டுக்கு, `ab+c` என்பது "abc ", "abbc ", "abbbc " அதே போல பலவற்றுக்கும் பொருந்தும் ஆனால் "ac " க்குப் பொருந்தாது.

இந்தக் கட்டமைப்புகள் ஒன்று சேர்ந்து கூட்டுத் தொடர்களை உருவாக்கலாம், இது எண்னியலில் எண்கள் மற்றும் + , - , * , மற்றும் ÷ போன்ற ஆப்பரேட்டர்களைக் கொண்டு கட்டமைப்பதைப் போன்றதே ஆகும். எடுத்துக்காட்டுக்கு, H(ae?|ä)ndel மற்றும் H(a|ae|ä)ndel ஆகிய இரண்டுமே செல்லக்கூடிய வகைகளாகும் பின்வரும் முந்தைய எடுத்துக்காட்டைப் போலவே அதே போன்ற சரங்களுக்குப் பொருந்தக்கூடியதாகும், H(ä|ae?)ndel.

சுருங்குறித் தொடர்களுக்கான துல்லியமான தொடரியல் கருவிகள் மற்றும் சூழல்களுக்கு ஏற்ப மாறுபடுகிறது, இது பற்றி கூடுதல் விவரங்கள் தொடரியல் பிரிவில் கொடுக்கப்பட்டுள்ளன.

வரலாறு

சுருங்குறித் தொடர்களின் தோற்றம் தானியங்கல் கோட்பாடு மற்றும் முறைசார் மொழிக் கோட்பாடு ஆகியவற்றை அடிப்படையாகக் கொண்டது, அவை இரண்டும் கோட்பாட்டியல் கணினி அறிவியலின் பகுதிகளாகும். இந்தத் துறைகள் கணிப்பியலின் (தானியங்கல்) மாதிரிகளையும் முறைசார் மொழிகளை விவரிக்கவும் வகைப்படுத்தவுமான வழிகளையும் பற்றி ஆய்வு செய்கின்றன. 1950களில், கணிதவியலாளர் ஸ்டீஃபன் கோல் கிளீன் சுருங்குறிக் குழுக்கள் என்ற தனது கணிதவியல் குறிப்புமுறையைப் பயன்படுத்தி இந்த மாதிரிகளை விவரித்தார் ^[1]. SNOBOL மொழியானது வகைப் பொருத்துதலின் முந்தைய செயல்படுத்தலாகும், ஆனால் அது சுருங்குறித் தொடர்களைப் போன்றதல்ல. கென் தாம்ப்சன், உரைக் கோப்புகளில் உள்ள வகைகளைப் பொருத்தும் வழியாக, கிளீனின் குறிப்புமுறையை QED திருத்தியில் கட்டமைத்தார். அவர் இந்தத் திறனை பின்னர் Unix திருத்தியான ed இல் சேர்த்தார், அது பிரபலமான தேடல் கருவியான grep சுருங்குறித் தொடர்களைப் பயன்படுத்த வழிகோலியது ("grep" என்ற சொல் ed திருத்தியில் சுருங்குறித் தொடர் தேடலுக்கான கட்டளையிலிருந்து வந்தது: g/re /p இதில் re என்பது சுருங்குறித் தொடரைக் குறிக்கும்^[2]). அப்போதிலிருந்து, தாம்ப்சனின் சுருங்குறித் தொடர்களின் பயன்பாட்டின் பல மாற்றியமைக்கப்பட்ட வடிவங்கள் Unix மற்றும் Unix ஐ ஒத்த பயன்பாடுகளில் பரவலாகப் பயன்படுத்தப்படுகின்றன, அவற்றில் expr மற்றும்AWK இமேக்சு vi lex ஆகியவையும் அடங்கும்.

Perl மற்றும் Tcl சுருங்குறித் தொடர்கள் ஹென்றி ஸ்பென்சர் எழுதிய regex நூலகத்திலிருந்து வந்ததாகும், இருப்பினும் Perl பின்னர் பல அம்சங்கள் சேர்க்கப்பட்டு ஸ்பென்சரின் நூலகத்தில் விரிவாக்கப்பட்டது.^[3] ஃபிலிப் ஹாசெல் PCRE ஐ (Perl இணக்கமுள்ள சுருங்குறித் தொடர்கள்) உருவாக்கினார், அது Perl இன் சுருங்குறித் தொடர் செயலம்சத்தை ஒத்ததாக இருக்க முயற்சிக்கிறது, மேலும் PHP மற்றும் அப்பாச்சி HTTP சேவையகம் உள்ளிட்ட கருவிகளால் பயன்படுத்தப்படுகிறது. Perl 6 ஐ உருவாக்குவதற்கான சிரத்தையின் ஒரு பகுதி Perl இன் சுருங்குறித் தொடர் ஒருங்கிணைப்பை சாத்தியப்படுத்துவதும் பாகுபடுத்தல் குறித்தொடர் இலக்கணங்களின் வரையறுத்தலை அனுமதிக்கும் வகையில் அவற்றின் வரம்பு மற்றும் திறன்களை அதிகரிப்பதுமே ஆகும்.^[4] இதன் விளைவு, Perl 6 rules எனும் சிறு-மொழி உருவானது, அவை Perl 6 இலக்கணத்தை வரையறுக்கவும் மொழிக்கான கருவிகளை டெவலப்பர்களுக்கு வழங்கவும் பயன்படுகின்றன. இந்த விதிகளில் Perl 5.x சுருங்குறித் தொடர்களின் அம்சங்கள் இருந்தன, ஆனால் துணை-விதிகளின் பயன்பாட்டின் மூலம் குவிப்பு இறங்குவரிசைப் பாகுபடுத்தியின் BNF-நடை வரையறையையும் அனுமதித்தது.

கட்டமைக்கப்பட்ட தகவல் தரநிலைகளில் ஆவணங்கள் மற்றும் தரவு அடிப்படையிலான மாதிரிப்படுத்தலில் சுருங்குறித் தொடர்களின் பயன்பாடு 1960களில் தொடங்கி ISO SGML (முன்னோடியாக ANSI "GCA 101-1983" இருந்தது) போன்ற தொழில் தரநிலைகள் ஒருங்கிணைந்த போது 1980களில் பரவலாகப் பெருகியது. கட்டமைப்புக் குறிப்புவிவர மொழி தரநிலைகளின் மையம் சுருங்குறித் தொடர்களாகும். எளிய பயன்பாடு DTD கூறுக் குழுத் தொடரியலில் தெளிவாகத் தெரியும்.

வகைப் பொருத்துதல்: வரலாறு என்பதையும் காண்க.

முறைசார் மொழிக் கோட்பாடு

வரையறை

சுருங்குறித் தொடர்களை முறைசார் மொழிக் கோட்பாட்டின் படி வரையறுக்கலாம். சுருங்குறித் தொடர்களில் பல சரங்களின் தொகுதியைக் குறிக்கும் மாறிலிகளும் அவற்றின் செயல்பாடுகளைக் குறிக்கும் ஆப்பரேட்டர்களும் உள்ளன. பின்வரும் வரையறையானது தரநிலையானதாகும், மேலும் முறைசார் மொழிக் கோட்பாட்டில் உள்ள பெரும்பாலான உரைப்புத்தகங்களில் காணப்படுகிறது ^[5]^[6]. வரையறுக்கப்பட்ட நெடுங்கணக்கு Σ கொடுக்கப்பட்டால், பின்வரும் மாறிலிகள் வரையறுக்கப்படுகின்றன:

(வெற்றுத் தொகுதி ) ∅ ∅ தொகுதியைக் குறிப்பது
(வெற்றுச் சரம் ) ε, எழுத்துக்குறிகள் இல்லாத "வெற்று" சரத்தைக் குறிப்பது.
Σ இல் உள்ள (குறிப்பு எழுத்துக்குறி ) a , மொழியில் உள்ள ஒரு எழுத்துக்குறியைக் குறிப்பது.

பின்வரும் செயல்பாடுகள் வரையறுக்கப்படுகின்றன:

(சங்கிலிச்சேர்ப்பு ) RS , தொகுதியைக் குறிப்பது { αβ

| R இல் α மற்றும் S இல் β}. எடுத்துக்காட்டுக்கு {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.

(தொடர்ச்சி ) R

| S மற்றும்' S ஆகியவற்றின் தொகுதிச் சேர்ப்பைக் குறிப்பது. எடுத்துக்காட்டுக்கு {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}.

ε ஐக் கொண்டுள்ளதும் சரத் சங்கிலிச்சேர்ப்பினால் மூடப்பட்டதும் R இன் மிகச்சிறிய முழுமைத் தொகுதியைக் குறிப்பதும் ஆன (கிளீன் ஸ்டார் ) R * . இது R இல் உள்ள சரங்களில் பூச்சிய அல்லது பல சரங்களின் சங்கிலிச்சேர்ப்பின் மூலம் உருவாக்கக்கூடிய அனைத்து சரங்களின் தொகுதியாகும். எடுத்துக்காட்டுக்கு, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", ... }.

பருந்தடைப்பைத் தவிர்ப்பதற்காக, கிளீன் ஸ்டார் மிக உயர்ந்த முன்னுரிமையையும் அடுத்து சங்கிலிச்சேர்ப்பும் அதனையடுத்து தொகுதிச் சேர்ப்பும் என வரிசைப்படுத்தப்படக்கூடியதாகக் கருதப்படுகிறது. அடுத்ததாக எதுவும் இல்லாவிட்டால் பருந்தடைப்பைப் புறக்கணித்துவிடலாம். எடுத்துக்காட்டுக்கு, (ab)c என்பதை abc எனவும் a|(b(c* )) என்பதை a|bc* எனவும் எழுதலாம். பல உரைப்புத்தகங்கள் செங்குத்துப் பட்டைக்குப் பதிலாக ∪, + அல்லது ∨ குறிகளைப் பயன்படுத்துகின்றன.

எடுத்துகாட்டுகள்

a

|b* என்பது {ε, {0}a, b , bb , bbb , ...} ஆகியவற்றைக் குறிக்கிறது

(a

|b)* என்பது a மற்றும் b ஐ தவிர்த்து வேறு குறிகள் ஏதும் இல்லாத, வெற்றுச்சரம் உள்ளிட்ட அனைத்து சரங்களின் தொகுதியையும் குறிக்கிறது: {ε, {0}a, b , aa , ab , ba , bb , aaa , ...}

ab* (c

|ε) என்பது a இல் தொடங்கி, பின்னர் பூச்சிய அல்லது b களைக் கொண்டு இறுதியாக ஒரு c ஐக் கொண்டிருக்கலாம் என்னும் வகையான அனைத்து சரங்களின் தொகுதியைக் குறிக்கிறது: {{0}a, ac , ab , abc , abb , abbc , ...}

குறிப்புணர்த்தும் ஆற்றலும் குறுக்கத் தன்மையும்

சுருங்குறித் தொடர்களின் முறைசார் வறையறைகள் செலவழிக்காதவையும் சில கூடுதல் அளவீட்டுருக்களைப் புறக்கணித்ததும் ஆகும், அவை ? and + ஆகியவவை. இதைப் பின்வருமாறு விளக்கலாம்: a+ = aa* மற்றும் a? = (a|ε). சிலநேரங்களில் நிரப்பு ஆப்பரேட்டர் சேர்க்கப்படுகிறது; R^c என்பது Σ* இல் உள்ளதும் R இல் இல்லாததுமான அனைத்து சரங்களின் தொகுதியைக் குறிக்கிறது. சுருக்கமாக நிரப்பு ஆப்பரேட்டர் என்பது கூடுதலான ஒன்று, ஏனெனில் அவை பிற ஆபரேட்டர்களின் பயன்பாட்டினால் கட்டுப்படுத்தப்படக்கூடியவையே ஆகும். இருப்பினும், அது போன்ற ஒரு குறிப்பைக் கணக்கிடுதலுக்கான செயலாக்கமானது கடினமானது, மேலும் அதன் முடிவானது அடுக்குத்தொடரியல் ரீதியான மிகப் பெரிய மதிப்பாக இருக்கவே வாய்ப்புள்ளது^[7]^[8].

சுருங்குறித் தொடர்கள் இதே முறையில் சுருங்குறி மொழிகளைக் குறிக்க முடியும், துல்லியமாக மொழிகளின் வகையானது நிர்ணயிக்கப்பட்ட வரையறுக்கப்பட்ட தானியங்கால் ஏற்றுக்கொள்ளப்படுகிறது. இருப்பினும் இதில் குறுக்கத்தன்மையில் குறிப்பிடும்படியான வேறுபாடு உள்ளது. சுருங்குறி மொழிகளின் சில வகைகள், அவற்றின் சுருங்குறித் தொடர்களின் அளவில் அடுக்குத்தொடர் முறையில் பெருகக்கூடிய அளவுள்ள நிர்ணயிக்கப்பட்ட வரையறுக்கப்பட்ட தானியங்குகளால் மட்டுமே விவரிக்கப்பட முடியும். மொழிகளில் சில வழக்கமான எடுத்துக்காட்டு, {{0}a,b } நெடுங்கணக்கிலுள்ளதும் k -கடைசி எழுத்து a க்கு சமமானதாகவும் இருக்கக்கூடிய அனைத்து சரங்களையும் L_k கொண்டுள்ளது. மற்றொரு புறம், L ₄ ஐ விவரிக்கும் ஒரு சுருங்குறித் தொடரை $(a|b)^{*}a(a|b)(a|b)(a|b)$ வழங்குகிறது. இந்த வகையை L_k க்குப் பொதுமைப்படுத்துவதன் மூலம் தொடர் கிடைக்கிறது

(a|b)^{*}a\underbrace {(a|b)(a|b)\cdots (a|b)} _{k-1{\text{ times}}}.\,

மற்றொரு புறம், Lk மொழியை ஏற்கும் எல்லா நிர்ணயிக்கப்பட்ட வரையறுக்கப்பட்ட தானியங்கலும் 2k பல நிலைகளைக் கொண்டிருக்க வேண்டியது அவசியம். அதிருஷ்டவசமாக, சுருங்குறித் தொடர்களிலிருந்து அவ்வாறு பெரிய அளவுக்குச் செல்ல வழிகோலாத பல நிர்ணயிக்கப்படாத வரையறுக்கப்பட்ட தானியங்குகளுக்கு (NFAகளுக்கு) எளிய மேப்பிங் உள்ளது; இந்தக் காரணங்களால் NFAகள் பெரும்பாலும் சுருங்குறி மொழிகளுக்கான மாற்றுக் குறிப்பு மொழியாகப் பயன்படுத்தப்படுகிறது. NFAகள் சோம்ஸ்கி வரிசையமைப்பின் இலக்கணங்களின் வகை-3 திரிபுகளாகும் ^[5].

இறுதியாக, பல யதார்த்த "சுருங்குறித் தொடர்" பொறிகள், சுருங்குறித் தொடர்களால் முறைசார் மொழிக்கோட்பாட்டின் தன்மையைக் கொண்டு விவரிக்க முடியாத அம்சங்களைச் செயல்படுத்துகின்றன; இதைப் பற்றி மேலும் அறிய கீழே காண்க.

சுருங்குறித் தொடர்களின் நிர்ணயிப்பு சமானம்

எடுத்துக்காட்டுகள் காண்பிப்பது போல, வெவ்வேறு சுருங்குறித் தொடர்கள் ஒரே மொழியைக் குறிக்கலாம்: வகைத் தத்துவம் என்பது கூடுதலானதாகும்.

கொடுக்கப்பட்ட இரண்டு சுருங்குறித் தொடர்களுக்கு விவரிக்கப்பட்ட மொழிகள் கண்டிப்பாக சமமானவையாக இருக்க வேண்டுமா என்பதை முடிவு செய்யக்கூடியதும் ஒவ்வொரு குறிப்புத் தொடரையும் குறைந்தபட்ச நிர்ணயிக்கப்பட்ட வரையறுக்கப்பட்ட நிலைக்குக் குறைப்பதும், மேலும் அவை ஒப்புமைக்கூறுகளா (சமானமானவையா) என்பதை நிர்ணயிக்கும் வகையிலான ஒரு வழிமுறையை எழுத முடியும்.

இந்தத் தேவையற்ற தன்மை எந்த அளவுக்குக் குறைக்கப்படுகிறது? முழுமையான குறிப்புத் தொடர் தன்மையைக் கொண்ட சுருங்குறித் தொடர்களின் துணைத் தொகுதியைக் கண்டறிய முடியுமா? கிளீன் ஸ்டார் மற்றும் தொகுதி சேர்ப்பு ஆகியவை கண்டிப்பாகத் தேவைப்படுகின்றன, ஆனால் அதன் தேவையை ஓரளவு நாம் கட்டுப்படுத்த முடியும். வியக்கத்தக்க வகையில் இது மிகக் கடினமான சிக்கலாக மாறுகிறது. சுருங்குறித் தொடர்களைப் போல எளியதாக இருக்கும் இவை, அவ்வாறு மாறினால் அவற்றை முறையாக ஒரு இயல்பான வடிவத்தில் மீண்டும் எழுத எந்த முறையும் இல்லை. கடந்தகாலத்தில் இருந்த கருதுகோள் தன்மையின் குறைவினால் ஸ்டார் உயரச் சிக்கல் உண்டாகியது. சமீபத்தில் டெக்ஸ்டெர் கோசென், சுருங்குறித் தொடர்களை கிளீன் இயற்கணிதத்தின் மூலம் கருதுகோள் தன்மையை நிறுவினார்^[9].

தொடரியல்

POSIX

POSIX அடிப்படை சுருங்குறித் தொடர்கள்

மரபுசார் Unix சுருங்குறித் தொடர் தொடரியலானது, பொதுவான மரபையே பின்பற்றியது, ஆனால் அது கருவிக்குக் கருவி மாறுபட்டது. IEEE POSIX அடிப்படை சுருங்குறித் தொடர்கள் (BRE) தரநிலையானது (நீட்டிக்கப்பட்ட சுருங்குறித் தொடர்கள் அல்லது ERE என்ற மாற்று வகைப்பதிப்புடன் வெளியிடப்பட்டது) மரபுசார் (எளிய சுருங்குறித் தொடர்) தொடரியலுக்கான பின்னோக்கிய இணக்கத்தன்மையைக் கருத்தில் கொண்டே உருவாக்கப்பட்டது, ஆனால் அது ஒரு பொதுவான தரநிலையை வழங்கியது, அப்போதிலிருந்து அதுவே பல Unix சுருங்குறித் தொடர் கருவிகளில் இயல்பான தொடரியலாகப் பின்பற்றப்பட்டது, இருப்பினும் அவற்றில் ஆங்காங்கே சில சிறு மாற்றங்கள் அல்லது கூடுதல் அம்சங்கள் இருந்தன. அது போன்ற கருவிகள் பல, கட்டளை வரி மதிப்புருக்களுடனான ERE தொடரியல் ஆதரவையும் வழங்கின.

BRE தொடரியலில், பெரும்பாலான எழுத்துக்குறிகள் குறிப்பெழுத்துகளாகவே கருதப்படுகின்றன — அவை அவற்றுக்கு மட்டுமே பொருந்தும் (அதாவது, a என்பது "a " க்கு மட்டுமே பொருந்தும்). கீழே பட்டியலிடப்பட்டுள்ள எதிர்பார்ப்புகள் மெட்டா எழுத்துக்குறிகள் அல்லது மெட்டா தொடர்கள் எனப்படுகின்றன.

மெட்டா எழுத்துக்குறி	விளக்கம்:
`.`	இது எந்த ஒற்றை எழுத்துக்குறியுடனும் பொருந்தும் (பல பயன்பாடுகள் நியூலைன்களைப் புறக்கணித்துவிடுகின்றன, மேலும் எந்த எழுத்துக்குறிகள் நியூலைன் எழுத்துக்குறியாகக் கருதப்படுகின்றன என்பது உணர்வு, எழுத்துக்குறி குறியாக்கம் மற்றும் பணித்தளம் சார்ந்தது, ஆனால் லைன் ஃபீட் எழுத்துக்குறி இதில் சேர்க்கப்பட்டிருப்பது பாதுகாப்பானதாகும்). POSIX அடைப்புக்குறிக் குறிப்புத்தொடர்களில், புள்ளி எழுத்துக்குறியானது ஒரு வழக்கமான புள்ளிக்குப் பொருந்துகிறது. எடுத்துக்காட்டுக்கு, `a.c` என்பது "abc ", போன்றவற்றுக்குப் பொருந்தும் ஆனால் `[a.c]` என்பது "a ", ". " அல்லது "c " க்கு மட்டுமே பொருந்தும்.
`[ ]`	இது ஒரு அடைப்புக்குறிக் குறிப்புத்தொடராகும். அடைப்புக்குறிக்குள் இருக்கும் ஒற்றை எழுத்துக்குறிக்குப் பொருந்தும். எடுத்துக்காட்டுக்கு, `[abc]` என்பது "a ", "b " அல்லது "c " க்குப் பொருந்தும். `[a-z]` என்பது "a " முதல் "z " வரையிலுள்ள எந்த ஒரு சிற்றெழுத்துக்கும் பொருந்தும் வரம்பைக் குறிப்பிடுகிறது. இந்த வடிவங்கள் கலந்து பயன்படுத்த முடியும்: `[abcx-z]` என்பது `[a-cx-z]` ஐப் போலவே "a ", "b ", "c ", "x ", "y " அல்லது "z " க்குப் பொருந்தும்.`-` எழுத்துக்குறியானது ஒரு அடைப்புக்குறிக்குள் முதல் அல்லது கடைசி எழுத்துக்குறியாக இருக்கும்பட்சத்தில் அல்லது பின்சாய்வுக்கோடு மூலம் தவிர்க்கப்பட்டிருந்தால் அது ஒரு குறிப்புமுறை எழுத்துக்குறியாகக் கருதப்படுகிறது: `[abc-]`, `[-abc]`, அல்லது `[a\-bc]`.
`[^ ]`	இது அடைப்புக்குறிக்குள் இல்லாத ஓர் ஒற்றை எழுத்துக்குறிக்குப் பொருந்துகிறது. எடுத்துக்காட்டுக்கு, `[^abc]` என்பது "a ", "b " அல்லது "c " அல்லாத எழுத்துக்குறி எந்த எழுத்துக்குறிக்கும் பொருந்துகிறது. `[^a-z]` என்பது "a " முதல் "z " வரையில் உள்ள சிற்றெழுத்தல்லாத எந்த ஒரு எழுத்துக்குறிக்கும் பொருந்துகிறது. மேலே உள்ளது போலவே, குறிப்புமுறை எழுத்துக்குறிகளும் வரம்புகளும் கலந்து பயன்படுத்தப்படலாம்.
`^`	இது சரத்தின் தொடக்க நிலைக்குப் பொருந்தும். இது வரி-அடிப்படையிலான கருவிகளில், எந்த ஒரு வரியின் தொடக்க நிலைக்கும் பொருந்துகிறது.
`$`	இது ஒரு சரத்தின் முடிவு நிலைக்குப் பொருந்துகிறது அல்லது ஒரு சரத்தின் புதிய வரியில் முடிவதற்கு சற்று முன்னதான நிலைக்குப் பொருந்துகிறது. இது வரி-அடிப்படையிலான கருவிகளில், எந்த ஒரு வரியின் முடிவு நிலைக்கும் பொருந்துகிறது.
BRE: `` ERE: `( )`	ஒரு குறிக்கப்பட்ட துணைக் குறிப்புத் தொடரை வரையறுக்கிறது. ஒரு பருந்தடைப்புக்குள் உள்ள சரமானது பின்னர் எப்போதும் மீண்டும் பயன்பாட்டுக்கு அழைக்கப்படலாம் (அடுத்த உள்ளீட்டைக் காண்க, `\n` ). ஒரு குறிக்கப்பட்ட துணைக் குறிப்புத் தொடரானது ஒரு தொகுப்பு அல்லது ஒரு பற்றுக் குழு எனவும் அழைக்கப்படுகிறது.
`\n`	எது n வது குறிக்கப்பட்ட துணைக் குறிப்புத் தொடருக்கு எது பொருந்துகிறதோ அதற்கு இது பொருந்துகிறது, இதில் n என்பது 1 முதல் 9 வரையிலுள்ள எண்ணாகும். இந்தக் கட்டமைப்பானது கோட்பாட்டினடிப்படையில் ஒழுங்கற்றதாகும் , மேலும் POSIX ERE தொடரியலிலும் பின்பற்றப்படவில்லை. சில கருவிகள் ஒன்பதுக்கும் மேற்பட்ட பற்றுக் குழுக்களைக் குறிப்பிடுவதற்கு அனுமதிக்கின்றன.
`*`	முன்னதாக உள்ள கூறுக்கு பூச்சியம் அல்லது மேற்பட்ட முறை பொருந்துகிறது. எடுத்துக்காட்டுக்கு, `ab* c` என்பது "ac ", "abc ", "abbbc ", போன்றவற்றுக்குப் பொருந்துகிறது. `[xyz]` என்பது "", "x ", "y ", "z ", "zx ", "zyx* ", "xyzzy ", இன்னும் பலவற்றுக்குப் பொருந்துகிறது. `$ab$` என்பது "", "ab ", "abab* ", "ababab ", போன்ற பலவற்றுக்குப் பொருந்துகிறது.
BRE: `\{m,n\}` ERE: `{m,n}`	முன்னதாக உள்ள கூறுக்கு குறைந்தபட்சம் m முறையும் n க்கு மிகாத முறையும் பொருந்துகிறது. எடுத்துக்காட்டுக்கு, `a\{3,5\}` என்பது "aaa ", "aaaa " மற்றும் "aaaaa " ஆகியவற்றுக்கு மட்டுமே பொருந்தும். இந்த அம்சம் சுருங்குறித் தொடர்களின் பழைய பதிப்புகளில் இருந்ததில்லை.

எடுத்துகாட்டுகள்

.at என்பது "at" என்று முடியும் ஏதேனும் மூன்று-எழுத்துக்குறி சரத்திற்குப் பொருந்தும் , இதில் "hat ", "cat " மற்றும் "bat " ஆகியவை அடங்கும்.
[hc]at என்பது "hat " மற்றும் "cat " க்குப் பொருந்தும்.
[^b]at என்பது "bat " நீங்கலாக .at மூலம் பொருந்தும் அனைத்து சரங்களுக்கும் பொருந்தும்.
^[hc]at என்பது "hat " மற்றும் "cat " க்குப் பொருந்தும், ஆனால் சரம் அல்லது வரியின் தொடக்கத்தில் மட்டுமே.
[hc]at$ என்பது "hat " மற்றும் "cat " க்குப் பொருந்தும், ஆனால் சரம் அல்லது வரியின் முடிவில் மட்டுமே.

POSIX நீட்டிக்கப்பட்ட சுருங்குறித் தொடர்கள்

பின்சாய்வுக்கோட்டின் மூலமாக தவிர்க்கப்பட்ட மெட்டா எழுத்துக்குறிகளின் பொருள், POSIX நீட்டிக்கப்பட்ட சுருங்குறித் தொடர் (ERE) தொடரியலில் சில எழுத்துக்குறிகளுக்கு எதிர்திசையில் அமைகின்றன. இந்தத் தொடரியலில், பின்சாய்வுக்கோடானது மெட்டா எழுத்துக்குறியை ஒரு குறிப்புமுறை எழுத்துக்குறியாகக் கருதப்படச் செய்கிறது. ஆகவே, எடுத்துக்காட்டுக்கு \ (\) என்பது இப்போது ( ) மற்றும் \{\} என்பது இப்போது { }. ஆகும் கூடுதலாக, \n பின்னோக்குக் குறிப்புகளுக்கான ஆதரவு நீக்கப்பட்டு பின்வரும் மெட்டா எழுத்துக்குறிகள் சேர்க்கப்பட்டுள்ளன:

மெட்டா எழுத்துக்குறி	விளக்கம்:
`?`	முன்னதாக உள்ள கூறுக்கு பூச்சியம் அல்லது ஒரு முறை பொருந்தும். எடுத்துக்காட்டுக்கு, `ba?` என்பது "b " அல்லது "ba " க்குப் பொருந்தும்.
`+`	இது முன்னதாக உள்ள கூறுக்கு ஒன்று அல்லது பல முறை பொருந்தும். எடுத்துக்காட்டுக்கு, `ba+` என்பது "ba ", "baa ", "baaa " மற்றும் அது போன்றவற்றுக்குப் பொருந்தும்.
`*`	இது முன்னதாக உள்ள கூறுக்கு பூச்சியம் அல்லது பல முறை பொருந்தும். எடுத்துக்காட்டுக்கு, `ba` என்பது "b ", "ba ", "baa* ", "baaa " மற்றும் அதுபோன்ற பலவற்றுக்குப் பொருந்தும்.
`\|`	தேர்வு (மாற்று அல்லது தொகுதி சேர்ப்பு என்றும் அறியப்படுகிறது) ஆப்பரேட்டரானது, அந்த ஆப்பரேட்டருக்கு முன்பு அல்லது பின்னதாக உள்ள குறிப்புத் தொடருக்குப் பொருந்துகிறது. எடுத்துக்காட்டுக்கு, `abc\|def` என்பது "abc " அல்லது "def " க்குப் பொருந்தும்.

எடுத்துக்காட்டுகள்:

[hc]+at matches "hat ", "cat ", "hhat ", "chat ", "hcat ", "ccchat ", and so on, but not "at ".
[hc]?at என்பது "hat ", "cat " மற்றும் "at " க்குப் பொருந்தும்.
[hc]* at matches "hat ", "cat ", "hhat ", "chat ", "hcat ", "ccchat ", "at ", and so on.
cat

|dog என்பது "cat " அல்லது "dog " க்குப் பொருந்தும்.

POSIX நீட்டிக்கப்பட்ட சுருங்குறித் தொடர்களைப் பெரும்பாலும் கட்டளை வரி கொடி -E ஐச் சேர்த்து Unix பயன்பாடுகளுடன் பயன்படுத்த முடியும்.

POSIX எழுத்துக்குறி வகைகள்

எழுத்துக்குறிகளின் பல வரம்புகள் தேர்ந்தெடுக்கப்படும் மொழியைச் சார்ந்திருப்பதால் (அதாவது சில அமைப்புகளில் எழுத்துகள் abc...zABC... Z ஆகவும் பிறவற்றில் aAbBcC...zZ ஆகவும் ஒழுங்கமைக்கப்படுவதால்), POSIX தரநிலையானது எழுத்துக்குறிகளின் சில வகை அல்லது பிரிவுகளை வரையறுக்கிறது, அது பின்வரும் அட்டவணையில் காண்பிக்கப்பட்டுள்ளது:

POSIX	Perl	ASCII	விளக்கம்
`[:alnum:]`		`[A-Za-z0-9]`	எண்ணெழுத்து எழுத்துக்குறிகள்
`[:word:]`	`\w`	`[A-Za-z0-9_]`	எண்ணெழுத்து எழுத்துக்குறிகள், கூடுதலாக "_"
	`\W`	`[^\w]`	சொல் அல்லாத எழுத்துக்குறி
`[:alpha:]`		`[A-Za-z]`	நெடுங்கணக்கு எழுத்துக்குறிகள்
`[:blank:]`		`[ \t]`	ஸ்பேஸ் மற்றும் tab
`[:cntrl:]`		`[\x00-\x1F\x7F]`	கட்டுப்பாட்டு எழுத்துக்குறிகள்
`[:digit:]`	`\d`	`[0-9]`	எண்கள்
	`\D`	`[^\d]`	எண்-அல்லாதவை
`[:graph:]`		`[\x21-\x7E]`	புலப்படக்கூடிய எழுத்துக்குறிகள்
`[:lower:]`		`[a-z]`	சிற்றெழுத்துகள்
`[:print:]`		`[\x20-\x7E]`	புலப்படக்கூடிய எழுத்துக்குறிகள் மற்றும் இடைவெளிகள்
`[:punct:]`		`[-!"#$%&'()* +,./:;`	புள்ளி எழுத்துக்குறிகள்
`[:space:]`	`\s`	`[ \t\r\n\v\f]`	ஒயிட்ஸ்பேஸ் எழுத்துக்குறிகள்
	`\S`	`[^\s]`	ஒயிட்ஸ்பேஸ்-அல்லாத எழுத்துக்குறி
`[:upper:]`		`[A-Z]`	பேரெழுத்துகள்
`[:xdigit:]`		`[A-Fa-f0-9]`	ஹெக்ஸாடெசிமல் எண்கள்

POSIX எழுத்துக்குறி வகைகளை அடைப்புக்குறிக் குறிப்புத் தொடர்களில் மட்டுமே பயன்படுத்த முடியும். எடுத்துக்காட்டுக்கு, [[:upper:]ab] என்பது பேரெழுத்துகள் மற்றும் சிற்றெழுத்துகள் "a " மற்றும் "b " க்குப் பொருந்தும்.

Perl சுருங்குறித் தொடர்களில், [:print:] என்பது [:graph:] union [:space:] ஆகியவற்றுக்குப் பொருந்தும். கூடுதலாக ஒரு POSIX அல்லாத வகை ஒன்று சில கருவிகளால் புரிந்துகொள்ளப்பட்டது, அது [:word:] ஆகும், அது வழக்கமாக [:alnum:] மற்றும் அண்டர்ஸ்கோர் என வரையறுக்கப்படுகிறது. இது, பல நிரலாக்க மொழிகளில் அடையாளங்காட்டிகளில் பயன்படுத்தப்படும் எழுத்துக்குறிகள் இவையே எனக் காட்டுகிறது. பல நிரலாக்க மொழிகளில் அடையாளங்காட்டிகளைத் தொடங்கக்கூடிய எழுத்துக்குறிகள் நிலைகளில் தோன்றக்கூடியவை போன்றதல்ல என்பதால் Vim திருத்தி, சொல் மற்றும் சொல் தலைப்பு வகைகளை (\w மற்றும் \h குறிப்புகளைப் பயன்படுத்தி) மேலும் வேறுபடுத்துகின்றது.

POSIX சுருங்குறித் தொடர் தரநிலைகள் எழுத்துக்குறி வகைகள் எனக் குறிப்பவை, பிற சுருங்குறித் தொடர் பதிப்புகளில் POSIX எழுத்துக்குறி வகைகளை ஆதரிக்கும் வகைகளே ஆகும். பிற பெரும்பாலான சுருங்குறித் தொடர் வகைப் பதிப்புகளில், எழுத்துக்குறி வகை எந்த POSIX அடைப்புக்குறிக் குறிப்புத் தொடர்களை அழைக்கும் என விவரிக்கப் பயன்படுத்தப்படுகிறது.

Perl-வழித்தோன்றல் சுருங்குறித் தொடர்கள்

Perl, POSIX அடிப்படை (BRE) மற்றும் நீட்டிக்கப்பட்ட (ERE) சுருங்குறித் தொடர் தரநிலைகளைக் காட்டிலும் மிகவும் இசைவுத்தன்மையுள்ள மற்றும் உயர்ந்த தொடரியலைக் கொண்டுள்ளது. \ எழுத்துக்குறி எப்போதும் ஓர் எண்ணெழுத்து அல்லாத எழுத்துக்குறியைத் தவிர்ப்பது அதன் இசைவுத்தன்மைக்கு ஓர் எடுத்துக்காட்டாகும். மந்த அளவீடு என்ற கருத்து Perl இல் உள்ள ஆனால் POSIX-இணக்கத்தன்மையுள்ள சுருங்குறித் தொடர்களில் இல்லாத மற்றொரு செயலம்சத்திற்கு எடுத்துக்காட்டாகும் (அடுத்த பிரிவைக் காண்க).

Perl இன் சக்திமிக்க குறிப்புத்தொடர் திறனின் காரணமாக பிற பல பயன்பாடுகளும் நிரலாக்க மொழிகளும் அதன் தொடரியலை ஒத்தத் தொடரியல்களைப் பின்பற்றின— எடுத்துக்காட்டுக்கு, Java, JavaScript, PCRE, Python, Ruby, Microsoft இன் .NET Framework மற்றும் W3C இன் XML Schema ஆகிய அனைத்தும் Perl இன் சுருங்குறித் தொடர் தொடரியலை ஒத்தத் தொடரியல்களைப் பின்பற்றின. சில மொழிகள் மற்றும் Boost மற்றும் PHP போன்ற கருவிகள் பல சுருங்குறித் தொடர் வகைகளை ஆதரிக்கின்றன. Perl-வழித்தோன்றலான சுருங்குறித் தொடர் செயல்படுத்தல்கள் ஒரே மாதிரியானவை அல்ல, மேலும் அவற்றில் பெரும்பாலானவை Perl இன் அம்சங்களின் துணைத் தொகுதிகள் மட்டுமே.Perl 5.10 இல், Python, PCRE, the .NET Framework மற்றும் Java போன்றவற்றிலிருந்து பெற்ற தொடரியல் நீட்டிப்புகளை Perl பயன்படுத்தியதுடன் அதன் இந்தச் செயலாக்கம் ஒரு முழு வட்டத்திற்கு வந்தது.

எளிய சுருங்குறித் தொடர்கள்

எளிய சுருங்குறித் தொடர்கள் என்பது பயன்பாட்டு நிரல்களின் வரலாற்றுப் பதிப்புகளால் பயன்படுத்தப்படும் தொடரியலாகும் மற்றும் பின்னோக்கு இணக்கத்தன்மை வழங்கும் நோக்கத்தில் சில பிற பயன்பாடுகளால் ஆதரிக்கப்படலாம், அது நிராகரிக்கப்பட்டது^[10].

மந்தமான அளவிடல்

சுருங்குறித் தொடர்களில் உள்ள தரநிலையான அளவீட்டுருக்கள் மிகவும் பேராசை பிடித்தவை, அதாவது அவற்றால் கூடுமான அளவு பொருத்த முயற்சிக்கின்றன, regex இன் மீதமுள்ளவற்றுக்குப் பொருந்தத் தேவையான அளவு மட்டுமே மீதம் வைக்கின்றன. எடுத்துக்காட்டுக்கு, regexes க்கு புதியவர் இந்த எடுத்துக்காட்டிலிருந்து < மற்றும் > க்கு இடையே உள்ள முதல் உருப்படியைக் கண்டறிய விரும்புகிறார் என்க:

Another whale explosion occurred on <January 26>, .

... அவர் <.* > அல்லது அது போன்ற ஒரு வகையைப் பயன்படுத்துவார். இருப்பினும் இந்த வகையானது, எதிர்பார்க்கப்படும் "<January 26> " க்குப் பதிலாக "<January 26>, " என்பதையே வழங்கும், ஏனெனில் * அளவீட்டுருவானது பேராசை பிடித்தது — உள்ளீட்டில் இருந்து தன்னால் கூடுமான அளவு எழுத்துக்குறிகளைப் பயன்படுத்திக்கொள்ளும், மேலும் "January 26>, " என்பதில் "January 26 " ஐ விடவும் அதிகமான எழுத்துக்குறிகள் உள்ளன.

இருப்பினும் இந்த சிக்கலைப் பல வழிகளில் தீர்க்கலாம் (எ.கா., பொருத்தக் கூடாத உரையைக் குறிப்பிடுதல்: <[^>]* >), நவீன சுருங்குறித் தொடர் கருவிகள் ஒரு அளவீட்டுருவிற்கு அடுத்து ஒரு கேள்விக்குறியை இடம்பெறச்செய்வதன் மூலம் அவற்றை மந்தமானவை (பேராசையற்றவை , விரும்பாதவை , குறைவானவை அல்லது பேராசையில்லாதவை ) எனக் குறிப்பிடும் வசதியை வழங்குகின்றன (எ.கா., <.* ?>) அல்லது அந்த அளவீட்டுருக்களின் பேராசையை எதிராக மாற்றும் மாற்றிகளைப் பயன்படுத்தியும் இதைச் செய்யலாம் (இருப்பினும் தரநிலையான அளவீட்டுருக்களின் பொருளை மாற்றுவது குழப்பத்தை விளைவிக்கலாம்). ஒரு மந்த அளவீட்டுருவைப் பயன்படுத்துவதன் மூலம், குறிப்புத் தொடரானது முதலில் குறைந்தபட்சப் பொருத்தங்களையே தேடும். இருப்பினும் முந்தைய எடுத்துக்காட்டில் பொருந்தக்கூடிய பல முடிவுகளில் ஒன்றைத் தேர்ந்தெடுக்க மந்தப் பொருத்தம் பயன்படுத்தப்படுகிறது, பேராசைப் பொருத்தத்திற்கு அதிக அளவு பின்தடமறியும் தேவை ஏற்படும் சில சந்தர்ப்பங்களில் மந்தப் பொருத்தமானது செயல்திறனை அதிகரிக்கவும் பயன்படுத்தப்படுகிறது.

சுருங்குறி அல்லாத மொழிகளுக்கான வகைகள்

நவீன சுருங்குறித் தொடர் நூலகங்களில் காணப்படும் பல அம்சங்கள் சுருங்குறி மொழிகளையும் விஞ்சும் அளவிலான குறிப்புத்தொடர்த் திறனை வழங்குகின்றன. எடுத்துக்காட்டுக்கு, பல செயல்படுத்தல்கள், பருந்தடைப்பின் மூலமாக துணைக் குறிப்புத் தொடர்களின் குழுப்படுத்தல் மற்றும் அதே குறிப்புத் தொடரில் அவற்றுக்குப் பொருந்தும் மதிப்புகளைப் பயன்படுத்த அழைத்தல் ஆகியவற்றை அனுமதிக்கின்றன(பின்குறிப்புமுறை ). அதாவது ஒரு வகையானது, முறைசார் மொழிக் கோட்பாட்டில் சதுரங்கள் என அழைக்கப்படும்"papa " அல்லது "WikiWiki " போன்ற திரும்பத் திரும்ப வரும் சொற்களைக் கொண்டுள்ள சரங்களைப் பொருத்த முடியும். இந்தச் சரங்களுக்கான வகை, (.[1] ஆகும்.

இருப்பினும், சதுரங்களின் மொழியானது சுருங்குறி அல்ல, மேலும் அது சூழல் தடையற்றதும் அல்ல. கட்டுப்பாடற்ற பல பின் குறிப்புகளைக் கொண்டு, பல நவீன கருவிகளை ஆதரிக்கும் வகையில் வகைப் பொருத்துதல் என்பதே NP-கம்ப்ளீட் எனப்படும், (^[11], தேற்றம் 6.2 ஐக் காண்க).

இருப்பினும், இது போன்ற கட்டமைப்புகளை வழங்கும் பல கருவிகள், நூலகங்கள் மற்றும் பொறிகள் அவற்றின் வகைகளைக் குறிப்பிட சுருங்குறித் தொடர் என்னும் சொல்லையே இப்போதும் பயன்படுத்துகின்றன. முறைசார் மொழிக் கோட்பாடு மற்றும் வகைப் பொருத்தலில் சுருங்குறித் தொடர் எனும் சொல் கொண்டுள்ள பல பொருள்களால் பெயரிடு முறை ஒன்று தோன்றும் நிலை ஏற்பட்டது. இந்தக் காரணத்தினாலே, பின்னதை விவரிக்க regex அல்லது வெறுமென வகை என்ற சொற்களைப் பயன்படுத்தினர். Perl நிரலாக்க மொழியின் ஆசிரியரான லாரி வால், Perl 6 உருவாக்கத்தைப் பற்றி தனது புத்தகத்தில் எழுதுகிறார்:

“

'Regular expressions' [...] are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood).^[4]

”

செயல்படுத்தல்கள் மற்றும் இயக்க நேரங்கள்

கொடுக்கப்பட்ட ஒரு சுருங்குறித் தொடர் ஒரு சரத்தை பொருத்துமா மற்றும் எவ்வாறு பொருத்தும் என்பதை விவரிக்க குறைந்தது மூன்று வெவ்வேறு வழிமுறைகள் உள்ளன.

மிகப் பழையதும் வேகமானதுமான இரண்டு வழிமுறைகள், எல்லா நிர்ணயிக்கப்படாத வரையறுக்கப்பட்ட நிலை இயந்திரத்தையும் (NFA) ஒரு நிர்ணயிக்கப்பட்ட வரையறுக்கப்பட்ட நிலை இயந்திரமாக (DFA) மாற்ற அனுமதிக்கும் முறைசார் மொழிக் கோட்பாட்டில் உள்ள ஒரு முடிவை நம்பியுள்ளவை. DFA ஐ தனிப்பட்ட விதத்தில் கட்டமைக்க முடியும், மேலும் பின்னர் அதை முடிவான உள்ளீட்டு சரத்தின் ஒரு குறியீட்டில் ஒரே நேரத்தில் இயக்கவும் முடியும். m அளவுள்ள ஒரு சுருங்குறித் தொடருக்கான DFA ஐக் கட்டமைப்பதற்கு நேரம் மற்றும் நினவகச் செலவு O(2^m ) என்று இருக்கும், ஆனால் அதனை n அளவுள்ள ஒரு சரத்தில் O (n ) நேரத்திற்கு இயக்க முடியும். NFA ஐ நேரடியாக நகலெடுப்பதும் மற்றொரு மாற்று அணுகுமுறையாகும், இதில் தேவைப்படும் போது ஒவ்வொரு DFA நிலையையும் கட்டமைப்பதும் அடுத்த படியில் அதனை கூடுமானவரை தேக்கக அம்சத்துடன் நிராகரிப்பதும் அவசியமாகும். இது DFA சந்தேகமற்றதாக மாற்றும், மேலும் அடுக்குத்தொடர் கட்டமைப்புச் செலவைக் குறைக்கும், ஆனால் இயக்குதல் செலவானது O (nm ) என இருக்கும். வெளிப்படையான அணுகுமுறையானது DFA வழிமுறை எனவும் மறைமுக அணுகுமுறையானது NFA வழிமுறை எனவும் அழைக்கப்படுகிறது. இவை இரண்டையுமே ஒரே DFA ஐச் செயல்படுத்தும் இரண்டு வழிகளாகக் கருதலாம், மேலும் அவை இரண்டும் தனித்தன்மையின்றி DFA வழிமுறைகள் எனவும் அழைக்கப்படுகின்றன. இந்த வழிமுறைகள் வேகமானவை, ஆனால் அவற்றை குழுப்படுத்தப்பட்ட துணைக் குறித்தொடர்கள், மந்தமான அளவீட்டுருவாக்கம் மற்றும் அது போன்ற அம்சங்களுக்காக மீண்டும் அழைப்பது என்பது மிகவும் சிக்கலானதாகும்.^[12]^[13]

மூன்றாவது வழிமுறையானது வகையை உள்ளீட்டுச் சரத்திற்கு எதிராக பின்தடமறிதல் மூலம் பொருத்துவதாகும். இந்த வழிமுறையானது பொதுவாக NFA என அழைக்கப்படுகிறது, ஆனால் இந்த சொல்லியல் குழப்பமானதாக இருக்கலாம். அதன் இயக்க நேரமானது, எளிய செயல்படுத்தல்கள், (a|aa)* b போன்ற மாற்றம் மற்றும் கட்டுப்படுத்தப்படாத அளவீட்டுருவாக்கம் கொண்டுள்ள குறிப்புத் தொடர்களுக்கெதிராக வழங்குவது போன்ற அடுக்குத்தொடர் தன்மை கொண்டதாக இருக்கலாம், மேலும் அவை வழிமுறையை அடுக்குத் தொடர் முறையில் அதிகரிக்கும் பல துணை-நிலைகளாகக் கருதச் செய்யலாம். மிகவும் சிக்கலான செயல்படுத்தல்கள் பெரும்பாலும் பொதுவான நிகழ்வுகளில் அடையாளங்காணவோ வேகப்படுத்தவோ அல்லது கைவிடவோ செய்கின்றன, அவை அவ்வாறு செய்யாவிட்டால் அவை வேகமாக இயங்காது எனும் நிலையில் இவ்வாறு செய்கின்றன.

பின்தடமறியும் செயல்படுத்தல்கள் மோசமான சூழ்நிலைகளுக்கு அடுக்குத்தொடருக்கான உத்தரவாதத்தை மட்டுமே கொடுக்கின்றன எனினும் அவை மிக அதிகமான நெகிழ்தன்மையையும் குறிப்புத்தொடர் திறனையும் வழங்குகின்றன. எடுத்துக்காட்டுக்கு, பின்குறிப்பு வழங்கலைப் பயன்படுத்த அனுமதிக்கும் அல்லது Perl அறிமுகப்படுத்திய பல்வேறு நீட்டிப்புகளைச் செயல்படுத்தும் செயல்படுத்தல்கள் எதுவும் பின்தடமறிதல் செயல்படுத்தலைப் பயன்படுத்த வேண்டும்.

சில செயல்படுத்தல்கள், முதலில் சரமானது சுருங்குறித் தொடருக்குப் பொருந்துகிறதா எனப் பார்க்க ஒரு வேகமான DFA பொருத்தத்தை இயக்கி இரண்டு வழிமுறைகளின் சிறப்பான விளைவை வழங்க முயற்சிக்கின்றன, மேலும் அவ்வாறு இருந்தால் மட்டுமே மெதுவான பின்தடமறிதல் பொருத்தத்தைச் செயல்படுத்துகின்றன.

சுருங்குறித் தொடர்கள் மற்றும் யுனிகோட்

சுருங்குறித் தொடர்கள் முதலில் ASCII எழுத்துக்குறிகளுடனே பயன்படுத்தப்பட்டன. பல சுருங்குறித் தொடர் பொறிகள் இப்போது யுனிகோடைக் கையாளக்கூடிய திறன் கொண்டவை. பெரும்பாலான சமயங்களில் எழுத்துக்குறித் தொகுதி எதுவாக இருந்தாலும் அது கருத்தில் கொள்ளத்தக்கதல்ல, ஆனால் சுருங்குறித் தொடர்களை யுனிகோடை ஆதரிக்கும் வகையில் நீட்டிப்பதால் சில சிக்கல்கள் எழுகின்றன.

ஆதரிக்கப்படும் குறியாக்கங்கள். சில சுருங்குறித் தொடர் நூலகங்கள் UTF-8 குறியாக்கத்தை எதிர்பார்ப்பவையாக உள்ளன, மற்றவை UTF-16 அல்லது UTF-32 ஐ எதிர்பார்க்கின்றன.

ஆதரிக்கப்படும் யுனிகோட் வரம்பு. பல சுருங்குறித் தொடர் பொறிகள் அடிப்படை பன்மொழித் தளங்களையே ஆதரிக்கின்றன, அதாவது 16 பிட்களில் மட்டுமே குறியாக்கம் செய்யக்கூடிய எழுத்துக்குறிகள். தற்போது, ஒரு சில சுருங்குறித் தொடர் பொறிகள் மட்டுமே 21-பிட் யுனிகோட் வரம்பைக் கையாளுகின்றன.

ASCII-சார்ந்த கருத்துகளை யுனிகோடிற்கு நீட்டித்தல். எடுத்துக்காட்டுக்கு, ASCII-அடிப்படையான செயல்படுத்தல்களில், [x-y] படிவத்தின் எழுத்துக்குறி வரம்புகள் x மற்றும் y ஆகியவை [0x00,0x7F] வரம்பில் இருக்கும் வரையிலும், குறியீட்டுப் புள்ளி(x) ≤ குறியீட்டுப்புள்ளி(y) என்ற நிலையில் இருக்கும் வரையிலும் செல்லுபடியாகக்கூடியனவாக உள்ளன. யுனிகோடுக்கான இது போன்ற எழுத்துக்குறி வரம்புகளால், [0x00,0x7F] இல் இருக்கும் முடிவுப் புள்ளிகள் [0,0x10FFFF] இல் இருக்க வேண்டிய அவசியத்தை ஏற்படுத்தும். இருப்பினும், நடைமுறையில் இது போல நிகழ்வதில்லை. gawk இன் செயல்படுத்தல் போன்ற சில செயல்படுத்தல்கள், எழுத்துக்குறி வரம்புகள் யுனிகோட் தொகுப்பை மீற அனுமதிப்பதில்லை. [0x61,0x7F] போன்ற வரம்புகள் இரண்டு முடிவுப் புள்ளிகளுமே அடிப்படை லத்தீன் தொகுப்பில் அமைவதால் செல்லுபடியாகின்றன, அது [0x0530,0x0560] போன்றதில் இரு முடிவுப்புள்ளிகளும் அமெரிக்கன் தொகுப்பில் அமைகின்றன, ஆனால் [0x0061,0x0532] போன்ற வரம்புகள் பல யுனிகோட் தொகுப்புகளைக் கொண்டிருப்பதால் அவை செல்லுபடியானவை அல்ல. Vim திருத்தியின் பொறி போன்ற பொறிகள், தொகுப்பு மீறல்களை அனுமதிக்கின்றன, ஆனால் எழுத்துக்குறிகளின் எண்ணிக்கையை 128 க்குள் வரம்புப்படுத்தியுள்ளன.

பேரெழுத்து உணராத் தன்மை. சில பேரெழுத்து உணராத் தன்மைக்கான கொடிகள் ASCII எழுத்துக்குறிகளை மட்டுமே பாதிக்கும். பிற கொடிகள் அனைத்து எழுத்துக்குறிகளையும் பாதிக்கின்றன. சில பொறிகள் இரண்டு வெவ்வேறு கொடிகளைக் கொண்டுள்ளன, அதில் ஒன்று ASCII க்கும் மற்றொன்று யுனிகோடுக்கும் ஆகும். துல்லியமாக POSIX வகைகளைச் சேர்ந்த எழுத்துக்குறிகளும் மாறுபடுகின்றன.

பேரெழுத்துணர்தன்மையின் உறவுகள். ASCII க்கு பேரெழுத்து தனிப்படுத்தல்கள் இருப்பதால், உரைத் தேடலில் பேரெழுத்து உணராத் தன்மை என்பது ஒரு தர்க்கவியல் அம்சமாகியது. தேவநகரி போன்ற பேரெழுத்து சிற்றெழுத்து வேறுபாடற்ற நெடுங்கணக்கு எழுத்துகளை யுனிகோட் அறிமுகப்படுத்தியது. இவற்றுக்கு, பேரெழுத்து உணர்தன்மை என்பது பொருந்தாது. சைனீஸ் போன்ற வரிவடிவங்களுக்கு, மற்றொரு வித்தியாசம் தர்க்க ரீதியானதாக் உள்ளது: அது மரபுசார்ந்த மற்றும் எளிய என்ற இரு வகைகளாகும். அரபி மொழி வரிவடிவங்களில், தொடக்க, இடைநிலை, இறுதி மற்றும் தனியான நிலைகளில் பேரெழுத்து உணராத் தன்மை தேவைப்படுகிறது.

இயல்பாக்குதல். யுனிகோட், சேர்ப்பு எழுத்துக்குறிகளை அறிமுகப்படுத்தியது. பழைய தட்டச்சுப் பொறிகளைப் போல, எளிய எழுத்துகளுக்கு அடுத்து இடைவெளியில்லா அசையழுத்தக் குறிகளைச் சேர்த்து ஒற்றை அசையழுத்தம் கொண்ட எழுத்தாக அவற்றை மாற்ற முடியும். இதன் விளைவாக, இரண்டு வெவ்வேறு குறியீட்டுத் தொடர்கள் ஒரே மாதிரியான எழுத்துக்குறிக் காட்சிப்படுத்தலை விளைவிக்கலாம்.

புதிய கட்டுப்பாட்டுக் குறியீடுகள். யுனிகோட் பலவற்றுடன் சேர்த்து பைட் வரிசை குறிப்புகள் மற்றும் உரைத் திசை மார்க்கர்கள் ஆகியவற்றையும் அறிமுகப்படுத்தியது. இந்தக் குறியீடுகள் ஒரு தனிச்சிறப்பு வழியில் கையாளப்பட வேண்டும்.

யுனிகோட் தொகுப்புகள் மற்றும் யுனிகோட் பொது எழுத்துக்குறி பண்புகள் மற்றும் எழுத்துக்குறி வகைகளின் அறிமுகம். Perl மற்றும் [[[:வார்ப்புரு:Javadoc:SE/Home URL]]docs/api/java/util/regex/package-summary.html java.util.regex] \p{InX} நூலகத்தில் வடிவத்தில் உள்ள எழுத்துக்குறிகள், X தொகுப்பிலுள்ள எழுத்துக்குறிகளுக்கும் \P{InX} அதற்கு எதிரானதற்கும் பொருந்தும். இதே போல, \p{Armenian} என்பது அமெரிக்கன் தொகுப்பில் உள்ள எந்த எழுத்துக்குறிக்கும் பொருந்தும், மேலும் \p{X} என்பது X எனும் பொது எழுத்துக்குறிப் பண்பு கொண்டுள்ள எந்த எழுத்துக்குறிக்கும் பொருந்தும். எடுத்துக்காட்டுக்கு, \p{Lu} என்பது பேரெழுத்து எதற்கும் பொருந்தும்.

சுருங்குறித் தொடர்களின் பயன்கள்

சுருங்குறித் தொடர்கள் தொடரியல் தனிப்படுத்தல் முறைமைகள் உருவாக்கம், தரவு செல்லுபடியாக்கம் மற்றும் பிற பல பணிகளிலும் பயன்படுகின்றன.

சுருங்குறித் தொடர்கள், கூகுள், Bing அல்லது Yahoo! தேடல் போன்ற தேடு பொறிகளில் மிகப் பயனுள்ளதாக உள்ளன, அவற்றை ஒட்டுமொத்த தரவுத்தளத்திலும் செயல்படுத்துவதற்கு மிக அதிக அளவு கணினி வளங்கள் தேவைப்படலாம், அது regex இன் சிக்கலான தன்மை மற்றும் வடிவமைப்பைச் சார்ந்தது. இருப்பினும், பல சமயங்களில் கணினி நிர்வாகிகள் regex-அடிப்படையிலான வினவல்களை அக ரீதியாக செயல்படுத்தலாம், பெரும்பாலான தேடுபொறிகள் பொதுமக்களுக்கு regex ஆதரவை வழங்குவதில்லை. Google குறியீட்டுத் தேடல் இதற்கு ஒரு பிரபல விதிவிலக்காகும்.

மேலும் பார்க்க

குறிப்புகள்

↑ (Kleene 1956)
↑ Raymond, Eric S. citing Dennis Ritchie (2003). "Jargon File 4.4.7: grep".
↑ Wall, Larry and the Perl 5 development team (2006). "perlre: Perl regular expressions".{{cite web}}: CS1 maint: numeric names: authors list (link)
↑ ^4.0 ^4.1 (Wall 2002)
↑ ^5.0 ^5.1 (Hopcroft, Motwani & Ullman 2000)
↑ (Sipser 1998)
↑ (Gelade & Neven 2008)
↑ (Gruber & Holzer 2008)
↑ (Kozen 1991)
↑ ஒற்றை Unix குறிப்புவிவரம் (பதிப்பு 2)
↑ (Aho 1990)
↑ (Cox 2007)
↑ (Laurikari 2009)

குறிப்புதவிகள்

Aho, Alfred V. (1990), "Algorithms for finding patterns in strings", in van Leeuwen, Jan (ed.), Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity, The MIT Press, pp. 255–300
"Regular Expressions", The Single UNIX Specification, Version 2, The Open Group, 1997
Cox, Russ (2007), Regular Expression Matching Can Be Simple and Fast
Forta, Ben (2004). Sams Teach Yourself Regular Expressions in 10 Minutes. Sams. பன்னாட்டுத் தரப்புத்தக எண் 0-672-32566-7.
Friedl, Jeffrey (2002). Mastering Regular Expressions. O'Reilly. பன்னாட்டுத் தரப்புத்தக எண் 0-596-00289-0. {{cite book}}: External link in |title= (help)
Gelade, Wouter; Neven, Frank (2008), "Succinctness of the Complement and Intersection of Regular Expressions", Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 325–336
Gruber, Hermann; Holzer, Markus (2008), "Finite Automata, Digraph Connectivity, and Regular Expression Size", Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008) (PDF), pp. 39–50, எண்ணிம ஆவணச் சுட்டி:10.1007/978-3-540-70583-3_4, archived from the original (PDF) on 2009-09-01, பார்க்கப்பட்ட நாள் 2010-01-11
Habibi, Mehran (2004). Real World Regular Expressions with Java 1.4. Springer. பன்னாட்டுத் தரப்புத்தக எண் 1-59059-107-0.
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2000). Introduction to Automata Theory, Languages, and Computation (2nd ed.). Addison-Wesley.
Kleene, Stephen C. (1956), "Representation of Events in Nerve Nets and Finite Automata", in Shannon, Claude E.; McCarthy, John (eds.), Automata Studies, Princeton University Press, pp. 3–42
Kozen, Dexter (1991), "A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events", Proceedings of the 6th Annual IEEE Symposium on Logic in Computer Science (LICS 1991), pp. 214–225
Laurikari, Ville (2009). "TRE library 0.7.6".
Liger, Francois (2002). Visual Basic .NET Text Manipulation Handbook. Wrox Press. பன்னாட்டுத் தரப்புத்தக எண் 1-86100-730-2. {{cite book}}: Unknown parameter |coauthors= ignored (help)
Sipser, Michael (1998). "Chapter 1: Regular Languages". Introduction to the Theory of Computation. PWS Publishing. pp. 31–90. பன்னாட்டுத் தரப்புத்தக எண் 0-534-94728-X.
Stubblebine, Tony (2003). Regular Expression Pocket Reference. O'Reilly. பன்னாட்டுத் தரப்புத்தக எண் 0-596-00415-X.
Wall, Larry (2002-06-04). "Apocalypse 5: Pattern Matching".{{cite web}}: CS1 maint: date and year (link)

புற இணைப்புகள்

JavaScript Regular Expressions Chapter பரணிடப்பட்டது 2008-12-03 at the வந்தவழி இயந்திரம் மற்றும் Mozilla டெவலப்பர் மையத்தில் RegExp Object Reference
Java கற்றல் பயிற்சிகள்: சுருங்குறித் தொடர்கள்
Perl சுருங்குறித் தொடர்கள் ஆவணமாக்கல்
VBScript மற்றும் சுருங்குறித் தொடர்கள்
.NET Framework சுருங்குறித் தொடர்கள்
Regular Expressions திறந்த ஆவணத் திட்டத்தில்
Regular-Expressions.info — பல பிரபலமான regex வகைப் பதிப்புகளைப் பற்றிய கற்றல் பயிற்சி மற்றும் குறிப்பு
வகைப் பொருத்துதல் கருவிகள் மற்றும் நூலகங்கள்
சுருங்குறித் தொடர்கள் கணித மற்றும் கணினிக் குறிப்புமொழிகளை விளக்கிப் பிரபலப் பயன்படுத்துகின்றன.
சுருங்குறித் தொடர்கள் நூலகம்
கட்டமைப்பு சுருங்குறித் தொடர்கள் - ராப் பைக்
மேம்பட்ட சுருங்குறித் தொடர்களில் உள்ள இன்றியமையாத கருத்துகள்

[1] (Kleene 1956)

[2] Raymond, Eric S. citing Dennis Ritchie (2003). "Jargon File 4.4.7: grep".

[3] Wall, Larry and the Perl 5 development team (2006). "perlre: Perl regular expressions".{{cite web}}: CS1 maint: numeric names: authors list (link)

[Apocalypse5-4] 4.0 ^4.1 (Wall 2002)

[HopcroftMotwaniUllman01-5] 5.0 ^5.1 (Hopcroft, Motwani & Ullman 2000)

[6] (Sipser 1998)

[7] (Gelade & Neven 2008)

[8] (Gruber & Holzer 2008)

[9] (Kozen 1991)

[10] ஒற்றை Unix குறிப்புவிவரம் (பதிப்பு 2)

[Aho90-11] (Aho 1990)

[12] (Cox 2007)

[13] (Laurikari 2009)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]