Skip to content

Latest commit

 

History

History
318 lines (197 loc) · 28.3 KB

article.md

File metadata and controls

318 lines (197 loc) · 28.3 KB

ধ্বংসাত্নক ব্যাকট্রাকিং (Catastrophic backtracking)

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

বেশিরভাগ ডেভলাপারই আগে বা পরে এই বিপর্যয়ের সম্মুখীন হন, কেননা এ ধরণের রেগুলার এক্সপ্রেশন লিখা সহজ। সাধারণত -- অনেক সময় এই রেগুলার এক্সপ্রেশনগুলো কাজ করে, কিন্তু কিছু নির্দিষ্ট স্ট্রিংয়ের জন্য এরা ১০০% সিপিউ ব্যবহারের মাধ্যমে "হ্যাং" হয়ে যায়।

এক্ষেত্রে ওয়েব ব্রাউজার স্ক্রিপ্টটিকে ধ্বংশ করে পুনরায় পেজটিকে রিলোড করার পরামর্শ দেয়। নিশ্চিতভাবে ব্যাপারটি ভালো না।

সার্ভার-সাইড জাভাস্ক্রিপ্টে এই ধরণের রেগুলার এক্সপ্রেশন সার্ভারের প্রসেস কে হ্যাং করে দেয়, যা আরো ভয়ানক! সুতরাং অবশ্যই আমাদের এই ব্যাপারটি জেনে রাখা উচিত..

উদাহরণ

মনে করুন আমাদের একটি স্ট্রিং আছে, এবং আমরা এটি শব্দ pattern:\w+ দ্বারা গঠিত কিনা যাচাই করতে চাই সেই সাথে প্রতিটির শেষে অপশনাল স্পেস pattern:\s? আছে কিনা যাচাই করব।

রেগুলার এক্সপ্রেশনে আমরা এটি সহজেই করতে পারি, একটি শব্দ নিয়ে তারপর একটি অপশনাল স্পেস pattern:\w+\s? এবং এটিকে বারবার পুনরাবৃত্তি করব * কোয়ান্টিফায়ারের সাহায্যে।

সুতরাং রেগুলার এক্সপ্রেশনটি হবে pattern:^(\w+\s?)*$, এটি দ্বারা যাচাই করা হচ্ছে লাইনের শুরুতে pattern:^ এবং pattern:$ শেষে শূন্য বা একাধিক শব্দ আছে কিনা।

যেমন:

let regexp = /^(\w+\s?)*$/;

alert( regexp.test("A good string") ); // true
alert( regexp.test("Bad characters: $@#") ); // false

এটি কাজ করছে। রেজাল্টটিও সঠিকভাবে দেয়। তবে, কিছু নির্দিষ্ট স্ট্রিংয়ের জন্য এটি প্রচুর সময় নিবে। সুতরাং জাভাস্ক্রিপ্ট ইঞ্জিন ১০০% সিপিউ ব্যবহারের মাধ্যমে "হ্যাং" হয়ে যাবে।

যদি আপনি নিচের উদাহরণটি রান করান, হয়তো আপনি কিছু দেখবেন না, তবে জাভাস্ক্রিপ্ট "হ্যাং" হয়ে যাবে। ওয়েব ব্রাউজারের ইভেন্ট, ইউ আই কাজ করা বন্ধ করে দিবে(তবে কিছু ব্রাউজারের স্ক্রল কাজ করতে পারে)। এবং কিছু সময় পর এটি পুনরায় পেজটিকে রিলোড করার পরামর্শ দিবে। সুতরাং এই ব্যাপারটি আপনার জেনে রাখা উচিত:

let regexp = /^(\w+\s?)*$/;
let str = "An input string that takes a long time or even makes this regexp to hang!";

// এটি অনেক সময় নিবে
alert( regexp.test(str) );

কিছু রেগুলার এক্সপ্রেশন ইঞ্জিন এই ধরণের সার্চ করতে পারে, তবে বেশিরভাগই পারেনা। ব্রাউজার ইঞ্জিন সাধারণত হ্যাং হয়ে যায়।

উদাহরণকে সহজীকরণ

এখানে কি ঘটছে? কেন রেগুলার এক্সপ্রেশন ইঞ্জিন "হ্যাং" হয়?

