article.md

গ্রীডি এবং লেজি কোয়ান্টিফায়ার

প্রথম দেখায় কোয়ান্টিফায়ারকে সহজ মনে হতে পারে, কিন্তু বাস্তবে এরা কৌশলী।

জটিল কিছু খোঁজার পূর্বে আমাদের বুঝতে হবে pattern:/\d+/ এরা কিভাবে কাজ করে।

উদাহরণ হিসাবে নিচের টাস্কটি নিয়ে কাজ করি।

আমাদের কাছে একটি টেক্সট আছে এবং আমরা সকল উদ্ধৃতি চিহ্নকে "..." গিলিমেট চিহ্ন «...» দিয়ে প্রতিস্থাপন করব। অনেক দেশে টাইপোগ্রাফির জন্য এগুলোই বেশি পছন্দের।

উদাহরণস্বরূপ: "Hello, world" হবে «Hello, world». আরো অনেক ধরণের উদ্ধৃতি চিহ্ন আছে, যেমন „Witam, świat!” (পোলিশ) অথবা 「你好，世界」 (চাইনিজ), কিন্ত আমাদের টাস্কের জন্য এখন এটিই «...» যুতসই।

আমাদের প্রথম কাজটি হল স্ট্রিং হতে উদ্ধৃতি চিহ্নগুলোকে চিহ্নিত করা, এবং তারপর এদের আমরা প্রতিস্থাপন করতে পারব।

রেগুলার এক্সপ্রেশনে আমাদের প্যাটার্নটি হবে এমন pattern:/".+"/g (শুরুর উদ্ধৃতি চিহ্ন, তারপর কিছু ক্যারাক্টার, অতঃপর শেষ উদ্ধৃতি চিহ্ন) যদিও দেখতে সঠিক মনে হচ্ছে, তবে এটি সঠিক নই!

চেষ্টা করা যাক:

let regexp = /".+"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch" and her "broom"

...আমরা দেখতে পাচ্ছি এটি আমাদের চাহিদামত কাজ করছে না!

match:"witch" এবং match:"broom" এই দুটি মিল খুঁজে পাওয়ার পরিবর্তে এটি দেখায়: match:"witch" and her "broom"।

এজন্য বলা হয় "লোভ হল সকল পাপের কারণ"।

গ্রীডি অনুসন্ধান

কোন একটি মিল খুঁজতে রেগুলার এক্সপ্রেশন ইঞ্জিন নিম্নে উল্লেখিত অ্যালগরিদম অনুযায়ী কাজ করে:

• স্ট্রিংয়ের প্রতিটি অবস্থানের জন্য
  • অই অবস্থানে প্যাটার্নটির অবস্থান মেলানোর চেষ্টা করে।
  • যদি কোন মিল না পায়, তাহলে পরের অবস্থানে যায়।

উপরোল্লিখিত নিয়ম থেকে রেগুলার এক্সপ্রেশন কিভাবে কাজ করে তা আমাদের কাছে সহজে বোধগম্য নই, চলুন এই প্যাটার্নটি pattern:".+" কিভাবে মিল খুঁজে তা বিস্তারিত দেখি।

১. আমাদের প্যাটার্নের প্রথম ক্যারাক্টারটি একটি উদ্ধৃতি চিহ্ন pattern:"।

রেগুলার এক্সপ্রেশন ইঞ্জিন প্রদত্ত স্ট্রিংয়ের `subject:a "witch" and her "broom" is one` শূন্যতম অবস্থানে একটি উদ্ধৃতি চিহ্ন মেলানোর চেষ্টা করে, কিন্তু অই অবস্থানে ক্যারাক্টারটি হল `subject:a`, সুতরাং কোন মিল খুঁজে পাবে না।

তারপর এটি এর পরবর্তী অবস্থানে যাবে: অই অবস্থানে প্রদত্ত স্ট্রিংয়ের সাথে প্যাটার্নের প্রথম ক্যারাক্টারটি মেলানোর চেষ্টা করে, এবং এটিও মেলে না, অবশেষে ৩য় অবস্থানে এটি উদ্ধৃতি চিহ্নের সাথে মেলে:

