0

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

我有一个“后缀”对象数组，这是后缀数组。每个 Suffix-object 都有两个值，document 和 position。

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

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

4

1 回答 1

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);
于 2013-02-26T19:45:26.460 回答