এটি বুঝার জন্য, চলুন সহজ একটি উদাহরণ দেখি: স্পেসটি বাদ দেন pattern:\s?। সুতরাং এটি হবে pattern:^(\w+)*$।

এবং, ব্যাপারটিকে আরো সুস্পষ্ট করে তুলতে, pattern:\w এর পরিবর্তে pattern:\d ব্যবহার করি। রেজাল্টের জন্য রেগুলার এক্সপ্রেশন ইঞ্জিন হ্যাং থাকবে, যেমন:

let regexp = /^(\d+)*$/;

let str = "012345678901234567890123456789z";

// এটি অনেক সময় নিবে (careful!)
alert( regexp.test(str) );

এই রেগুলার এক্সপ্রেশনের ভুলটি কোথায়?

প্রথমত, আমরা লক্ষ্য করছি আমাদের প্যাটার্নটি pattern:(\d+)* কিছুটা অদ্ভুত। কোয়ান্টিফায়ারটি pattern:* এখানে অপ্রয়োজনীয় মনে হচ্ছে। যদি আমরা সংখ্যা চাই, আমরা pattern:\d+ এটি ব্যবহার করতে পারি।

প্রকৃতপক্ষে, রেগুলার এক্সপ্রেশনটি আর্টিফিশিয়াল, পূর্বের উদাহরণে আমরা এটি দেখেছি। কিন্তু এটি কেন এত ধীরে কাজ করছে। চলুন আগে এটি বুঝি, এবং তারপর আমাদের কাছে উপরের উদাহরণটি আরো সুস্পষ্ট হবে।

subject:123456789z এর মধ্যে pattern:^(\d+)*$ এর দ্বারা অনুসন্ধানে কি ঘটে(সংক্ষিপ্তরূপটি আমাদের বুঝার সুবিধার্তে শেষে আমরা একটি অঙ্ক নয় এমন একটি ক্যারাক্টার subject:z সবার শেষে রেখেছি), কেন এটি এত সময় নেয়?

এখানে রেগুলার এক্সপ্রেশন ইঞ্জিন কিভাবে কাজ করছে:

১. প্রথমত, রেগুলার এক্সপ্রেশনটি প্যারেন্টেসিসের অংশটি একটি সংখ্যা pattern:\d+ অনুসন্ধান করে। কোয়ান্টিফায়ারটি pattern:+ ডিফল্টভাবে গ্রীডি, সুতরাং এটি সকল অঙ্ক নিবে:

```
\d+.......
(123456789)z
```

সকল অঙ্ক নেয়ার পর, `pattern:\d+` অনুসন্ধানকৃত মানটি (`match:123456789`)।

এরপর এটি `pattern:(\d+)*` কোয়ান্টিফায়ার প্রয়োগ করবে, কিন্ত এখানে আর কোন অঙ্ক নেই, সুতরাং * কোন কিছু দিবে না।

প্যাটার্নের শেষ অংশটি হল `pattern:$`, কিন্তু স্ট্রিংয়ের শেষ ক্যারাক্টারটি হল `subject:z`, সুতরাং এখানে কোন মিল পাবে না:

```
           X
\d+........$
(123456789)z
```

২. যেহেতু কোন মিল খুঁজে পাবে না, গ্রীডি কোয়ান্টিফায়ার pattern:+ সুতরাং এটি আবার ক্যারাক্টারকে কমাতে থাকবে, সুতরাং এর অবস্থানটি পূর্ববর্তী ক্যারাক্টারে আসবে।

এখন `pattern:\d+` শেষ ক্যারাক্টারটি বাদে সকল ক্যারাক্টার নিবে (`match:12345678`):
```
\d+.......
(12345678)9z
```

৩. অতঃপর ইঞ্জিন পরবর্তী অবস্থান (match:12345678) থেকে পুনরায় অনুসন্ধান চালাবে।

`pattern:(\d+)*` কোয়ান্টিফায়ারটি আবার প্রয়োগ হবে -- এটি আরো একটি সংখ্যার `pattern:\d+` সাথে মিলে, সংখ্যাটি `match:9`:

```

\d+.......\d+
(12345678)(9)z
```