![](witch_greedy1.svg)

২. উদ্ধৃতি চিহ্নের সাথে মিল হওয়ার পর, ইঞ্জিন বাকি প্যাটার্নটির মিল খুঁজে। ইঞ্জিন প্রদত্ত স্ট্রিংয়ের সাথে আমাদের প্যাটার্নের pattern:.+" মিল খুঁজে।

এইক্ষত্রে, আমাদের প্যাটার্নের পরবর্তী ক্যারাক্টারটি হল `pattern:.` (একটি ডট ক্যারাক্টার)। এটি দ্বারা বুঝায় "নতুন লাইন ব্যাতীত সকল ক্যারাক্টার", সুতরাং স্ট্রিংয়ের পরবর্তী বর্ণ `match:'w'` এর সাথে মিল খুঁজে পায়:

![](witch_greedy2.svg)

৩. এরপর ডটের সাথে কোয়ান্টিফায়ার pattern:.+ থাকার কারনে রেগুলার এক্সপ্রেশন ইঞ্জিন পরবর্তী ক্যারাক্টার গুলোর সাথে মিলতে থাকে।

...কিন্তু কতক্ষণ পর্যন্ত মিলবে? এটি স্ট্রিংয়ের শেষ পর্যন্ত এর সকল ক্যারাক্টার ডটের সাথে মেলতে থাকে:

![](witch_greedy3.svg)

৪. এখন ইঞ্জিন এই প্যাটার্নের pattern:.+ পুনরাবৃত্তি শেষে পরের প্যাটার্নটি খুঁজে। এটি হল উদ্ধৃতি চিহ্ন pattern:"। কিন্ত এখানে একটি সমস্যা আছে: প্যাটার্নের অবস্থান প্রদত্ত স্ট্রিংটির শেষে, এরপর আর কোন ক্যারাক্টার নেয়!

রেগুলার এক্সপ্রেশন ইঞ্জিন বুঝতে পারে `pattern:.+` অনেক বেশী অগ্রসর হয়ে গেছে সুতরাং এটি প্রাপ্ত মিলটিকে *ব্যাকট্রাক* বা প্রত্যাখ্যান করা শুরু করে।

অন্যথায় বলা যায়, কোয়ান্টিফায়ারের জন্য একটি ক্যারাক্টার বাদ দেয়:

![](witch_greedy4.svg)

এখন এটি ধরা যাক `pattern:.+` শেষ। স্ট্রিংয়ের শেষ অবস্থান হতে একটি ক্যারাক্টার নেয় এবং সেই অবস্থান থেকে বাকী প্যাটার্নটি মেলাতে চেষ্টা করে।

যদি অই অবস্থানে উদ্ধৃতি চিহ্ন থাকে তবে আমাদের অনুসদ্ধানটি শেষ হবে, কিন্তু শেষ ক্যারাক্টারটি হল `subject:'e'`, সুতরাং কোন মিল হবেনা।

৫. ...সুতরাং ইঞ্জিন pattern:.+ এর জন্য আরও একটি ক্যারাক্টার কমাবে:

![](witch_greedy5.svg)

কিন্তু `pattern:'"'` উদ্ধৃতি চিহ্ন `subject:'n'` এর সাথে মেলেনা।

৬. ইঞ্জিনটি ব্যাকট্র্যাকিং চালিয়ে যায়: এটি pattern:'.' এর জন্য ক্রমাগত অনুসন্ধানকৃত ফলাফলটিকে সংক্ষিপ্ত করতে থাকে যতক্ষণ পর্যন্ত আমাদের প্যাটার্নটির (এইক্ষেত্রে pattern:'"') মিল শেষ হয়:

![](witch_greedy6.svg)

৭. অনুসন্ধানটি সম্পূর্ন হয়।

