Суффиксная реализация массива в Java

Question

Я собираюсь написать эффективный метод цепей Маркова n-го порядка для генерации случайных текстовых строк на основе набора примеров текста. В настоящее время у меня есть реализация Java, которая использует несколько слоев карт, но это неуклюже. Суффиксный массив был бы идеален для моих нужд, но я не уверен, может ли это быть эффективно реализовано в Java.

В C я мог бы сделать что-то вроде:

char exampleText[MAX];
char *suffixArray[MAX];
...
while(n<MAX && suffixArray[n++] = &exampleText[n]);
sort(suffixArray);

Это ужасно в Java, так как мне нужно было бы взять подстроки exampleText или превратить suffixArray в массив индексов или что-то еще.

Какие-нибудь предложения для хорошего подхода к этому в Java?

Answer 1

String [обычно] сделает это за вас.(Типичные реализации совместно используют резервные массивы при создании с substring, хотя это может быть изменено в любое время.)

Answer 2

Вы можете сделать несколько вариантов из массива суффиксов:

Первый:

public static String[] suffixes(String s)
{
int N = s.length();
String[] suffixes = new String[N];
for (int i = 0; i < N; i++)
suffixes[i] = s.substring(i, N);
return suffixes;
}

Второе:

public static String[] suffixes(String s)
{
int N = s.length();
StringBuilder sb = new StringBuilder(s);
String[] suffixes = new String[N];
for (int i = 0; i < N; i++)
suffixes[i] = sb.substring(i, N);
return suffixes;
}

Answer 3

Для тех, кто интересуется более эффективными способами построения массива суффиксов в Java, я однажды использовал библиотеку под названием jsuffixarrays .Код здесь .Он предлагает широкий выбор алгоритмов построения, и я нашел, что он работает очень хорошо.Например, чтобы использовать алгоритм SKEW, вы делаете это:

import org.jsuffixarrays.Algorithm;
import org.jsuffixarrays.ISuffixArrayBuilder;
import org.jsuffixarrays.SuffixArrays;
import org.jsuffixarrays.SuffixData;

String              exampleText = "....";
ISuffixArrayBuilder suxBuilder  = Algorithm.SKEW.getDecoratedInstance();
SuffixData          sux         = SuffixArrays.createWithLCP(text,sux_builder);

/* Then, to access the suffix array: */
sux.getSuffixArray();
/* And, to access the LCP array: */
sux.getLCP();

Вы можете построить без массива LCP, если вам это не нужно.