ইঞ্জিন প্যাটার্নের `pattern:$` শেষ অংশটি আবার মিলাতে চেষ্টা করে, কিন্তু আবারো মিলবে না, কেননা শেষ ক্যারাক্টারটি হল `subject:z`:

```
             X
\d+.......\d+
(12345678)(9)z
```

৪. আবারো কোন মিল খুঁজে পাবে না, সুতরাং ইঞ্জিন আবারো ব্যাকট্রাকিং চালাবে, এবং সংখ্যার পুনরাবৃত্তি কমাবে। ব্যাকট্রাকিং সাধারণত এভাবে কাজ করে: শেষ গ্রীডি কোয়ান্টিফায়ার যত সম্ভব সংখ্যার পুনরাবৃত্তি কমাবে। তারপর এর পূর্ববর্তী কোয়ান্টিফায়ারের জন্য কমাবে, এভাবেই চলতে থাকে।

সকল সম্ভাব্যতা যাচাইয়ের চেষ্টা করবে। যেমন:

প্রথম সংখ্যাটিতে `pattern:\d+` ৭টি অঙ্ক আছে, এবং পরবর্তী সংখ্যাটিতে ২টি অঙ্ক আছে:

```
             X
\d+......\d+
(1234567)(89)z
```

প্রথম সংখ্যাটিতে `pattern:\d+` ৭টি অঙ্ক আছে, এবং পরবর্তী ২টি সংখ্যাতে ১টি করে অঙ্ক আছে:

```
               X
\d+......\d+\d+
(1234567)(8)(9)z
```

প্রথম সংখ্যাটিতে `pattern:\d+` ৬টি অঙ্ক আছে, এবং পরবর্তী সংখ্যাতে ৩টি অঙ্ক আছে:

```
             X
\d+.......\d+
(123456)(789)z
```

প্রথম সংখ্যাটিতে `pattern:\d+` ৭টি অঙ্ক আছে, এবং পরবর্তী ২টি সংখ্যাতে ২টি এবং ১টি করে অঙ্ক আছে:

```
               X
\d+.....\d+ \d+
(123456)(78)(9)z
```

...এভাবেই চলতে থাকে।

এখানে 123456789 অঙ্কগুলোকে বিভিন্ন উপায়ে সাজানোর পদ্ধতি আছে। মোট উপায়টি হল, 2n-1, যেখানে n হল সেটটির অঙ্কের সংখ্যা।

  • 123456789 এ n=9, এর মোট ৫১১টি কম্বিনেশন আছে।
  • আরো বড় সিক্যুয়েন্সের জন্য n=20 মোট ১০৪৮৫৭৫ টি কম্বিনেশন আছে।
  • n=30 এর জন্য - আরো হাজার গুণ (১০৭৩৭৪১৮২৩ টি কম্বিনেশন)।

ইঞ্জিন প্রতিটি কম্বিনেশন মেলাতে চেষ্টা করে, তাই এটি এত সময় নেয়।

পুনরায় শব্দ এবং স্ট্রিং

একই ব্যাপারটি ঘটে আমাদের প্রথম উদাহরণে, যখন আমরা প্যাটার্নটি দ্বারা pattern:^(\w+\s?)*$ স্ট্রিংয়ে subject:An input that hangs! শব্দের অনুসন্ধান চালায়।

কেননা আমরা শব্দকে pattern:\w+ এক বা একাধিক উপায়ে প্রকাশ করতে পারি:

(input)
(inpu)(t)
(inp)(u)(t)
(in)(p)(ut)
...

একজন মানুষ সহজেই বুঝতে পারে এখানে কোন মিল নেই, কেননা স্ট্রিংটি একটি আশ্চর্যবোধক চিহ্ন দ্বারা ! শেষ হয়, কিন্তু আমাদের প্যাটার্নটি সবার শেষে pattern:\w একটি বর্ণ বা স্পেস pattern:\s খুঁজে। কিন্ত ইঞ্জিন এটি বুঝতে পারেনা।

