java - Java中的后缀数组实现

Question

我正在寻找一种有效的 n 阶马尔可夫链方法来生成给定一组示例文本的随机文本字符串。我目前有一个使用多层地图的 Java 实现，但它很笨重。后缀数组非常适合我的需求，但我不清楚这是否可以在 Java 中有效实现。

在 CI 中可能会执行以下操作：

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

这在 Java 中变得很棘手，因为我必须获取 的子字符串exampleText，或者变成suffixArray索引数组或其他东西。

对 Java 中的一个好的方法有什么建议吗？

Answer 1

对于任何对在 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 阵列的情况下进行构建。

Answer 2

String[通常] 会为您做到这一点。（典型的实现在使用 创建时共享支持数组substring，尽管这可能随时更改。）

Answer 3

您可以使一些变体形成后缀数组：

第一的：

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;
}