问题：如何选取将每个插值段中任何点的最大误差保持在指定范围内？
目标是使用逆变换抽样根据齐普夫定律塑造随机分布。我在这里找到了 Zipf 归一化因子的一个很好的近似值：
https://arxiv.org/abs/1511.01480 (毛里齐奥·纳尔迪(Maurizio Naldi(的"截断的Zeta分布和齐普夫定律的近似"(
我现在正在做的是创建 CDF 值与秩的样条曲线，并尝试设置一个误差边界，以便对于任何秩，插值的偏差都超过其值的一定百分比(相对误差(。如果我的样条点太多，那会浪费内存。如果我的点太少，就会增加错误。我试图找到样条点的最佳位置，以平衡这两者。
我目前的方法(失败(是遍历所有等级并查看连续等级之间 PDF 值的差异。此差值是一阶导数的代理。我跟踪差值的 MIN 和 MAX 值，当它们与 CDF 成比例差异太大时，我假设曲线弯曲得太大，我添加了一个新的插值点并开始跟踪整个差异。此算法产生的插值点太少，因为误差的累积速度比我预期的要快。
我还有另一个想法：保持两个指针，一个在增长段的末尾，另一个在前进速度一半的中点。当中点的误差变得太大时，添加新的插值点。但是，我不确定最糟糕的错误是否一定在范围的中间。
我可以存储所有等级的 CDF 值(使用大量内存 - 我当前的应用程序的最大等级为 50 万(。然后，我可以详尽地测试建议段的每个插值，并在误差太大时停止。我可以超调并进行二进制搜索以找到最佳段长度 - 更快，但仍然需要大量内存。我希望使用具有适度内存开销的单通道或双通道在线算法。
顺便说一下，对于每个样条线段，我尝试了以下插值函数：
-
线性 - 结果不佳。
-
二次 - 更好，但仍然很差。
-
双曲 - 适用于两倍于二次曲线的线段，但仍然不够好。(如果我找到更好的方法来选择插值点，这可能就足够了。
注意：双曲比预期更好，因为高斯分布像大多数其他分布一样为 CDF 生成 S 曲线，而 Zipf PDF 在开始时有峰值，因此它的 CDF 看起来像一条双曲线，渐近线在一个
。更新：
我采纳了我的一个想法。我跟踪样条线段的中点，因为它随着第二个指针的增长而增长，当中点的误差变得太大时，我结束该段并开始另一个。正如预期的那样，中点不是误差最大的地方，所以我将我的理想误差除以 7，如果中点误差超过该误差，我开始一个新的段。
以上还不够。我发现由于最后一个段保证在 CDF = 1 处结束，因此最后一个段实际上到达渐近线。我的双曲线曲线拟合公式预计在秩达到无穷大之前不会达到渐近线，因此这引入了错误。因此，对于 CDF = 1 附近的最后几个段，我回退到使用抛物线拟合。
上述方法对 CDF 误差产生了良好的结果，但有时会导致往返计算的结果不佳。如果我要求给定等级的 CDF，然后在反向查找中使用该 CDF 来查找排名，则生成的排名并不总是与原始等级匹配。我仍在研究如何纠正此往返错误。
我解决了往返协议不佳的问题。秩到 CDF 函数的水平渐近线为 1。反函数在 N 处有一个垂直渐近线。我有错误的插值函数！
我发现延长段直到中点误差太大是一个很好的解决方案，与将每个段拟合到双曲线(最后一个段(或几个段(之外，我使用拉格朗日二次插值多项式拟合到二次曲线。
对于 N = 10000，我需要大约 200 个插值点来保持非常低的误差。但是，如果我只是使用 Zipf 发行版进行测试，那么 30 个就足够了。