8

ウィキに記載されているように、サブ文字列を検索するためのラビン-カープアルゴリズムの実装に興味があります：http：//en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm。宿題のためではなく、利己心のためです。Rabin-Karpアルゴリズム（以下に表示）を実装しましたが、機能します。しかし、パフォーマンスは本当に、本当に悪いです!!! 私のハッシュ関数は基本的なものだと理解しています。ただし、strstr（）を呼び出すだけで、関数rabin_karp（）よりも常にパフォーマンスが向上するようです。理由は理解できます。ハッシュ関数は、各ループを単純な文字ごとに比較するよりも多くの作業を行っています。ここで何が欠けていますか？Rabin-Karpアルゴリズムは、strstr（）の呼び出しよりも高速である必要がありますか？ラビン-カープアルゴリズムが最適に使用されるのはいつですか？したがって、私の利己心。アルゴリズムを正しく実装しましたか？

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の鍵は、一致する可能性のあるものが検索対象の文字列に沿って移動するときに、ハッシュを段階的に更新することです。あなたが決定したように、潜在的な一致位置ごとにハッシュ全体を再計算すると、物事は本当に遅くなります。

最初の比較を除くすべての場合で、ハッシュ関数は既存のハッシュ、1つの新しい文字、および1つの古い文字を取得し、更新されたハッシュを返す必要があります。

于 2012-04-21T06:54:05.863 に答える
4

Rabin-Karpはローリングハッシュアルゴリズムです。アイデアは、部分文字列をいずれかの方向（左または右）に1位置移動し、一定数の操作でハッシュを再計算できるようにすることです。これを実装したため、検索の複雑さはO（N * L）になります。ここで、Nは大きな文字列の長さ、Lは検索する文字列の長さです。これは最も素朴なアプローチの複雑さであり、実際、私の意見では少し悲観的です。

アルゴリズムを改善するには、magic_expの指数を事前計算し、それらを使用してハッシュを「ロール」します。基本的に、多項式の場合と同様に、最高次の乗算にmagic_expを減算し、シンボルのハッシュを右側に追加する必要があります（ハッシュを権利）。

お役に立てれば。

于 2012-04-21T07:12:47.697 に答える
1

strstr本質的に線形でもあるKMPアルゴリズムを使用しています。これは、2つのアルゴリズムの複雑さがほぼ同じであることを意味します。それ以降、定数が重要な要素になります。特に、衝突が多い悪いハッシュ関数がある場合、KMPははるかに高速になります。

編集：もう1つ。Rabin Karpアルゴリズムでは、プレフィックスのすべてのハッシュコードを事前に計算することが非常に重要です。関数の呼び出しは線形であり、複雑さが一定ではないため、適切なラビンカープを実装していません。（ちなみに、これはウィキペディアがラビン・カープを学ぶのにあまり良い情報源ではないことを意味します）。

于 2012-04-21T06:56:15.413 に答える