pattern:(\w+\s?)* এই প্যাটার্নটি স্ট্রিংয়ের সকল সম্ভাব্যতা এমনকি স্পেসসহ pattern:(\w+\s)* এবং স্পেসছাড়া pattern:(\w+)* সবকে যাচাই করে(কেননা স্পেস হল pattern:\s? অপশনাল)। এখানে অনেক কম্বিনেশন আছে(সংখ্যার উদাহরণে আমরা দেখেছি), এরা প্রচুর সময় নেয়।

এক্ষেত্রে আমরা কি করতে পারি?

আমরা কি লেজি মোডে অনুসন্ধান করব?

দুর্ভাগ্যবশত, এটি কাজ করবে না: যদি আমরা pattern:\d+ এর পরিবর্তে pattern:\d+? ব্যবহার করি, তাও রেগুলার এক্সপ্রেশন ইঞ্জিন হ্যাং হয়ে যাবে। কম্বিনেশন পরিবর্তন হবে, কিন্তু সম্পূর্ন সংখ্যার পরিবর্তন হবে না।

কিছু রেগুলার এক্সপ্রেশন ইঞ্জিন কৌশলে সসীম অটোমেশন যাচাই করে, যাতে সকল কম্বিনেশন যাচাই করতে না হয়, এর ফলে এরা কিছুটা দ্রুত কাজ করে, কিন্তু সকল ইঞ্জিন সকল টেস্টের জন্য এভাবে যাচাই করতে পারে না।

কিভাবে সমাধান করতে পারি?

সমস্যাটি সমাধানের দুটি পদ্ধতি আছে।

প্রথমটি হল আমরা যথাযথ সম্ভব কম্বিনেশনকে কমাব।

চলুন প্যাটার্নটি আবার লিখি pattern:^(\w+\s)*\w* - প্রথমে আমরা খুঁজব শব্দের শেষে কোন স্পেস আছে কিনা pattern:(\w+\s)*, এবং সর্বশেষে একটি(অপশনাল) শব্দ pattern:\w*।

এই প্যাটার্নটি পূর্বের মত(একই মিল খুঁজে) এবং এটি ভালোভাবে কাজ করে:

let regexp = /^(\w+\s)*\w*$/;
let str = "An input string that takes a long time or even makes this regex to hang!";

alert( regexp.test(str) ); // false

সমস্যাটি কিভাবে দূরীভূত হল?

কেননা এখন স্পেসটি বাধ্যতামূলক।

পূর্ববর্তী রেগুলার এক্সপ্রেশনে, যদি আমরা স্পেসটি বাদ দেই এটি হবে এমন pattern:(\w+)*, যা দ্বারা একটি শব্দের একাধিক \w+ কম্বিনেশন হবে।

সুতরাং subject:input এটি পুনরাবৃত্তির সময় pattern:\w+ দুইবার মিলবে, যেমন:

\w+  \w+
(inp)(ut)

কিন্ত আমাদের নতুন প্যাটার্নটিতে আমরা স্পেস দ্বারা শব্দকে নির্দিষ্ট করে দিচ্ছি: pattern:(\w+\s)*! subject:input স্ট্রিংটি দ্বিতীয়বার পুনরাবৃত্তিতে মিলবে না pattern:\w+\s, কেননা এখন স্পেসটি বাধ্যতামূলক।

এর সাহায্যে আমরা একাধিক অপ্রয়োজনীয় কম্বিনেশন কে এড়াতে পারি।

প্রিভেন্ট ব্যাকট্রাকিং

পুনরায় রেগুলার এক্সপ্রেশন লিখা সবসময় সহজ নয়। উপরের উদাহরণে এটি পরিবর্তন করা সহজ ছিল, কিন্তু সবসময় আমাদের কাছে এটি সহজবোধ্য থাকে না।

এছাড়াও, পুনরায় লিখিত রেগুলার এক্সপ্রেশন আরো জটিল হয়, এবং এটি ভালোও না। এমনিতেও রেগুলার এক্সপ্রেশনসমূহ যথেষ্ট জটিল।

তবে, আমাদের কাছে আরো একটি উপায় আছে। যার মাধ্যমে আমরা কোয়ান্টিফায়ারের জন্য ব্যাকট্রাকিং কে বাধা দিতে পারি।

