8

我有兴趣实现 Rabin-Karp 算法来搜索 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;
}
4

3 回答 3

14

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

对于除第一次比较之外的所有情况，您的散列函数应采用现有散列、一个新字符和一个旧字符，并返回一个更新的散列。

于 2012-04-21T06:54:05.863 回答
4

Rabin-Karp 是一种滚动散列算法 - 其想法是能够将子串移动一个位置到任一方向（左或右），并能够以恒定数量的操作重新计算散列。当您实现它时，搜索的复杂度为 O(N * L)，其中 N 是大字符串的长度，L 是您要搜索的字符串的长度。这是最天真的方法的复杂性，在我看来实际上是对它的一点悲观。

为了改进您的算法，预先计算 magic_exp 的指数并使用它们来“滚动”您的哈希 - 基本上就像多项式一样，您需要减去最高次数乘以 magic_exp 并将符号的哈希添加到右侧（用于将哈希移动到正确的）。

希望这可以帮助。

于 2012-04-21T07:12:47.697 回答
1

strstr正在使用本质上也是线性的KMP算法。这意味着两种算法的复杂度大致相同。从那时起，常数是重要的因素。尤其是在你的哈希函数很糟糕并且有很多冲突的情况下，KMP 会快很多。

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

于 2012-04-21T06:56:15.413 回答