0

我想解决 Levenshtein_distance这个字符串长度太大的问题。

Edit2：
正如Bobah所说的那样，标题是小姐领先，所以我更新了 questoin 的标题。
初始title was如何在 C++ 中声明 100000x100000 二维整数？
Content was
有任何方法可以在 c++ 中声明 int x[100000][100000] 。
当我全局声明它时，编译器会生成 error: size of array ‘x’ is too large.
一种方法可能是使用map< pair< int , int > , int > mymap.
但是分配和解除分配需要更多时间。
还有其他像 uisng 的方式vector<int> myvec；

4

3 回答 3

3

对于这么大的内存块，最好的方法是使用操作系统为进程添加虚拟内存的工具进行动态分配。

但是，请查看您尝试分配的块有多大：

 40 000 000 000 bytes

我收回我之前的建议。对于这么大的块，最好的方法是分析问题并找出使用更少内存的方法。

于 2014-10-05T12:51:22.333 回答
2

可以一次对每一行进行填充编辑距离矩阵。记住前一行就足以计算当前行。这种观察将空间使用从二次方减少到线性。说得通？

于 2014-10-05T13:14:36.880 回答
0

您的问题很有趣，但标题具有误导性。

这就是您在数据模型方面所需要的（x - 第一个字符串，y - 第二个字符串，* - 距离矩阵）。

      y <-- first string (scrolls from top down)

      y
  x  x  x  x  x  x  x  x  <- second string (scrolls from left to right)
      y *  *  *

      y *  *  *

      y *  *  * <-- distance matrix (a donut) scrolls together with strings
                    and grows/shrinks when needed, as explained below
      y

有两个相对较长（但仍然 << N）的字符缓冲区和相对较小的（<< 缓冲区大小）矩形（从正方形开始）距离矩阵。

使矩阵成为一个甜甜圈- 二维环形缓冲区（可以使用 boost 中的一个，或者只是 std::deque）。

当当前被矩阵覆盖的字符串片段是 100% 匹配时，将两个缓冲区移动一个，围绕两个轴旋转甜甜圈，重新计算距离矩阵中的一个新行/列。

当匹配 <100% 并且小于配置的阈值时，然后在不删除任何行/列的情况下增加甜甜圈的两个维度的大小，并执行此操作直到任一匹配高于阈值或达到最大甜甜圈大小。当匹配率从下面达到阈值时，您需要滚动甜甜圈丢弃 x 和 y 缓冲区的头部并同时对齐它们（当距离矩阵告诉 X [i] 在 Y 中不存在时，只有 X 需要移动 1 , 但 X[i+1,i+m] 匹配 Y[j, j+m-1])。

因此，您将拥有一个简单但非常有效的启发式差异引擎，具有确定性有限的内存占用，并且所有内存都可以在启动时预先分配，因此在运行时没有动态分配会减慢它的速度。

Apache v2 许可证，以防您决定使用它。

于 2014-10-05T17:49:02.743 回答