তবে রেগুলার এক্সপ্রেশন ইঞ্জিন এমন সব সম্ভাব্যতা নিয়ে চেষ্টা করে, কম্বিনেশনগুলো ভুল তা মানুষ সহজেই বুঝতে পারে।

যেমন রেগুলার এক্সপ্রেশনটি pattern:(\d+)*$ প্রোগ্রামারদের কাছে সুষ্পষ্ট, এটির pattern:+ ব্যাকট্রাকিং করা উচিত নয়। যদি আমরা এটিকে pattern:\d+ দুটি pattern:\d+\d+ প্যাটার্নে বিভক্ত করি, তারপরও কোন পরিবর্তন হবে না:

\d+........
(123456789)!

\d+...\d+....
(1234)(56789)!

এবং আমাদের মূল উদাহারণটিতে pattern:^(\w+\s?)*$ আমরা চাই ব্যাকট্রাকিংকে বাদ দিতে pattern:\w+। সুতরাং: pattern:\w+ এটি সম্ভাব্য পুরো শব্দের সাথে মিলবে। পুনরাবৃত্তি কে না কমিয়ে আমরা pattern:\w+ কে pattern:\w+\w+ দুটি শব্দে বিভক্ত করতে পারি।

আধুনিক রেগুলার এক্সপ্রেশ ইঞ্জিন গুলো পসেসিভ কোয়ান্টিফায়ার সমর্থন করে। পসেসিভের কোয়ান্টিফায়ারের জন্য কোয়ান্টিফায়ারের পরে pattern:+ যোগ করলে হবে। ব্যাকট্রাকিংকে থামাতে আমরা pattern:\d+ এর বদলে pattern:\d++ লিখব।

পসেসিভের কোয়ান্টিফায়ার সমূহ আরো সহজ। এরা ব্যাকট্রাকিং ছাড়া যতটা সম্ভব মেলাতে চেষ্টা করে। ব্যাকট্রাকিং ছাড়া এই অনুসন্ধানটি আরো সহজবোধ্য।

এদেরকে "এটমিক ক্যাপচারিং গ্রুপও" বলা হয় - প্যারেন্টেসিসের ভিতর ব্যাকট্রাকিংয় রোধের একটি উপায়।

...কিন্তু দুর্ভাগ্যবশত, জাভাস্ক্রিপ্টে এটি সাপোর্ট করে না।

তবে লুকঅ্যাহেডের মাধ্যমে আমরা অনূরূপ কাজ করতে পারি।

Lookahead to the rescue!

এখন আমরা আমাদের মূল সমস্যাটির আলোচনা করব। আমরা এমন একটি কোয়ান্টিফায়ার চাই, যেমন pattern:+ যেন ব্যাকট্রাক না করে, কেননা অনেক সময় ব্যাকট্রাকিং কাজে আসে না।

pattern:(?=(\w+))\1 প্যাটার্নটি ব্যাকট্রাকিং ছাড়াই সর্বোচ্চ সংখ্যক pattern:\w পুনরাবৃত্তিকে ক্যাপচার করে। অবশ্য, আমরা pattern:\w এর পরিবর্তে অন্যান্য প্যাটার্নও নিতে পারি।

এটি দেখতে যদিও বিদঘুটে, কিন্তু আসলেই এটি সাধারণ একটি পরিবর্তন।

চলুন প্যাটার্নটি বুঝার চেষ্টা করি:

  • লুকঅ্যাহেড pattern:?= বর্তমান পজিশন থেকে সবচেয়ে দীর্ঘ শব্দটি pattern:\w+ খুঁজে।
  • প্যারেন্টেসিসের pattern:?=... ভিতরের কন্টেন্ট pattern:?=... ইঞ্জিন সংরক্ষণ করে না, সুতরাং আমরা pattern:\w+ কে আরো একটি প্যারেন্টেসিসের মধ্যে রাখি। এখন ইঞ্জিন কন্টেন্টসমূহকে সংরক্ষণ করে
  • ...এবং আমরা একে প্যাটার্নে রেফারেন্স হিসেবে ব্যবহার করি pattern:\1।

অর্থাৎ: আমরা পরবর্তী ক্যারাক্টারগুলো দেখছি এবং যদি কোন শব্দ pattern:\w+ থাকে, তারপর pattern:\1 এটির সাথে মিলবে।

