1 Тема від fromes

  • fromes
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 09.04.2020
  • Повідомлень: 9
    • Репутація: 0

Тема: Catastrophic Backtracking в регулярному виразі

При написанні невеликого парсеру пошукової системи виникав проблема з регулярним виразом:

Є регулярний вираз для парсинга HTML сторінки:

var pattern = @
<div class="A(.*?)(href=")(?<href>.*?)"(.*?)<div class="B">(?<anchor>.*?)<.*?><div class="C yDYNvb">(?<sniplet>.*?)</div>

при парсінгу сторінки все працює.

Але якщо відбувається зміна дизайну на сторінці, наприклад: <div class="B замінюється на <div class="K , то відбувається Catastrophic backtracking і починає зависати парсер.

Завдання: підкоригувати регулярний вираз так, щоб у випадку зміни дизайну, сторінки не відбувалося повернення Catastrophic backtracking, а парсер просто переставав шукати (Нічого не знайдено або помилка)


Заздалегідь вдячний за допомогу

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Catastrophic Backtracking в регулярному виразі

Для початку, не варто парсити HTML regexp-ами.
Тепер по поверненнях у пошуку. Вони стаються, коли ви маєте вираз, який може по-різному відповідати частині регулярки, а потім - щось фіксоване. Фіксованим, вочевидь, є <div class="B">. Вам, відповідно, треба зробити так, щоб початок мав менше варіантів. Ви шукаєте

<div class="A

за яким на певній відстані (.*?) іде 

href="

далі купка символів (.*?), які збираються в <href>
потім лапки, знову багато символів (.*?) і отой

<div class="B">

Халепа в тому, що кількість символів в усіх групах невизначена, вони можуть як завгодно розподілятися і створюють оті повернення. Найочевидніше обмеження, яке я бачу - 

(?<href>[^"]*?)

Це не дозволить регулярці вийти за межі href-а і, відповідно, суттєво обмежить пошук.
Але, ще раз, не слід так робити.

Ну і принагідно - це яка мова програмування? Не плюси ж.

Подякували: leofun011

koala вебсайт

3 Відповідь від fromes

  • fromes
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 09.04.2020
  • Повідомлень: 9
    • Репутація: 0

Re: Catastrophic Backtracking в регулярному виразі

Дуже дякую за відповідь.

Забув сказати, що тільки вчуся.

Перечитав багато інформації про регулярні вирази і з питань Catastrophic backtracking.
Але стільки інформації, що не можу правильно зрозуміти суть, в голові всі ці символи вже так заплуталися, що немає сил.
Тому і попросив допомоги у знаючих людей.

Ну і принагідно - це яка мова програмування? Не плюси ж.

Програма створюється на С #

Але мені дали завдання створити регулярний вираз в RegEx для парсинга сторінок, на прикладі звичайного пошуку Google.

Я був би вдячний за допомогу в коригуванні вираження.

Мій приклад: 

<div class="KJDcUb(.*?)(href=")(?<href>.*?)"(.*?)<div class="PpBGzd YcUVQe">(?<anchor>.*?)<.*?><div class="MUxGbd yDYNvb">(?<sniplet>.*?)</div>

в HTML коді сторінки пошука працює (збирає урл, назву и опис)

але на прикладі зміни дизайну в HTML сторінки змінили 

<div class="PpBGzd YcUVQe">

на 

<div class="ApBGzd YcUVQe">

і на моїй регулярке відбувається повернення Catastrophic backtracking. таке ж може статися і при зміні будь-якого <div class="KJDcUb" чи  <div class="MUxGbd yDYNvb"> , які є в моїй регулярке


Тому, якщо не важко, прошу допомоги: покажіть приклад моєї ж регулярки зі змінами, які потрібно зробити для запобігання повернення Catastrophic backtracking  (Краще воно напише що, не знайдено).

На вашому прикладі (зміненої моєї регулярки) я зрозумію, що не так.
Дякую ще раз. Вибачте за дурні питання, якщо що.

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Catastrophic Backtracking в регулярному виразі

Ні, не можу. Бо ваша регулярка - то ваша регулярка. А зі змінами вона буде вже не вашою, і шукатиме щось інше. Розумієте?
Можливо, я б зміг краще написати регулярку за вашою умовою, але, наскільки я зрозумів, вона цілком таємна, і ви з нами нею не поділитеся.

koala вебсайт

5 Відповідь від fromes

  • fromes
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 09.04.2020
  • Повідомлень: 9
    • Репутація: 0

Re: Catastrophic Backtracking в регулярному виразі

Мені дали завдання створити регулярку на основі виданого шаблону в RegEx для парсинга сторінок в Гугл, але поки я в регулярних виразах новачок і дуже багато не зрозуміло в них, хоч і прочитав n-під кількість інформації про них

Шаблон регулярного виразу, який мені видали для коригування:

<div class="KJDcUb(.*?)(href=")(?<href>.*?)"(.*?)<div class="PpBGzd YcUVQe">(?<anchor>.*?)<.*?><div class="MUxGbd yDYNvb">(?<sniplet>.*?)</div>