৮. সুতরাং আমাদের প্রথম অনুসন্ধানটি হল match:"witch" and her "broom"। যদি রেগুলার এক্সপ্রেশনে pattern:g ফ্ল্যাগটি থাকে, তাহলে অনুসন্ধানটি চলবে যেখানে প্রথম মিলটি শেষ হয়। বাকী স্ট্রিংয়ে subject:is one আর কোন উদ্ধৃতি চিহ্ন নেই, সুতরাং অন্য কোন ফলাফল আসবে না।

যদিওবা এটি আমাদের চাহিদামত কাজ করেনি, কিন্তু আমরা বুঝতে পারছি এটি কিভাবে কাজ করে।

গ্রীডি অবস্থায়(ডিফল্ট ভাবে) একটি কোয়ান্টিফায়ার যতবার সম্ভব এর পুনরাবৃত্তি ঘটায়।

রেগুলার এক্সপ্রেশন ইঞ্জিন যত সম্ভব ক্যারাক্টার pattern:.+ এর জন্য সংযোজন করে, এবং এরপর বাকী প্যাটার্ন না মিললে একটির পর একটি ক্যারাক্টার বাদ দিতে থাকে।

আমাদের টাস্কের জন্য আরো একটি বিষয় জানা উচিত। এই ক্ষেত্রে আমরা লেজি মোডের সাহায্য নিতে পারি।

লেজি মোড

লেজি মোড কোয়ান্টিফায়ার হল গ্রীডি মোড কোয়ান্টিফায়ারের বিপরীত। অর্থাৎ: "সবচেয়ে কম সংখ্যকবার পুনরাবৃত্তি"।

কোয়ান্টিফায়ারের পর প্রশ্নবোধক চিহ্ন সংযুক্ত করে pattern:'?' এটিকে চালু করা যায়, সুতরাং এরা হতে পারে pattern:*? অথবা pattern:+? এমনকি pattern:'?' এর জন্যpattern:??।

আমাদের এটি বুঝতে হবে: সাধারণত প্রশ্নবোধক চিহ্ন pattern:? নিজেই একটি কোয়ান্টিফায়ার এটি দ্বারা বুঝায় (শূন্য অথবা এক), কিন্তু যদি আমরা এটি অন্য কোয়ান্টিফায়ারের (এমনকি প্রশ্নবোধক চিহ্নের) পর সংযুক্ত করি এর অন্য অর্থ বোঝায় -- তখন এটি দ্বারা বুঝায় অনুসন্ধান গ্রীডি হতে লেজি মোডে পরিবর্তন হয়েছে।

pattern:/".+?"/g রেগুলার এক্সপ্রেশনটি আমাদের চাহিদামত কাজ করবে: অনুসন্ধানকৃত ফলাফল হবে match:"witch" এবং match:"broom":

let regexp = /".+?"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // witch, broom

পরিবর্তনটি বোঝার জন্য, আসুন ধাপগুলো একে একে বোঝার চেষ্টা করি।

১. প্রথম ধাপটি পূর্বের মত: ৩য় অবস্থানে প্যাটার্নটি pattern:'"' খুঁজে:

![](witch_greedy1.svg)

২. এর পরের স্টেপটিও একই: ইঞ্জিন ডটের pattern:'.' জন্য একটি মিল খুঁজে:

![](witch_greedy2.svg)

৩. এবং এর পরবর্তী অনুসন্ধানটি পূর্বের চেয়ে ভিন্ন হয়। কেননা আমরা এখন লেজি মোডে pattern:+? খুঁজ করছি, ইঞ্জিন ডটের জন্য একের অধিক মিল খুঁজবে না, অতঃপর এখন এটি এর পরবর্তী প্যাটার্নটি pattern:'"' মেলানোর চেষ্টা করবে:

![](witch_lazy3.svg)

