کمیت کننده های حریص و تنبل

کمیت سازها در نگاه اول بسیار ساده هستند، اما در واقع می توانند مشکل ساز باشند.

اگر بخواهیم به دنبال چیزی پیچیده تر از /d+/ باشیم، باید بفهمیم که چگونه جستجو به خوبی کار می کند.

بیایید کار زیر را به عنوان مثال در نظر بگیریم.

ما یک متن داریم و باید همه نقل قول ها را با علامت های guillemet جایگزین کنیم: «.» . آنها برای تایپوگرافی در بسیاری از کشورها ترجیح داده می شوند.

به عنوان مثال: "سلام، دنیا" باید به "سلام، دنیا" تبدیل شود. نقل قول های دیگری نیز وجود دارد، مانند "Witaj, świecie!"(لهستانی) یا 「你好，世界」 (چینی)، اما برای وظیفه خود بیایید « را انتخاب کنیم.» .

اولین کاری که باید انجام دهیم این است که رشته های نقل قول شده را پیدا کنیم و سپس می توانیم آنها را جایگزین کنیم.

یک عبارت منظم مانند /".+"/g (یک نقل قول، سپس چیزی، سپس نقل قول دیگر) ممکن است مناسب به نظر برسد، اما اینطور نیست!

... ما می توانیم ببینیم که آنطور که در نظر گرفته شده کار نمی کند!

به جای یافتن دو کبریت "جادوگر" و "جارو"، یکی را پیدا می کند: "جادوگر" و "جارو" او.

می توان آن را به عنوان "طمع علت همه بدی ها" توصیف کرد.

جستجوی حریصانه

برای یافتن یک مطابقت، موتور عبارت منظم از الگوریتم زیر استفاده می کند:

