java - 如何从字符串中进行插值搜索

Question

插值搜索是二分搜索的一种改进，在二分搜索中，通过计算在每次迭代中将输入分成相等的两半。您可以对整数进行插值搜索，如下所示。

public static int interpolationSearch(int[] sortedArray, int toFind) {
    int low = 0;
    int high = sortedArray.length - 1;
    int mid;
    while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
        if (sortedArray[high] - sortedArray[low] == 0)
            return (low + high) / 2;
        // out of range is possible here
        mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]);

        if (sortedArray[mid] < toFind)
            low = mid + 1;
        else if (sortedArray[mid] > toFind)
            high = mid - 1;
        else
            return mid;
    }
    if (sortedArray[low] == toFind)
        return low;
    // not found
    else
        return -1;
}

但是对于字符串来说，上面的算法是不能直接使用的。这里大部分的比较都可以用java的compareTo方法代替。但是，对字符串执行以下操作的最佳方法是什么？

mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]);  

Answer 1

如果您将字符串视为以 K 为基数的分数，则按比例插值字符串是有意义的，其中 K 是字母表中的字符数，隐含的小数点位于字符串的前面。例如，

.aaa < .aaaa < .aaaaa

就像

.111 < .1111 < .11111

通过这种解释，我们可以在任何通常的情况下使用带有参数 T 的 x 和 y 的正常数值插值表格。

I(T) = T * x + (1 - T) * y = y + T * (x - y)

对于插值搜索，我们知道 I(T)。这是我们要搜索的字符串，写成基数 K 分数。而我们要找到T * D，其中D是当前搜索“差距”的大小。通过一些简单的代数，我们得到:

T * D = D * (I(T) - y) / (x - y)

x 和 y 是基数 K 分数，即内插字符串。

诀窍是以合理有效的方式实现该算法。这个公式的一个好处是我们可以按相同的因子缩放 x、y 和 I(T)，它仍然成立.因此，我们可以将它们扩展为 BigInteger，只要三个字符串中最长的一个即可，假设字符整理为无符号字节。因此 K=256。然后该部门只是截断以获得所需的索引。这是一个快速的技巧。它可能包含错误，但这个想法是正确的。

import java.math.BigInteger;
import static java.math.BigInteger.ZERO;
import static java.nio.charset.StandardCharsets.US_ASCII;
import static java.util.Arrays.copyOf;
import static java.lang.Math.max;

public class InterpolationSearch {
  static int interpolate(String ys, String xs, String iOfTs, int id) {
    int maxLen = max(max(xs.length(), ys.length()), iOfTs.length());
    BigInteger x = new BigInteger(1, copyOf(xs.getBytes(US_ASCII), maxLen));
    BigInteger y = new BigInteger(1, copyOf(ys.getBytes(US_ASCII), maxLen));
    BigInteger iOfT = new BigInteger(1, copyOf(iOfTs.getBytes(US_ASCII), maxLen));
    BigInteger d = BigInteger.valueOf(id);
    BigInteger den = x.subtract(y);
    return ZERO.equals(den) ? 0 : (int) d.multiply(iOfT.subtract(y)).divide(den).longValue();
  }

  static int search(String [] a, String target) {
    int p = 0;
    int q = a.length - 1;
    while (target.compareTo(a[p]) >= 0 && target.compareTo(a[q]) <= 0) {
      int m = p + interpolate(a[p], a[q], target, q - p);
      int cmp = target.compareTo(a[m]);
      if (cmp < 0) q = m - 1;
      else if (cmp > 0) p = m + 1;
      else return m;
    }
    return -1; // search fail
  }

  public static void main(String [] args) {
    String [] data = {
      "bbbb",
      "cccccccc",
      "ddd",
      "eeeeeee",
      "fffff",
      "ggggggggggggggg",
      "hhhhh",
    };   
    for (int i = 0; i < data.length; ++i) {
      System.out.println(search(data, data[i]));
    }
    System.out.println(search(data, "bbb"));
    System.out.println(search(data, "hhhhhh"));
    System.out.println(search(data, "eeeee"));
  }
}

正如您所希望和期望的那样，对数据数组中的值的搜索每次都需要一次迭代，但有一种情况需要两次。

补充说明

我想指出，上面的代码很有趣，而且有效，但是使用 Latin-1 字符代码的简单插值在用于现实世界的集合字符串时性能不佳。这是因为 256 个可能的字符值中的大块包含很少或没有字符。例如。缺少的字符在上面被编码为 0，但根本不可能有任何字符串的代码介于 0 和 64 之间。如果所有单词都是小写，情况会更糟，因为这会将空范围扩展到 95。大部分未使用的代码倾斜插值。为避免这种情况，请转换为基数 K 分数，其中 K 是字符串中实际使用的字符数，这些字符将映射到值 0 到 K-1。

即便如此，只有当所有字符以大致相等的频率和随机位置出现时，您才会获得好的结果。真正的字符串通常缺少这些属性。

这一切都是为了解释为什么在实践中很少使用插值搜索。真实数据集可能非常不随机。