এখন এখানে যদি উদ্ধৃতি চিহ্ন থাকত, তাহলে অনুসন্ধানটি শেষ হত, কিন্তু এর পরবর্তী অবস্থানে আছে `'i'`, সুতরাং কোন মিল হবেনা।

৪. অতঃপর রেগুলার এক্সপ্রেশন ইঞ্জিন পূর্বের ধাপটির পুনরাবৃত্তি করবে এবং আরো একবার উদ্ধৃতি চিহ্ন pattern:'"' এর সাথে মেলানোর চেষ্টা করবে:

![](witch_lazy4.svg)

আবারো মেলবে না। অতঃপর ধাপটি বার বার পুনরাবৃত্তি করবে...

৫. ...পরবর্তী প্যাটার্নের সাথে মিল হওয়া পর্যন্ত অনুসন্ধানটি চলবে:

![](witch_lazy5.svg)

৬. পরবর্তী অনুসন্ধানটি শেষ বর্তমান মিলপ্রাপ্ত অবস্থান থেকে শুরু হয় এবং নতুন আরো একটি মিল যুক্ত হয়:

![](witch_lazy6.svg)

এই উদাহরণে আমরা pattern:+? কোয়ান্টিফায়ারের জন্য লেজি মোড কিভাবে কাজ করে দেখলাম। pattern:*? এবং pattern:?? এই কোয়ান্টিফায়ারগুলোর জন্যও অনুরূপভাবে কাজ হয় -- রেগুলার এক্সপ্রেশন ইঞ্জিন কেবল পুনরাবৃত্তি করতে থাকে যদি বাকী প্যাটার্নগুলো অই অবস্থানে না মিলতে থাকে।

লেজি মোড কেবল কাজ করবে যদি কোয়ান্টিফায়ারের পর ? দেয়া হয়।

অন্যথায় কোয়ান্টিফায়ারগুলো গ্রীডি মোডে থাকে।

উদাহরণস্বরূপ:

alert( "123 456".match(/\d+ \d+?/) ); // 123 4

১. pattern:\d+ এই প্যাটার্নটি (গ্রীডি মোড) অনুসন্ধানে সর্বোচ্চ যতটা সম্ভব তত অঙ্কের সাথে মেলানোর চেষ্টা করে, অতঃপর এটি এর সাথে মেলে match:123 এবং এই প্যাটার্নের অনুসন্ধান শেষ হয়, কেননা পরবর্তী ক্যারাক্টারটি হল স্পেস pattern:' '। ২. এরপর প্যাটার্নে একটি স্পেস থাকে, এবং এটি এর সাথে মেলে। ৩. অতঃপর পরবর্তী প্যাটার্নটি হল pattern:\d+?। এখানে কোয়ান্টিফায়ারটি লেজি মোডে আছে, সুতরাং এটি একটি অঙ্কের match:4 সাথে মেলে এবং বাকী প্যাটার্নের সাথে মেলানোর চেষ্টা করে।

...কিন্তু এখানে `pattern:\d+?` এর পর আর কোন প্যাটার্ন নাই।

লেজি মোডে প্রয়োজন ছাড়া পুনরাবৃত্তি হয় না। অবশেষে প্যাটার্নটি সম্পন্ন হয়, এবং সাথে অনুসন্ধানও। সুতরাং আমরা ফলাফল হিসেব পায় `match:123 4`।

বর্তমানে রেগুলার এক্সপ্রেশন ইঞ্জিনগুলো দ্রুত কাজ করার জন্য নিজস্ব অপ্টিমাইজেশন অ্যালগরিদম ব্যবহার করে। সুতরাং এরা উপরে বর্ণিত ধাপগুলোর থেকে কিছুটা ভিন্নভাবে কাজ করে।

কিন্তু কিভাবে রেগুলার এক্সপ্রেশন কাজ করে এবং কিভাবে রেগুলার এক্সপ্রেশন লিখা যায় তা বোঝার জন্য, আমাদের এইসম্পর্কে না জানলেও হবে। অপ্টিমাইজেশনের জন্য এদের ইন্টারনালি ব্যবহার করা হয়।