Завдання підкоригувати її так, щоб при зміні дизайну сторінки (змінили <div class = "PpBGzd YcUVQe"> на <div class = "ApBGzd YcUVQe">) не відбувається нескінченний бектракінг, а просто було "не знайдено або помилка"

Приклад коду сторінки, на якій вона працює:

▼Прихований текст

Приклад зміненої сторінки:

▼Прихований текст

дякую за допомогу

6 Відповідь від fromes

  • fromes
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 09.04.2020
  • Повідомлень: 9
    • Репутація: 0

Re: Catastrophic Backtracking в регулярному виразі

Я не маю доступ до самої програми.

Мені дали робочий шаблон, який я зрозумів використовується в самій програмі і потрібно його підкоригувати в RegEx для позбавлення від нескінченного бектракінгу

7 Відповідь від fromes

  • fromes
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 09.04.2020
  • Повідомлень: 9
    • Репутація: 0

Re: Catastrophic Backtracking в регулярному виразі

<href> - це посилання
<anchor> - текст посилання
<sniplet> - опис посилання (сайту)

8 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Catastrophic Backtracking в регулярному виразі

Усі назви класів - автозгенеровані, по них орієнтуватися не можна взагалі. Орієнтуйтеся на теги a, div та h2/h3.

koala вебсайт

9 Відповідь від fromes

  • fromes
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 09.04.2020
  • Повідомлень: 9
    • Репутація: 0

Re: Catastrophic Backtracking в регулярному виразі

Я розумію, що при зміні дизайну потрібно дивитися в тегах. Але як укласти висновок в вираження розуму не прикладу.

10 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Catastrophic Backtracking в регулярному виразі

А моєї першої пропозиції точно не вистачило?

koala вебсайт

11 Відповідь від fromes

  • fromes
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 09.04.2020
  • Повідомлень: 9
    • Репутація: 0

Re: Catastrophic Backtracking в регулярному виразі

На жаль ні.

Зробив так для тесту

