java - 使用 Arrays.binarySearch 将字符串与对象进行比较

Question

我正在研究后缀数组的实现，用于加速短语搜索。

我有一个“后缀”对象数组，这是后缀数组。每个后缀对象都有两个值:文档和位置。

我有一个比较器，它根据使用两个值文档和位置在字符串字典中的查找来对该数组进行排序。 (例如，一个 document=1、position=5 的后缀对象指向“fish”，另一个对象指向“cake”。“Cake”将排序在“fish”之前。这很好用，并且后缀数组按预期按字典顺序排序

但是现在我想在这个后缀数组中进行二分查找查找，这次的输入是一个字符串。如何将 Arrays.binarySearch() 与我制作的比较器一起使用来比较字符串键(我正在搜索的短语)来搜索后缀数组？如果 binarySearch() 方法允许我在比较器中以某种方式执行此操作，那么将字符串与 Suffix 对象进行比较将是微不足道的...

Answer 1

不确定我是否完全理解，但这是我的想法:

修改类中的 compareTo 方法，如下所示:

class Suffix implements Comparable<Object>
{
   /* ... */

   int getDocumentId() { /* ... */ }
   int getPosition() { /* ... */ }

   @Override
   public int compareTo(Object o)
   {
      if (o.getClass() == String.class)
      {
         /* Derived from compare code comment */
         String key = dictionary.getDocument(getDocumentId()).getData();
         String suffix = (getPosition() == 0) ? key : key.substring(getPosition());

         suffix.compareTo((String)o);
      }
      else
      {
         /* same as original comparison */
      }
   }
}

那么你可以这样做:

Arrays.binarySearch(yourArray, yourString);