Објашњен Рабин-Карпов алгоритам

Рабин-Карп алгоритам је алгоритам подударања / претраживања низа који су развили Мицхаел О. Рабин и Рицхард М. Карп. За поређење користи технику хеширања и грубу силу и добар је кандидат за откривање плагијаризма.

Важни појмови

  • паттерн је низ који треба претражити. Узмите у обзир дужину узорка као М знакова.
  • текст је цео текст из којег се тражи образац. Узмите у обзир дужину текста као Н знакова.

Шта је поређење грубе силе?

У поређењу са грубом силом, сваки знак узорка се упоређује са сваким знаком текста док се не пронађу знакови који се не подударају.

Како функционише Рабин-Карпов алгоритам

  1. Израчунајте хеш вредност шаблона
  2. Израчунајте хеш вредност првих М знакова текста
  3. Упоредите обе хеш вредности
  4. Ако су неједнаке, израчунајте хеш вредност за следећих М знакова текста и поново упоредите.
  5. Ако су једнаки, извршите грубо упоређивање.
hash_p = hash value of pattern hash_t = hash value of first M letters in body of text do if (hash_p == hash_t) brute force comparison of pattern and selected section of text hash_t= hash value of next section of text, one character over while (end of text or brute force comparison == true)

Предност над алгоритмом подударања наивног низа

Ова техника резултира само једним поређењем по подсеквенци текста, а груба сила је потребна само када се хеш вредности подударају.