<div class="KJDcUb(.*?)(href=")(?<href>[^"]*?)"(.*?)
<div class="PpBGzd YcUVQe">(?<anchor>.*?)<.*?>
<div class="MUxGbd yDYNvb">(?<sniplet>.*?)</div>

в першому html коді, який відповідає зазначеним в регулярке #div class# працює вираз,

у другому html коді, де один з #div class# змінений відбувається нескінченній бектракінг

12 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Catastrophic Backtracking в регулярному виразі

Трохи погрався, але суттєво не покращив. Ні, боюся, C̱̱̟͈ͅa̢͇̲͔̥̣t͞as̙͝t̶͍r͇̯o̠p҉͎h̦̰̬̤̼̠͈͟i̭͍͝c̲̞̻̠ ̮̞̦͓͔͎B͏͎̤͈̞̞͔a̡͓c̛͔͚̜k̰̖t̴ṛ̬͇̘͙͜a̡͔̜͙̥̻̼̻ćk͙̗͓̲i̭̙͉͇͙̤̦͟n̰̫͓̮̲̟͟g̴̯ ̢̺͈- є̛̦̙͖͓̙̫̬̫͖д̶̦̤̠̱͉́и̵̪̪͈́͡ͅн̨͙͘е͔͍̰̻̥̝̙̤͢,͏̪̱͇͉̭̥ ̝͎͙̭щ̧͉̭̱͖о̛̜̜̮̖̫͟ ̴̧̺͈̩̲̱̙в̶͔͙̟͘і͈͜д͏̡̣̰̰̞̫̤д̲̝͡і̶͕̦͇͓̝̝̠̱͔͝л͈̬͔я̝̘̫̣̕є̘̻̼̠̫̕͟ͅͅ ̤̯͍͇̠̠͇́н̤̱̼̠̼͉̀͞а̯̙͇̺̟͍͔ш̧͙̯̗ ͘͏͙̫̼̝̙͙͕̞с̛͖̠͙̣̥̘͖́в̞͇̼̣͟і̧͔̜͚͓͎͇͡͠т̙̬̮̫̬͡ в̶̶̧̛͙̩̘̰͡і̴͙̰͔̞̜̟ͅд̡͏̶̪̦̞͕̘͉͚̖͜ͅ ̴̳̪͍͕̗͡͞З̛̀́͠҉͍̝̘͈͓̗̫̠͚̩͕͍̦̟͚̗а҉̛̙͕̫ͅл̹͍̠̻̜̻̳̙̯̘̦͠͠ͅґ҉̶̛̬̺͓̼̥͙̱͔̼̹̗̬̲̩͖̼̳͡о͜҉̗̟̖̠̜̱̝̦͕̩̀͟ͅ.̱͓̣̬̺̕͢.̵̡̨̛̪͔̳̱͖͕̰̰̝̪͈̙̬͔͔͍̺.̵͏̧͖͕̠̝͕̣̤̤̼̪͙͎̰̠̲̤̞̦

Подякували: Betterthanyou1

koala вебсайт

13 Відповідь від fromes

  • fromes
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 09.04.2020
  • Повідомлень: 9
    • Репутація: 0

Re: Catastrophic Backtracking в регулярному виразі

Спасибі, що намагалися допомогти.

14 Відповідь від fromes

  • fromes
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 09.04.2020
  • Повідомлень: 9
    • Репутація: 0

Re: Catastrophic Backtracking в регулярному виразі

Поки відклав першу проблему.


Але виникла інша проблема: потрібно отримати дані з пошуку Яндекс через регулярні вирази..


Уже другий день б'юся, і все ніяк. Якщо не складно можете допомогти, так як я новачок в цьому?

Завдання: з сторінки html отримати такі дані: урл, назва і текст сайтів  (<href>, <anchor>, <sniplet>)

Приклад html сторінки http://wdfiles.ru/6r3k

потрібно відібрати 10 сайтів, які відображаються в пошуку, крім рекламних

15 Відповідь від Betterthanyou

  • Звідки: Київ
  • Дата реєстрації: 16.05.2014
  • Повідомлень: 1 695
    • Репутація: 1022

Re: Catastrophic Backtracking в регулярному виразі

▼не по темі
koala написав:

C̱̱̟͈ͅa̢͇̲͔̥̣t͞as̙͝t̶͍r͇̯o̠p҉͎h̦̰̬̤̼̠͈͟i̭͍͝c̲̞̻̠ ̮̞̦͓͔͎B͏͎̤͈̞̞͔a̡͓c̛͔͚̜k̰̖t̴ṛ̬͇̘͙͜a̡͔̜͙̥̻̼̻ćk͙̗͓̲i̭̙͉͇͙̤̦͟n̰̫͓̮̲̟͟g̴̯ ̢̺͈- є̛̦̙͖͓̙̫̬̫͖д̶̦̤̠̱͉́и̵̪̪͈́͡ͅн̨͙͘е͔͍̰̻̥̝̙̤͢,͏̪̱͇͉̭̥ ̝͎͙̭щ̧͉̭̱͖о̛̜̜̮̖̫͟ ̴̧̺͈̩̲̱̙в̶͔͙̟͘і͈͜д͏̡̣̰̰̞̫̤д̲̝͡і̶͕̦͇͓̝̝̠̱͔͝л͈̬͔я̝̘̫̣̕є̘̻̼̠̫̕͟ͅͅ ̤̯͍͇̠̠͇́н̤̱̼̠̼͉̀͞а̯̙͇̺̟͍͔ш̧͙̯̗ ͘͏͙̫̼̝̙͙͕̞с̛͖̠͙̣̥̘͖́в̞͇̼̣͟і̧͔̜͚͓͎͇͡͠т̙̬̮̫̬͡ в̶̶̧̛͙̩̘̰͡і̴͙̰͔̞̜̟ͅд̡͏̶̪̦̞͕̘͉͚̖͜ͅ ̴̳̪͍͕̗͡͞З̛̀́͠҉͍̝̘͈͓̗̫̠͚̩͕͍̦̟͚̗а҉̛̙͕̫ͅл̹͍̠̻̜̻̳̙̯̘̦͠͠ͅґ҉̶̛̬̺͓̼̥͙̱͔̼̹̗̬̲̩͖̼̳͡о͜҉̗̟̖̠̜̱̝̦͕̩̀͟ͅ.̱͓̣̬̺̕͢.̵̡̨̛̪͔̳̱͖͕̰̰̝̪͈̙̬͔͔͍̺.̵͏̧͖͕̠̝͕̣̤̤̼̪͙͎̰̠̲̤̞̦

Як таке написати ?

Подякували: 221VOLT1

Betterthanyou вебсайт

16 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Catastrophic Backtracking в регулярному виразі

᠎
    ᠎
    ᠎

    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎    ᠎H̶̪̣̥̯̯͎͈̯̻͚̻̻̗̰̩̠͚̔̆ͥͥ̇ͮͭ͑̊ͧ͘͟Ę̗̹͓̦̯̳͉̳̖͗̋ͧͬ͂̒ͅ ̵̖͇͓ͤ̃̊̉̋ͮ͗͑͒ͭ̍́͛͐ͤͨͥͥ̆ͅĊ̊ͯ͑͒ͯͦ̑͗̋ͫ҉̪͖̲̖̣̣͕̩̞̼͞O̡̡̢̘̱͙̺̻̱̩̥̹̫̲͇̦ͧ̎͋ͦ̇̃ͤ͆̈́̆̓̌̄̂ͨ͌̚̕M̝̣̙̰͈͕̊̐̓͗̄̏̍͑̿ͦͫ̓ͮͧ͘͠E̙̳̲̯ͥ̎ͬͨͩ͑ͯ̓̿̇̍̌ͬ̚͝ͅŚ̵̢͍̞̺̝͍͔͙̯̾͊̉̈͡
    ᠎
    ᠎
    ᠎

Подякували: Betterthanyou1

koala вебсайт