Поиск подстроки в строке по алгоритму Карпа-Рабина
Поиск подстроки в строке по алгоритму Карпа-Рабина
Когда речь заходит об алгоритмах точного поиска подстроки в строке, то обычно все так или иначе сводится к последовательному сравнению символов. Но есть группа алгоритмов, которые основаны не на сравнении символов, а на сравнении числовых данных - хешей. Одним из таких алгоритмов является алгоритм Карпа-Рабина. Его принцип достаточно простой: вычисляется хеш от строки поиска, затем вычисляется хеш от фрагмента строки, в которой производится поиск. Длина фрагмента равна длине искомой строки. Если хеши равны, то выполняется дополнительное посимвольное сравнение, если не равны, то продвигаемся по строке дальше. Казалось бы, что выигрыша тут никакого быть не может, ведь вместо сравнения вычислительные ресурсы тратятся на хеширование. Однако, как показывает практика, для поиска совпадения это гораздо эффективнее, чем сравнение отдельных символов строк. Вместо O(n*m) операций можно добиться среднего результата O(n+m), где n - длина исходной строки, а m - длина искомой строки. К тому же алгоритм Карпа-Рабина не требует выделения дополнительной памяти для своей работы.
Функция хеширования - очень важная часть алгоритма. Ведь если при ее использовании начнут появляться многочисленные ложные срабатывания, то последующее сравнение символов станет выполняться слишком часто, что сводит на нет всю эффективность алгоритма. Также хеш не должен полностью заново вычисляться для каждого фрагмента, он должен получаться из предыдущего, но при этом соответствовать параметрам поиска. Таким условиям удовлетворяет полиномиальный "скользящий" хеш с операциями сложения и битового сдвига.
Code (Assembler) : Убрать нумерацию
- ;----------------------------------------------------------------
- ; Функция поиска подстроки в строке по алгоритму Карпа-Рабина
- ; by ManHunter / PCL (www.manhunter.ru)
- ;----------------------------------------------------------------
- ; Параметры:
- ; lpHaystack - указатель на исходную строку
- ; dHLen - длина исходной строки
- ; lpNeedle - указатель на строку для поиска
- ; dNLen - длина строки для поиска
- ; На выходе:
- ; EAX = позиция подстроки в строке
- ; EAX = -1 если подстрока не найдена
- ;----------------------------------------------------------------
- proc kr_search lpHaystack:DWORD, dHLen:DWORD, lpNeedle:DWORD, dNLen:DWORD
- pusha
- ; Искомая строка длиннее области поиска?
- mov eax,[dHLen]
- cmp eax,[dNLen]
- jb .loc_error
- ; Строки не могут быть пустыми
- cmp [dHLen],0
- je .loc_error
- cmp [dNLen],0
- je .loc_error
- ; Искомая строка не может быть длиннее 32 символов
- cmp [dNLen],32
- ja .loc_error
- ; Первоначальный расчет хешей
- xor esi,esi
- xor edi,edi
- xor ebx,ebx
- @@:
- shl esi,1
- mov eax,[lpNeedle]
- movzx eax,byte[eax+ebx]
- add esi,eax
- shl edi,1
- mov eax,[lpHaystack]
- movzx eax,byte[eax+ebx]
- add edi,eax
- inc ebx
- cmp ebx,[dNLen]
- jb @b
- mov ebx,[dNLen]
- .loc_scan:
- ; Хеши совпали?
- cmp esi,edi
- jne @f
- ; Строки совпали целиком?
- push esi edi
- mov esi,[lpNeedle]
- mov edi,[lpHaystack]
- add edi,ebx
- sub edi,[dNLen]
- mov ecx,[dNLen]
- repe cmpsb
- pop edi esi
- jnz @f
- ; Найденная позиция подстроки
- sub ebx,[dNLen]
- jmp .loc_done
- @@:
- ; Пересчитать сравниваемый хеш
- mov eax,ebx
- sub eax,[dNLen]
- mov edx,[lpHaystack]
- movzx eax,byte[edx+eax]
- mov edx,1
- mov ecx,[dNLen]
- dec ecx
- shl edx,cl
- mov ecx,edx
- xor edx,edx
- imul ecx
- sub edi,eax
- shl edi,1
- mov eax,ebx
- mov edx,[lpHaystack]
- movzx eax,byte[edx+eax]
- add edi,eax
- ; Следующая позиция
- inc ebx
- cmp ebx,[dHLen]
- jb .loc_scan
- .loc_error:
- ; Подстрока не может быть найдена
- mov ebx,-1
- .loc_done:
- ; Результат в EAX
- mov [esp+28],ebx
- popa
- ret
- endp
Так как размер используемых хешей равен размеру DWORD, то максимальная длина искомой подстроки не должна превышать 32 символа. В противном случае поиск вернет ошибку, даже если подстрока содержится в строке. Это единственное функциональное ограничение. В принципе, его тоже можно обойти, если хешировать не более 32 символов с начала строки, ведь хэша хватит для отсеивания подавляющего числа несоответствий, а потом все равно побайтовое сравнение по полной длине подстроки выявит оставшиеся несоответствия. Длины 32-битного хеша будет достаточно, чтобы минимизировать коллизии.
Алгоритм Карпа-Рабина будет максимально эффективным при одновременном поиске множества подстрок, так как все операции сравнения будут выполняться за один проход. При этом длина искомых строк может быть различной, хоть это и повлечет за собой некоторое усложнение кода. Использование хеша также позволяет сверять не паттерны целиком, а соответствующие им числовые значения, что также положительно влияет на структурирование данных при хранении.
В приложении пример программы с исходным текстом, которая ищет вхождение подстроки в строке по алгоритму Карпа-Рабина.
Пример программы с исходным текстом (FASM)
Просмотров: 1969 | Комментариев: 3
Метки: Assembler, полезные функции
Внимание! Статья опубликована больше года назад, информация могла устареть!
Комментарии
Отзывы посетителей сайта о статье
Darkz
(10.04.2023 в 21:26):
Интересно было бы взглянуть на алгоритм поиска множество подстрок из массива,и сравнить на сколько быстрей repe scasb и (первый байт) и repe cmpsb вся строка. А так если искать по 1 строке то особой разницы не заметил
DRON
(01.06.2022 в 16:39):
Там много чего ещё есть: например Bitap (он же Shift-OR) вообще за O(n) может найти, причём поиск может быть не строгим.
Джо
(01.06.2022 в 08:29):
Интересно, не знал про такой алгоритм. Думал что кроме Бойера—Мура ничего особо нет. Весь секрет тут видимо в функции хэша.
Добавить комментарий
Заполните форму для добавления комментария
Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Вам помог этот сайт?
Поблагодарили 35,185 раз
Поблагодарили 35,185 раз
Буду очень благодарен, если размеcтите мою кнопочку:
 |
Яндекс ИКС: 360 |
 |
 |