Rabin-Karp算法

Question

我对实现拉宾-卡普算法来搜索子字符串很感兴趣，如wiki：http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm所述。不是用来做作业的，而是用来谋利的。我已经实现了Rabin-Karp算法(如下所示)，并且它是有效的。然而，性能真的真的很差！我知道我的散列函数是基本的。但是，似乎对strstr()的简单调用总是优于我的函数rabin_karp()。我可以理解为什么-哈希函数比简单的逐个字符比较每个循环做了更多的工作。这里我漏掉了什么？Rabin-Karp算法应该比调用strstr()更快吗？什么时候最好使用Rabin-Karp算法？这就是我的私利。我是否实现了正确的算法？

size_t hash(char* str, size_t i)
{
   size_t h = 0;
   size_t magic_exp = 1;
// if (str != NULL)
   {
      while (i-- != 0)
      {
         magic_exp *= 101;
         h += magic_exp + *str;
         ++str;
      }
   }

   return h;
}

char* rabin_karp(char* s, char* find)
{
   char* p = NULL;

   if (s != NULL && find != NULL)
   {
      size_t n = strlen(s);
      size_t m = strlen(find);

      if (n > m)
      {
         size_t hfind = hash(find, m);

         char* end = s + (n - m + 1);
         for (char* i = s; i < end; ++i)
         {
            size_t hs = hash(i, m);
            if (hs == hfind)
            {
               if (strncmp(i, find, m) == 0)
               {
                  p = i;
                  break;
               }
            }
         }
      }
   }

   return p;
}

Answer 1

您没有正确地实现哈希。Rabin-Karp的关键是随着潜在匹配沿着要搜索的字符串移动，逐步更新散列。正如您已经确定的那样，如果您为每个潜在的匹配位置重新计算整个散列，事情将会非常缓慢。

对于除第一次比较之外的每种情况，您的散列函数都应该接受现有散列、一个新字符和一个旧字符，并返回更新后的散列。

Answer 2

Rabin-Karp是一种滚动哈希算法-其思想是能够将子串向任何一个方向(左或右)移动一个位置，并能够以恒定的操作次数重新计算哈希。由于您已经实现了它，搜索的复杂度为O(N * L)，其中N是大字符串的长度，L是要搜索的字符串的长度。这就是最幼稚的方法的复杂性，在我看来，这实际上是对它的一种微不足道的模仿。

为了改进你的算法，预先计算magic_exp的指数，并使用它们‘滚动’你的散列--基本上就像多项式一样，你需要减去最高阶乘以magic_exp，然后将符号的散列添加到右边(用于将散列移到右边)。

希望这能有所帮助。

Answer 3

strstr使用KMP算法，该算法本质上也是线性的。这意味着这两种算法的复杂度大致相同。从那时起，常数就成了重要的因素。尤其是当你的散列函数很糟糕，并且有很多冲突的时候，KMP的速度会快很多。

编辑：还有一件事。对于Rabin Karp算法来说，预先计算所有前缀的哈希码是非常重要的。现在您没有实现正确的Rabin Karp，因为对您的函数的调用将是线性的，而不是复杂度恒定的。(顺便说一句，这意味着维基百科不是学习拉宾·卡普的好来源)。