0

フレーズ検索の高速化に使用する Suffix Array の実装に取り​​組んでいます。

「サフィックス」オブジェクトの配列があります。これがサフィックス配列です。各 Suffix-object には、document と position の 2 つの値があります。

document と position の 2 つの値を使用して、文字列の辞書の検索に基づいてこの配列を並べ替える Comparator があります。(たとえば、document=1、position=5 の 1 つの接尾辞オブジェクトは「魚」を指し、別のオブジェクトは「ケーキ」を指します。「ケーキ」は「魚」の前にソートされます。これは問題なく機能し、接尾辞配列は辞書順で期待どおりにソートされます

ただし、このサフィックス配列でバイナリ検索ルックアップを実行したいのですが、今回の入力は文字列です。Arrays.binarySearch() を作成した Comparator で使用して、文字列キー (検索しているフレーズ) を比較してサフィックス配列を検索するにはどうすればよいですか? String と Suffix オブジェクトを比較するのは、binarySearch() メソッドを使用して Comparator で何らかの方法で実行できる場合は簡単です...

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 に答える