c++ - 搜索整数子串的超快速方法

Question

我处于一种情况，我需要在一系列非常大的字符串中找到一个整数子字符串。我想到了使用 vector 的 vector 来存储整数字符串的范围，同样我将要搜索的整数字符串存储在 vector 中。示例如下:

//vector of 5 vectors
std::vector<std::vector<int>> vec(5);
// elements= {10,5,8,23,15,32,12,34,56,55,43,12,33,4}

并将子串转化为vector

//vector with integer substring
std::vector<int> vec1;
//elements = {5,8,23}

然后我使用 std::search 对 vector of vectors 执行搜索操作以找到 vector，类似这样

for( int i = 0; i < vec.size(); i++) // searching read into 
   {
     auto pos = std::search(vec[i].begin(), vec[i].end(), vec1.begin(), vec1.end());
// some more code
}

在测试中，从 10 个 vector 的范围内搜索 1000 个字符串 花费了大约 1m，每个长度 500000.

有一些数据结构非常快，例如 unordered_map，但我怀疑我的数据是否会使用该数据结构。我将不胜感激任何在时间和空间方面都有效的容器或数据结构的建议或链接。

注意:

1) 无法对数据进行排序，因为我通过排序丢失了数据表示。

2) 我不是在搜索单个项目，而是在搜索整数的子字符串。

编辑

字符串的原始长度在每个 vector 中可能是100000000，子串的长度可能是100，在数量上是1000000。

Answer 1

这是我尝试的一种快速解决方案——在我的 2.7GHz Mac mini 上，它能够在 1357 毫秒内找到 1000 个“子字符串”的位置。它通过首先建立每个整数出现在大 vector 中的所有位置的索引来实现这一点，这样对于每个子字符串，它不必搜索所有地方，而是只搜索该子字符串可能实际开始的位置。需要注意的是，索引会占用相当多的额外 RAM，并且需要一些时间来构建；因此，这可能是也可能不是实用的解决方案，具体取决于您的用例。 (但请注意，它只需构建一次，除非/直到您继续搜索另一组大 vector )

#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdint>
#include <chrono>
#include <iostream>
#include <unordered_map>

using namespace std;

// Store a vector index and an offset into the vector efficiently
// Supports up to 256 vectors and offsets up to 16777216
static inline uint32_t GetVectorLocationKey(uint8_t whichVector, uint32_t offsetIntoVector)
{
   return ((((uint32_t)whichVector)<<24)|offsetIntoVector);
}

static inline void GetVectorLocationFromKey(uint32_t key, uint8_t & retWhichVector, uint32_t & retOffsetIntoVector)
{
   retWhichVector = (key >> 24) & 0xFF;
   retOffsetIntoVector = (key & 0xFFFFFF);
}

static inline bool SubstringExistsAtOffset(const int * bigVector, const vector<int> & substring)
{
   const int * smallVector = &substring[0];
   const size_t subLen = substring.size();
   for (size_t i=0; i<subLen; i++) if (bigVector[i] != smallVector[i]) return false;
   return true;
}

int main(int, char **)
{
   // Create some large vectors to search in
   vector<vector<int> > big_vectors;
   const size_t num_big_vectors = 5;
   const size_t big_vector_size = 500000;
   for (size_t i=0; i<num_big_vectors; i++)
   {
      big_vectors.push_back(vector<int>());
      vector<int> & v = big_vectors.back();
      for (size_t j=0; j<big_vector_size; j++) v.push_back(rand()%100);
   }

   // Pick out some small "substring" vectors to search for within the large vectors
   vector<vector<int> > substrings;
   const size_t num_substrings = 1000;
   const size_t substring_size = 14;
   for (size_t i=0; i<num_substrings; i++)
   {
      substrings.push_back(vector<int>());
      size_t whichBigVector = rand()%num_big_vectors;
      size_t offsetIntoVector = rand()%(big_vector_size-substring_size);
      vector<int> & v = substrings.back();
      const vector<int> & bigVector = big_vectors[whichBigVector];
      for (size_t j=0; j<substring_size; j++) v.push_back(bigVector[offsetIntoVector+j]);
   }

   // Now we'll build up a map so that for any given integer we'll
   // have immediate access to a list of the locations it is at.
   // That way we can jump immediately to those locations rather than
   // having to scan through the entire set of big_vectors
   unordered_map<int, vector<uint32_t> > index;
   for (size_t i=0; i<big_vectors.size(); i++)
   {
      const vector<int> & bigVector = big_vectors[i];
      for (size_t j=0; j<bigVector.size()-substring_size; j++)
      {
         int val = bigVector[j];
         index[val].push_back(GetVectorLocationKey(i, j));
      }
   }

   // Now for the time-critical part:  Let's see how fast we
   // can find our substrings within the larger vectors!
   std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
   vector<vector<uint32_t> > results;
   for (size_t i=0; i<substrings.size(); i++)
   {
      results.push_back(vector<uint32_t>());
      vector<uint32_t> & resultVec = results.back();

      const vector<int> & substring = substrings[i];
      const int firstVal = substring[0];
      const vector<uint32_t> & lookup = index[firstVal];
      for (size_t j=0; j<lookup.size(); j++)
      {
         const uint32_t key = lookup[j];
         uint8_t whichVector;
         uint32_t offsetIntoVector;
         GetVectorLocationFromKey(key, whichVector, offsetIntoVector);

         const vector<int> & bigVector = big_vectors[whichVector];
         if (SubstringExistsAtOffset(&bigVector[offsetIntoVector], substring)) resultVec.push_back(key);
      }
   }
   std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

   cout << " Total time spent finding " << substrings.size() << " substrings was " << std::chrono::duration_cast<std::chrono::milliseconds>(end-begin).count() << " milliseconds." << std::endl;

   cout << endl << endl << "RESULTS:" << endl;
   for(size_t i=0; i<results.size(); i++)
   {
      const vector<uint32_t> & result = results[i];
      for (size_t j=0; j<result.size(); j++)
      {
         const uint32_t key = result[j];
         uint8_t whichVector;
         uint32_t offsetIntoVector;
         GetVectorLocationFromKey(key, whichVector, offsetIntoVector);

         cout << "An instance of substring #" << i << " was found in bigVector #" << (int)whichVector << " at offset " << offsetIntoVector << endl;

         // Let's just double-check that the substring actually exists where I said it did
         // It would be embarrassing to find out I'm not actually finding them correctly :P
         const vector<int> & bigVector = big_vectors[whichVector];
         const vector<int> & substring = substrings[i];
         for (size_t k=0; k<substring.size(); k++)
         {
            if (bigVector[offsetIntoVector+k] != substring[k]) cout << "ERROR BAD RESULT in substring #" << i << " at offset " << k << endl;
         }
      }
   }
}