Blog. Just Blog

Поиск подстроки в строке по алгоритму Карпа-Рабина

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
Поиск подстроки в строке по алгоритму Карпа-Рабина
Поиск подстроки в строке по алгоритму Карпа-Рабина

Когда речь заходит об алгоритмах точного поиска подстроки в строке, то обычно все так или иначе сводится к последовательному сравнению символов. Но есть группа алгоритмов, которые основаны не на сравнении символов, а на сравнении числовых данных - хешей. Одним из таких алгоритмов является алгоритм Карпа-Рабина. Его принцип достаточно простой: вычисляется хеш от строки поиска, затем вычисляется хеш от фрагмента строки, в которой производится поиск. Длина фрагмента равна длине искомой строки. Если хеши равны, то выполняется дополнительное посимвольное сравнение, если не равны, то продвигаемся по строке дальше. Казалось бы, что выигрыша тут никакого быть не может, ведь вместо сравнения вычислительные ресурсы тратятся на хеширование. Однако, как показывает практика, для поиска совпадения это гораздо эффективнее, чем сравнение отдельных символов строк. Вместо O(n*m) операций можно добиться среднего результата O(n+m), где n - длина исходной строки, а m - длина искомой строки. К тому же алгоритм Карпа-Рабина не требует выделения дополнительной памяти для своей работы.

Функция хеширования - очень важная часть алгоритма. Ведь если при ее использовании начнут появляться многочисленные ложные срабатывания, то последующее сравнение символов станет выполняться слишком часто, что сводит на нет всю эффективность алгоритма. Также хеш не должен полностью заново вычисляться для каждого фрагмента, он должен получаться из предыдущего, но при этом соответствовать параметрам поиска. Таким условиям удовлетворяет полиномиальный "скользящий" хеш с операциями сложения и битового сдвига.
  1. ;----------------------------------------------------------------
  2. ; Функция поиска подстроки в строке по алгоритму Карпа-Рабина
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpHaystack - указатель на исходную строку
  7. ;   dHLen - длина исходной строки
  8. ;   lpNeedle - указатель на строку для поиска
  9. ;   dNLen - длина строки для поиска
  10. ; На выходе:
  11. ;   EAX = позиция подстроки в строке
  12. ;   EAX = -1 если подстрока не найдена
  13. ;----------------------------------------------------------------
  14. proc kr_search lpHaystack:DWORD, dHLen:DWORD, lpNeedle:DWORD, dNLen:DWORD
  15.         pusha
  16.  
  17.         ; Искомая строка длиннее области поиска?
  18.         mov     eax,[dHLen]
  19.         cmp     eax,[dNLen]
  20.         jb      .loc_error
  21.  
  22.         ; Строки не могут быть пустыми
  23.         cmp     [dHLen],0
  24.         je      .loc_error
  25.         cmp     [dNLen],0
  26.         je      .loc_error
  27.         ; Искомая строка не может быть длиннее 32 символов
  28.         cmp     [dNLen],32
  29.         ja      .loc_error
  30.  
  31.         ; Первоначальный расчет хешей
  32.         xor     esi,esi
  33.         xor     edi,edi
  34.         xor     ebx,ebx
  35. @@:
  36.         shl     esi,1
  37.         mov     eax,[lpNeedle]
  38.         movzx   eax,byte[eax+ebx]
  39.         add     esi,eax
  40.         shl     edi,1
  41.         mov     eax,[lpHaystack]
  42.         movzx   eax,byte[eax+ebx]
  43.         add     edi,eax
  44.         inc     ebx
  45.         cmp     ebx,[dNLen]
  46.         jb      @b
  47.  
  48.         mov     ebx,[dNLen]
  49. .loc_scan:
  50.         ; Хеши совпали?
  51.         cmp     esi,edi
  52.         jne     @f
  53.  
  54.         ; Строки совпали целиком?
  55.         push    esi edi
  56.         mov     esi,[lpNeedle]
  57.         mov     edi,[lpHaystack]
  58.         add     edi,ebx
  59.         sub     edi,[dNLen]
  60.         mov     ecx,[dNLen]
  61.         repe    cmpsb
  62.         pop     edi esi
  63.         jnz     @f
  64.  
  65.         ; Найденная позиция подстроки
  66.         sub     ebx,[dNLen]
  67.         jmp     .loc_done
  68. @@:
  69.         ; Пересчитать сравниваемый хеш
  70.         mov     eax,ebx
  71.         sub     eax,[dNLen]
  72.         mov     edx,[lpHaystack]
  73.         movzx   eax,byte[edx+eax]
  74.         mov     edx,1
  75.         mov     ecx,[dNLen]
  76.         dec     ecx
  77.         shl     edx,cl
  78.         mov     ecx,edx
  79.         xor     edx,edx
  80.         imul    ecx
  81.         sub     edi,eax
  82.         shl     edi,1
  83.         mov     eax,ebx
  84.         mov     edx,[lpHaystack]
  85.         movzx   eax,byte[edx+eax]
  86.         add     edi,eax
  87.  
  88.         ; Следующая позиция
  89.         inc     ebx
  90.         cmp     ebx,[dHLen]
  91.         jb      .loc_scan
  92. .loc_error:
  93.         ; Подстрока не может быть найдена
  94.         mov     ebx,-1
  95. .loc_done:
  96.         ; Результат в EAX
  97.         mov     [esp+28],ebx
  98.         popa
  99.         ret
  100. endp
Функции передается четыре параметра: указатель на исходную строку, длина исходной строки, указатель на строку для поиска и длина строки для поиска. Если подстрока была найдена, то в регистре EAX вернется ее позиция в строке, иначе EAX будет равно -1.

Так как размер используемых хешей равен размеру DWORD, то максимальная длина искомой подстроки не должна превышать 32 символа. В противном случае поиск вернет ошибку, даже если подстрока содержится в строке. Это единственное функциональное ограничение. В принципе, его тоже можно обойти, если хешировать не более 32 символов с начала строки, ведь хэша хватит для отсеивания подавляющего числа несоответствий, а потом все равно побайтовое сравнение по полной длине подстроки выявит оставшиеся несоответствия. Длины 32-битного хеша будет достаточно, чтобы минимизировать коллизии.

Алгоритм Карпа-Рабина будет максимально эффективным при одновременном поиске множества подстрок, так как все операции сравнения будут выполняться за один проход. При этом длина искомых строк может быть различной, хоть это и повлечет за собой некоторое усложнение кода. Использование хеша также позволяет сверять не паттерны целиком, а соответствующие им числовые значения, что также положительно влияет на структурирование данных при хранении.

В приложении пример программы с исходным текстом, которая ищет вхождение подстроки в строке по алгоритму Карпа-Рабина.

Пример программы с исходным текстом (FASM)Пример программы с исходным текстом (FASM)

Karp.Rabin.Search.Demo.zip (2,256 bytes)


Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 924 | Комментариев: 2

Комментарии

Отзывы посетителей сайта о статье
DRON (01.06.2022 в 16:39):
Там много чего ещё есть: например Bitap (он же Shift-OR) вообще за O(n) может найти, причём поиск может быть не строгим.
Джо (01.06.2022 в 08:29):
Интересно, не знал про такой алгоритм. Думал что кроме Бойера—Мура ничего особо нет. Весь секрет тут видимо в функции хэша.

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2022
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.07 сек. / MySQL: 2 (0.0055 сек.) / Память: 4.75 Mb
Наверх