使用Arrays.binarySearch比较字符串与对象

我正在研究用于加快短语搜索的后缀数组实现。我有一个“后缀”对象的数组，这是后缀数组。每个后缀对象都有两个值，文档和位置。使用Arrays.binarySearch比较字符串与对象

我有一个比较器，它使用两个值文档和位置基于字符串字典中的查找来对此数组进行排序。（例如，一个文档为1的后缀对象，位置= 5指向“鱼”，另一个对象指向“蛋糕”，“蛋糕”将被排序在“鱼”的前面，这工作得很好，后缀数组按照字面顺序排序如下

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

来源

2013-02-26 ponycat

你有可能包括代码样本，你要完成？ – Zack 2013-02-26 19:10:42

您的标题中是否忘记了“SuffixTree”？ – 2013-02-26 19:13:54

@moose：不。带帽子的男人是来自流行电视连续剧“绝命毒师”的“海森堡”。我不知道KIT是什么，我也没有发布任何关于这个问题的地方。 – ponycat 2013-02-26 19:48:19

不知道我是否完全理解，但这里是我的想法：

修改您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-26 19:45:26 Dukeling

问题是它指向的字符串没有保存在我的对象中。有一个单独的“存储”，我可以使用ints文档和位置访问，并从该存储中获取字符串。 – ponycat 2013-02-26 20:08:21

@ponycat请参阅编辑。 – Dukeling 2013-02-26 20:18:01

非常感谢您的时间和帮助！虽然你的解决方案不适合我的实现（主要是由于我对真实问题的可怕解释），但它有助于指向另一个解决方案的正确方向。再次感谢！ – ponycat 2013-02-26 21:23:16

使用Arrays.binarySearch比较字符串与对象

回答

相关问题