将一百万个字符串映射到 C++11 中的整数

Question

我有一百万个 ASCII 字符串，没有重复，每个字符串最多 7 个字节。我需要将每个字符串映射到一个正整数。这些整数中最大的应该不超过一百万。虽然初始化可能很慢，但查找应该很快：给定一个字符串，return对应的整数（或 - 1，如果没有找到）。如何在 C++11 中实现这一点？

一个解决方案：将字符串累加成一个std::unordered_map<string,int>；然后迭代地图，从递增计数器分配整数。然后去查找，就unordered_map::find("foo")->second。但它闻起来像其他一些容器会更快并且开销更少（内置索引，而不是手动编码）。也许 unordered_set 和指针算术??

范围限制似乎使完美哈希变得困难。

（int 的范围是有限的，因为它索引到传递给 svm_light 的特征向量。该软件不使用稀疏存储，因此具有数万亿（大部分为零）元素的向量使其成为运行内存不足。所以这种字符串到整数的预处理实现了一种稀疏数据结构。）

Answer 1

你所描述的看起来像 perfect hashing。

有实现完美哈希的 C++ 库，例如 Tiny perfect hash library for C, C++, and Lua。

Answer 2

如果您正好有数百万个字符串，每个字符串恰好有 7 个字节长，那么这是使用基数排序的完美先决条件；所以基本上首先你将所有 10^6 个字符串存储在大数组中（它只有 7MB/6.7MiB，所以很容易管理），然后使用基数排序算法排序 - 时间复杂度 O(wn), w = 7, n = 10^6 在你的情况下，可以实现 in situ .实现的细节对于保持线性复杂度的低常数很重要，但基数排序相当容易实现。

作为基数排序的替代方法，您可以简单地将字符串视为 uint64_t 并使用 std::sort（它实现了优化良好的内部排序，对于您的约束，它的性能可能与基数一样好，尽管时间复杂度更高）。

一旦数组被排序，你就遍历它并将数组的索引放入普通的 std::unordered_map 中，以字符串作为键。所以最后你在基本线性时间内创建了完美的散列，并以平均 O(1).

的反向查找结束

[edit] 为了将字符串放入 unordered_map，您可能想要实现自己的哈希算法，我建议使用 djb2，它具有良好的统计特性并且是易于实施。

Answer 3

将您的字符串转换为 int64_t，将它们存储在 unordered_set 中，并将迭代器用作唯一索引。实际上，您将实现 O(1) 查找，加上 O(N) 计算迭代器偏移量。您还将保证最大索引不会超过数组的大小。

  unordered_set<int> s;
  s.insert(10);
  s.insert(2000000);
  s.insert(5000000);

  int index = std::distance(s.find(10), s.end());
  cout << index << endl;
  index = std::distance(s.find(2000000), s.end());
  cout << index << endl;
  index = std::distance(s.find(5000000), s.end());
  cout << index << endl;

输出：

1
2
3

既然你有一个独特的映射，使用unordered_map来实现你的目标，并丢弃unordered_set:

  unordered_set<int> s;
  unordered_map<int,int> m;
  s.insert(10);
  s.insert(2000000);
  s.insert(5000000);

  int index = std::distance(s.find(10), s.end());
  m[10] = index;
  cout << index << endl;
  index = std::distance(s.find(2000000), s.end());
  m[2000000] = index;
  cout << index << endl;
  index = std::distance(s.find(5000000), s.end());
  m[5000000] = index;
  cout << index << endl;

  s.clear();
  cout << m[10] << " " << m[2000000] << " " << m[5000000] <<  endl;

查找将是 O(1)。

将一百万个字符串映射到 C++11 中的整数

map a million strings to ints in c++11

string

dictionary

svm

sparse-matrix

c++11