জটিল রেগুলার এক্সপ্রেশনগুলো অপ্টিমাইজ করা কঠিন, সুতরাং এরা উপরে বর্ণিত নিয়মানুযায়ী কাজ করে।

ভিন্ন উপায়ে

রেগুলার এক্সপ্রেশনে একই কাজ বিভিন্ন উপায়ে করা সম্ভব।

এইক্ষেত্রে লেজি মোড ছাড়াও আমরা উদ্ধৃতি চিহ্নের উক্তিগুলো খুঁজে পেতে পারি এই প্যাটার্নের মাধ্যমে pattern:"[^"]+":

let regexp = /"[^"]+"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // witch, broom

এই প্যাটার্নটি pattern:"[^"]+" আমাদের সঠিক ফলাফল দেয়, কেননা এটি pattern:'"' একটি উদ্ধৃতি চিহ্ন খুঁজে অতঃপর pattern:[^"] এক বা একাধিক উদ্ধৃতি চিহ্ন নয় এমন ক্যারাক্টার খুঁজে, এবং শেষ উদ্ধৃতি চিহ্ন খুঁজ করে।

যখন রেগুলার এক্সপ্রেশন ইঞ্জিন pattern:[^"]+ এর মাধ্যমে বারবার মিল খুঁজে এটি শেষ উদ্ধৃতি চিহ্ন পর্যন্ত খুঁজ করে, এবং অনুসন্ধানটি শেষ হয়।

তবে আমাদের মনে রাখা উচিত, এটি লেজি কোয়ান্টাফায়ার মোডের বিকল্প না!

এটি সম্পূর্ণ ভিন্ন। আমাদের চাহিদামত আমরা এগুলোকে ব্যবহার করব।

চলুন আরেকটি উদাহরণ দেখি যেখানে লেজি কোয়ান্টিফায়ার কাজ করেনা কিন্ত অন্য উপায়টি কাজ করে।

উদাহরণস্বরূপ, আমরা এই <a href="..." class="doc"> ট্যাগের href অ্যাট্রিবিউট হতে লিঙ্ক গুলো খুঁজে পেতে চাই।

কোন রেগুলার এক্সপ্রেশনটি আমরা ব্যবহার করব?

আমাদের চিন্তায় প্রথমে এটি আসতে পারে: pattern:/<a href=".*" class="doc">/g.

চলুন এটি দেখি:

let str = '...<a href="link" class="doc">...';
let regexp = /<a href=".*" class="doc">/g;

// এটি কাজ করছে!
alert( str.match(regexp) ); // <a href="link" class="doc">

এটি কাজ করছে। কিন্তু একাধিক ট্যাগের জন্য এটি কিভাবে কাজ করবে?

let str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href=".*" class="doc">/g;

// ওওপস! দুইটি লিঙ্ক একটি মিলের জন্য!
alert( str.match(regexp) ); // <a href="link1" class="doc">... <a href="link2" class="doc">

এখন এই ফলাফলটি পূর্বের "witches" উদাহরণের মত ভুল। কোয়ান্টিফায়ারটি pattern:.* একাধিক ক্যারাক্টার নিয়ে নেয়।

অনুসন্ধানটি দেখতে অনেকটা এমন:

<a href="....................................." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">

এখন আমাদের প্যাটার্নটিকে লেজি কোয়ান্টিফায়ার pattern:.*? দিয়ে পরিবর্তন করি:

let str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href=".*?" class="doc">/g;

// এটি কাজ করছে!
alert( str.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

এখন এরা কাজ করছে, এখানে দুটি মিল আছে:

<a href="....." class="doc">    <a href="....." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">

...কিন্তু চলুন ভিন্ন টেস্টের জন্য আরেকটি ইনপুট নিয়ে দেখি:

let str = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
let regexp = /<a href=".*?" class="doc">/g;

// ভুল অনুসন্ধান!
alert( str.match(regexp) ); // <a href="link1" class="wrong">... <p style="" class="doc">

কিন্তু এবার এটি কাজ করল না। অনুসন্ধানে লিঙ্ক ব্যতীত <p...> সহ আরো অনেক কিছু যুক্ত হয়েছে।

কিন্তু এমন কেন?

চলুন দেখি এটি কিভাবে কাজ করল:

১. প্রথমে রেগুলার এক্সপ্রেশন match:<a href=" এটি দ্বারা খুঁজা শুরু করে। ২. অতঃপর এটি pattern:.*? এর মাধ্যমে খুঁজ চালিয়ে যায়: (লেজি মোডে!) একটি ক্যারাক্টার নেয়, pattern:" class="doc"> এটির জন্য কোন মিল খুঁজে পায় কিনা দেখে (কোন মিল পায় না)। ৩. অতঃপর pattern:.*? এর জন্য আরো একটি ক্যারাক্টার নেয়, এবং এভাবেই চলতে থাকে... যতক্ষণ না এটি match:" class="doc"> এর সাথে মিল হয়।

কিন্ত মূল সমস্যাটি হল: <a...> এই লিঙ্কের পর আরো একটি ট্যাগ <p> আছে। কিন্তু আমরা এটি চাই না।

নিচের ছবিটি দেখুন এরা টেক্সটের সাথে কিভাবে মিল হচ্ছে:

<a href="..................................." class="doc">
<a href="link1" class="wrong">... <p style="" class="doc">

সুতরাং, আমরা এই প্যাটার্নটির খুঁজ করি <a href="...something..." class="doc">, কিন্তু লেজি এবং গ্রীডি উভয়ই মোডে এটি সঠিক ফলাফল দেয় না।

সঠিক পদ্ধতিটি হতে পারে: pattern:href="[^"]*"। এটি href অ্যাট্রিবিউট শেষ হওয়ার পূর্বে পর্যন্ত এর মধ্যকার সকল ক্যারাক্টার নেয়, যা আমাদের দরকার।

সঠিক এই উদাহরণটি দেখুন:

let str1 = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
let str2 = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href="[^"]*" class="doc">/g;