• برای هر موقعیت در رشته
  • سعی کنید الگو را در آن موقعیت مطابقت دهید.
  • اگر مطابقت وجود ندارد، به موقعیت بعدی بروید.

  این کلمات رایج مشخص نمی کنند که چرا regexp شکست می خورد، بنابراین بیایید نحوه عملکرد جستجو برای الگوی ".+" را توضیح دهیم.

  اولین کاراکتر الگو یک نقل قول است " .

  موتور عبارت منظم سعی می کند آن را در موقعیت صفر رشته منبع یک "جادوگر" و "جاروب" او یک پیدا کند، اما وجود دارد، بنابراین بلافاصله هیچ تطبیقی وجود ندارد.

  سپس پیشرفت می کند: به موقعیت های بعدی در رشته منبع می رود و سعی می کند اولین کاراکتر الگو را در آنجا پیدا کند، دوباره شکست می خورد و در نهایت نقل قول را در موقعیت 3 پیدا می کند:

  نقل قول شناسایی می شود و سپس موتور سعی می کند برای بقیه الگوی مطابقت پیدا کند. سعی می کند ببیند که آیا بقیه رشته موضوع مطابق با .+ است یا خیر.

  در مورد ما کاراکتر الگوی بعدی .(یک نقطه). این نشان دهنده "هر کاراکتری به جز یک خط جدید" است، بنابراین حرف رشته بعدی "w" متناسب است:

  سپس به دلیل کمیت .+ نقطه تکرار می شود. موتور عبارت منظم یکی پس از دیگری به تطابق می افزاید.

  …تا کی؟همه کاراکترها با نقطه مطابقت دارند، بنابراین فقط زمانی متوقف می شود که به انتهای رشته برسد:

  اکنون موتور تکرار .+ را به پایان رساند و سعی می کند کاراکتر بعدی الگو را پیدا کند. این نقل قول است. اما یک مشکل وجود دارد: رشته تمام شده است، هیچ کاراکتری وجود ندارد!

  موتور بیان منظم می فهمد که خیلی زیاد طول کشید.+ و شروع به عقب نشینی می کند.

  به عبارت دیگر ، مسابقه را برای یک کمیت توسط یک کاراکتر کوتاه می کند:

  اکنون فرض می کند که+ قبل از پایان رشته یک کاراکتر به پایان می رسد و سعی می کند بقیه الگوی را از آن موقعیت مطابقت دهد.

  اگر یک نقل قول در آنجا وجود داشته باشد ، جستجو به پایان می رسد ، اما آخرین شخصیت "E" است ، بنابراین هیچ تطبیقی وجود ندارد.

  … بنابراین موتور تعداد تکرارها را کاهش می دهد.+ توسط یک شخصیت دیگر:

  نقل قول "" "با" n "مطابقت ندارد.

  موتور عقب مانده است: باعث کاهش تعداد تکرار برای '' می شود. تا بقیه الگوی (در مورد ما "") مطابقت داشته باشد:

  مسابقه کامل است.

  بنابراین مسابقه اول "جادوگر" و "جارو" او است. اگر عبارت معمولی دارای پرچم G باشد ، جستجو از جایی که مسابقه اول به پایان می رسد ادامه خواهد یافت. هیچ نقل قول دیگری در بقیه رشته ها وجود ندارد ، بنابراین نتیجه بیشتری نیست.

  این احتمالاً چیزی نیست که ما انتظار داشتیم ، بلکه اینگونه کار می کند.

  در حالت حریص (به طور پیش فرض) یک شخصیت کمیت تا حد ممکن تکرار می شود.

  موتور REGEXP به اندازه بسیاری از کاراکترها که می تواند به مسابقه اضافه می کند.+ ، و سپس آن را یک به یک کوتاه می کند ، اگر بقیه الگوی مطابقت نداشته باشد.

  برای کار ما چیز دیگری می خواهیم. این جایی است که یک حالت تنبل می تواند کمک کند.

  حالت تنبل

  حالت تنبل اندازه گیری ها برعکس با حالت حریص است. این بدان معنی است: "حداقل تعداد بار را تکرار کنید".

  ما می توانیم با قرار دادن یک علامت سؤال "آن را فعال کنیم؟"بعد از کمیت ، به طوری که *شود؟یا +؟یا حتی؟برای '؟'بشر

  برای روشن کردن امور: معمولاً یک علامت سوال؟یک کمیت به خودی خود (صفر یا یک) است ، اما اگر بعد از کمیت دیگر (یا حتی خود) اضافه شود ، معنای دیگری دارد - حالت تطبیق را از حریص به تنبل تغییر می دهد.

  regexp /".+؟"/g مطابق آنچه در نظر گرفته شده است کار می کند: "جادوگر" و "جارو" را پیدا می کند:

  برای درک واضح تغییر ، اجازه دهید مرحله به مرحله جستجو را ردیابی کنیم.

  مرحله اول یکسان است: این الگوی شروع "" را در موقعیت 3 می یابد:

  مرحله بعدی نیز مشابه است: موتور مسابقه ای را برای نقطه پیدا می کند.:

  و اکنون جستجو متفاوت است. از آنجا که ما یک حالت تنبل برای +داریم؟، موتور سعی نمی کند یک بار دیگر با یک نقطه مطابقت داشته باشد ، اما متوقف می شود و سعی می کند با بقیه الگوی "" هم اکنون مطابقت داشته باشد:

  اگر در آنجا نقل قول وجود داشته باشد ، جستجو به پایان می رسد ، اما "من" وجود دارد ، بنابراین هیچ مسابقه ای وجود ندارد.

  سپس موتور بیان منظم تعداد تکرارها را برای DOT افزایش می دهد و یک بار دیگر تلاش می کند:

  دوباره شکستسپس تعداد تکرارها دوباره و دوباره افزایش می یابد ...

  ... تا زمان مسابقه برای بقیه الگوی یافت می شود:

  جستجوی بعدی از پایان مسابقه فعلی شروع می شود و یک نتیجه دیگر به دست می آورد:

  در این مثال دیدیم که حالت تنبل برای +چگونه کار می کند؟بشراندازه گیری *؟و ؟؟به روش مشابه کار کنید - موتور REGEXP فقط در صورتی که بقیه الگوی نتوانند در موقعیت داده شده مطابقت داشته باشند ، تعداد تکرارها را افزایش می دهد.

  تنبلی فقط برای کمیته فعال است؟بشر

  سایر کمیته ها حریص هستند.

  الگوی d+ سعی می کند با رقم های زیادی که می تواند مطابقت داشته باشد (حالت حریص) ، بنابراین 123 را پیدا می کند و متوقف می شود ، زیرا شخصیت بعدی یک فضا است.

  سپس فضایی در الگوی وجود دارد ، مطابقت دارد.

  سپس d+وجود دارد؟بشرکمیته در حالت تنبل است ، بنابراین یک رقم 4 را پیدا می کند و سعی می کند بررسی کند که آیا بقیه الگوی از آنجا مطابقت دارد یا خیر.

  ... اما هیچ چیز در الگوی بعد از d+وجود ندارد؟بشر

  حالت تنبل بدون نیاز هر چیزی را تکرار نمی کند. الگوی به پایان رسید ، بنابراین ما تمام شدیم. ما یک مسابقه 123 4 داریم.

  موتورهای بیان منظم مدرن می توانند الگوریتم های داخلی را بهینه کنند تا سریعتر کار کنند. بنابراین آنها ممکن است کمی متفاوت از الگوریتم شرح داده شده کار کنند.

  اما برای درک اینکه چگونه عبارات منظم کار می کنند و برای ساختن عبارات منظم ، لازم نیست در مورد آن بدانیم. آنها فقط در داخل برای بهینه سازی چیزها مورد استفاده قرار می گیرند.

  بهینه سازی های معمولی پیچیده دشوار است ، بنابراین جستجو ممکن است دقیقاً مطابق توضیحات کار کند.

  رویکرد جایگزین

  با استفاده از regexps ، اغلب بیش از یک راه برای انجام همین کار وجود دارد.

  در مورد ما می توانیم رشته های نقل شده بدون حالت تنبل را با استفاده از regexp "[^"]+"پیدا کنیم:

  regexp "[^"]+"نتایج صحیحی می دهد ، زیرا به دنبال نقل قول" "" "و به دنبال آن یک یا چند غیرقانونی [^"] و سپس نقل قول بسته است.

  هنگامی که موتور regexp به دنبال [^"]+ است که هنگام دیدار با نقل قول ، تکرارها را متوقف می کند ، و ما انجام می دهیم.

  لطفاً توجه داشته باشید که این منطق جایگزین اندازه گیری های تنبل نمی شود!

  این فقط متفاوت استمواقعی وجود دارد که به یک یا دیگری احتیاج داریم.

  بیایید مثالی را ببینیم که تعداد کمی از آنها تنبل شکست می خورند و این نوع درست کار می کند.