কেন? কেননা লুকঅ্যাহেড সম্পূর্ন শব্দকে pattern:\w+ খুঁজে এবং আমরা এটিকে প্যাটার্নে ক্যাপচার করি pattern:\1। এটি দ্বারা আসলে আমরা পসেসিভ কোয়ান্টিফায়ারকে pattern:+ বাস্তবায়িত করছি। এটি দ্বারা কোন একটি অংশ ক্যাপচার না হয়ে সম্পূর্ন শব্দটি ক্যাপচার হচ্ছে pattern:\w+।

যেমন, subject:JavaScript এই শব্দটি কেবল match:Java এর সাথে ম্যাচ করবে না, এবং বাকী প্যাটার্নের match:Script সাথে মিল খুঁজে বাদ দেয়।

এখানে প্যাটার্ন দুটির তুলনা দেখুন:

alert( "JavaScript".match(/\w+Script/)); // JavaScript
alert( "JavaScript".match(/(?=(\w+))\1Script/)); // null
  1. প্রথম প্যাটার্নটিতে pattern:\w+ প্রথমে সম্পুর্ন শব্দটি subject:JavaScript ক্যাপচার করে এবং তারপর pattern:+ ব্যাকট্রাকিং করে শেষ হতে, এবং বাকী প্যাটার্নটি মেলানোর চেষ্টা করে, এবং শেষ পর্যন্ত মিলে যায় (যখন pattern:\w+ প্যাটার্নটি match:Java এর সাথে মিলে)।
  2. দ্বিতীয় লুকঅ্যাহেড প্যাটার্নটি pattern:(?=(\w+)) শব্দটি subject:JavaScript খুঁজে, এবং এটিও প্যাটার্নে pattern:\1 সংযুক্ত হয়, সুতরাং এর পরে আর subject:Script খুঁজে পায় না।

আমরা pattern:(?=(\w+))\1 এই প্যাটার্নে pattern:\w এর পরিবর্তে আরো জটিল এক্সপ্রেশন রাখতে পারি, যদি আমরা pattern:+ এর ব্যাকট্রাকিং রোধ করতে চায়।

পসেসিভ কোয়ান্টফায়ার এবং লুকঅ্যাহেড সম্পর্কে আরো বিস্তারিত জানতে এই আর্টিকেলগুলো দেখুন  [Regex: Emulate Atomic Grouping (and Possessive Quantifiers) with LookAhead](http://instanceof.me/post/52245507631/regex-emulate-atomic-grouping-with-lookahead) এবং [Mimicking Atomic Groups](http://blog.stevenlevithan.com/archives/mimic-atomic-groups)।

চলুন আমাদের প্রথম উদাহরণটি লুকঅ্যাহেড এর সাহায্যে আবার লিখি যা ব্যাকট্রাকিং রোধ করে:

let regexp = /^((?=(\w+))\2\s?)*$/;

alert( regexp.test("A good string") ); // true

let str = "An input string that takes a long time or even makes this regex to hang!";

alert( regexp.test(str) ); // ভুল, এবং দ্রুত কাজ করছে!

এখানে আমরা এর pattern:\1 পরিবর্তে pattern:\2 ব্যবহার করেছি, কেননা এখানে আরো একটি অতিরিক্ত একটি প্যারেন্টেসিস আছে। ক্রমের ঝামেলা এড়াতে আমরা গ্রুপের নাম দিতে পারি, যেমন pattern:(?<word>\w+)।

// parentheses are named ?<word>, referenced as \k<word>
let regexp = /^((?=(?<word>\w+))\k<word>\s?)*$/;

let str = "An input string that takes a long time or even makes this regex to hang!";

alert( regexp.test(str) ); // false

alert( regexp.test("A correct string") ); // true

এই আর্টিকেলে বর্ণিত সমস্যাটিকে বলা হয় "catastrophic backtracking"।

আমরা এখানে দুটি উপায় দেখেছি কিভাবে সমস্যাটি সমাধান করা যায়:

  • রেগুলার এক্সপ্রেশন পুনরায় লিখে কম্বিনেশনের সংখ্যা কমানো।
  • প্রিভেন্ট ব্যাকট্রাকিং।