Pattern Matching се използва широко в компютърните науки и много други области. Алгоритмите за съпоставяне на шаблони се използват за търсене на шаблони в рамките на по-голям текст или набор от данни. Един от най-популярните алгоритми за съвпадение на шаблони е Бойер-Мур алгоритъм, който беше публикуван за първи път през 1977 г. В тази статия ще обсъдим алгоритмите за съвпадение на шаблони в C и как работят.
Какво е алгоритъм за съпоставяне на шаблон?
Алгоритмите за съпоставяне на шаблони се използват за намиране на шаблони в рамките на по-голям набор от данни или текст. Тези алгоритми работят, като сравняват модел с по-голям набор от данни или текст и определят дали моделът присъства или не. Алгоритмите за съвпадение на шаблони са важни, защото ни позволяват бързо да търсим модели в големи набори от данни.
подчертаване с помощта на css
Алгоритъм за съпоставяне на шаблони с груба сила:
Brute Force Pattern Matching е най-простият алгоритъм за Pattern Matching. Това включва сравняване на знаците от модела със знаците на текста един по един. Ако всички символи съвпадат, алгоритъмът връща началната позиция на шаблона в текста. Ако не, алгоритъмът се премества на следващата позиция в текста и повтаря сравнението, докато се намери съвпадение или се стигне до края на текста. Времевата сложност на алгоритъма за груба сила е O(MXN) , където М обозначава дължината на текста и н обозначава дължината на шаблона.
Наивен алгоритъм за съвпадение на шаблони:
Алгоритъмът Naive Pattern Matching е подобрение спрямо алгоритъма Brute Force. Избягва ненужните сравнения, като пропуска някои позиции в текста. Алгоритъмът започва да сравнява модела с текста на първа позиция. Ако знаците съвпадат, той преминава към следващата позиция и повтаря сравнението. Ако символите не съвпадат, алгоритъмът се премества на следващата позиция в текста и отново сравнява шаблона с текста. Времевата сложност на Naive алгоритъма също е O(MXN) , но в повечето случаи е по-бърз от алгоритъма Brute Force.
Алгоритъм на Кнут-Морис-Прат:
The Кнут-Морис-Прат (KMP) алгоритъмът е по-усъвършенстван алгоритъм за съвпадение на шаблони. Основава се на наблюдението, че когато възникне несъответствие, може да се използва известна информация за текста и модела, за да се избегнат ненужни сравнения. Алгоритъмът предварително изчислява таблица, която съдържа информация за модела. Таблицата определя колко знака от модела могат да бъдат пропуснати, когато възникне несъответствие. Времевата сложност на KMP алгоритъмът е O(M+N) .
Алгоритъмът на Бойер-Мур:
Един от най-популярните алгоритми за съвпадение на шаблони е Бойер-Мур алгоритъм. Този алгоритъм е публикуван за първи път през 1977 г. от Robert S. Boyer и J Strother Moore. The Бойер-Мур алгоритъмът сравнява модел с по-голям набор от данни или текст отдясно наляво вместо отляво надясно, както при повечето други алгоритми за съвпадение на шаблони.
The Бойер-Мур алгоритъмът има два основни компонента: правилото за лош символ и правилото за добър суфикс. Правилото за лош знак работи, като сравнява знака в шаблона със съответния знак в данните или текста. Ако знаците не съвпадат, алгоритъмът премества шаблона надясно, докато намери символ, който съвпада. Правилото за добър суфикс сравнява суфикса на шаблона със съответния суфикс на данните или текста. Ако суфиксите не съвпадат, алгоритъмът премества шаблона надясно, докато намери съвпадащ суфикс.
The Бойер-Мур Алгоритъмът е известен със своята ефективност и се използва широко в много приложения. Смята се за един от най-бързите налични алгоритми за съвпадение на шаблони.
Прилагане на алгоритъма на Boyer-Moore в C:
За прилагане на Бойер-Мур алгоритъм в C, можем да започнем с дефиниране на правилото за лош знак. Можем да използваме масив, за да съхраним последното появяване на всеки знак в шаблона. Този масив може да определи колко далеч трябва да преместим шаблона надясно, когато възникне несъответствие.
Ето пример за това как можем да приложим правилото за лош символ в C:
алгоритми за търсене
C код:
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>