// এটি কাজ করছে!
alert( str1.match(regexp) ); // নাল, কোন মিল নেই, যা সঠিক
alert( str2.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

সারাংশ

দুটি মোডে কোয়ান্টিফায়ার কাজ করে:

গ্রীডি : রেগুলার এক্সপ্রেশন ইঞ্জিন ডিফল্টভাবে কোয়ান্টিফায়ারকে যত বেশী সম্ভব এর পুনরাবৃত্তি করে। উদাহরণস্বরূপ, pattern:\d+ সকল সম্ভাব্য অঙ্কের সাথে মিলে। যখন আর কোন কিছুর সাথে মিল খুঁজে পায় না (স্ট্রিং শেষ অথবা আর কোন অঙ্ক থাকে না), তারপর এটি বাকী প্যাটার্নের সাথে মিল খুঁজে। আর যদি কোন মিল না থাকে তাহলে পুনরাবৃত্তিকৃত ফলাফলটিকে কমাতে থাকে এবং আবার মেলানোর চেষ্টা করে।

লেজি : কোয়ান্টিফায়ারের পরে প্রশ্নবোধক চিহ্ন pattern:? দিলে এই মোডটি চালু হয়। রেগুলার এক্সপ্রেশন ইঞ্জিন কোয়ানটিফায়ারের পুনরাবৃত্তির পূর্বে বাকী প্যাটার্নটি মেলানোর চেষ্টা করে।

এছাড়াও আমরা দেখেছি, গ্রীডি অনুসন্ধানের জন্য লেজি মোড "প্যানাসিয়া বা সর্বসব" না। এর পরিবর্তে গ্রীডি অনুসন্ধানের জন্য এই প্যাটার্নটিও pattern:"[^"]+" যথেষ্ট কাজের।