Зіставлення шаблонів широко використовується в інформатиці та багатьох інших галузях. Алгоритми зіставлення шаблонів використовуються для пошуку шаблонів у більшому тексті чи наборі даних. Одним із найпопулярніших алгоритмів зіставлення шаблонів є Боєр-Мур algorithm, який вперше був опублікований у 1977 році. У цій статті ми обговоримо алгоритми зіставлення шаблонів у C і як вони працюють.
Що таке алгоритм зіставлення шаблонів?
Алгоритми зіставлення шаблонів використовуються для пошуку шаблонів у більшому наборі даних або тексту. Ці алгоритми працюють, порівнюючи шаблон із більшим набором даних або текстом і визначаючи, чи присутній шаблон. Алгоритми зіставлення шаблонів важливі, оскільки вони дозволяють нам швидко шукати шаблони у великих наборах даних.
що таке об'єкт java
Алгоритм зіставлення шаблону грубої сили:
Зіставлення шаблону грубою силою є найпростішим алгоритмом зіставлення шаблону. Він передбачає порівняння символів шаблону з символами тексту по одному. Якщо всі символи збігаються, алгоритм повертає початкову позицію шаблону в тексті. Якщо ні, алгоритм переходить до наступної позиції в тексті та повторює порівняння, доки не буде знайдено відповідність або досягнуто кінця тексту. Часова складність алгоритму грубої сили становить O(MXN) , де М позначає довжину тексту і Н позначає довжину візерунка.
Наївний алгоритм зіставлення шаблонів:
Алгоритм Naive Pattern Matching є вдосконаленим алгоритмом Brute Force. Це дозволяє уникнути непотрібних порівнянь, пропускаючи деякі позиції в тексті. Алгоритм починає порівнювати шаблон з текстом з першої позиції. Якщо символи збігаються, він переходить до наступної позиції та повторює порівняння. Якщо символи не збігаються, алгоритм переходить до наступної позиції в тексті та знову порівнює шаблон із текстом. Часова складність Наївного алгоритму також є O(MXN) , але в більшості випадків це швидше, ніж алгоритм Brute Force.
Алгоритм Кнута-Морріса-Пратта:
The Кнут-Морріс-Пратт (KMP) algorithm — це вдосконалений алгоритм зіставлення шаблонів. Він заснований на спостереженні, що коли виникає невідповідність, можна використати деяку інформацію про текст і шаблон, щоб уникнути непотрібних порівнянь. Алгоритм попередньо обчислює таблицю, яка містить інформацію про шаблон. Таблиця визначає, скільки символів шаблону можна пропустити, коли виникає невідповідність. Часова складність КМП алгоритм є O(M+N) .
Алгоритм Боєра-Мура:
Одним із найпопулярніших алгоритмів зіставлення шаблонів є Боєр-Мур алгоритм. Цей алгоритм був вперше опублікований у 1977 році Робертом С. Боєром і Дж. Стротером Муром. The Боєр-Мур алгоритм порівнює шаблон із більшим набором даних або тексту справа наліво, а не зліва направо, як у більшості інших алгоритмів зіставлення шаблонів.
The Боєр-Мур Алгоритм має два основних компоненти: правило поганих символів і правило хороших суфіксів. Правило поганого символу працює шляхом порівняння символу в шаблоні з відповідним символом у даних або тексті. Якщо символи не збігаються, алгоритм переміщує шаблон праворуч, доки не знайде символ, який відповідає. Правило хорошого суфікса порівнює суфікс шаблону з відповідним суфіксом даних або тексту. Якщо суфікси не збігаються, алгоритм переміщує шаблон праворуч, доки не знайде відповідний суфікс.
The Боєр-Мур Алгоритм відомий своєю ефективністю і широко використовується в багатьох програмах. Він вважається одним із найшвидших доступних алгоритмів зіставлення шаблонів.
Реалізація алгоритму Боєра-Мура в 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;>