Java中后缀数组的实现

发布于 2024-09-12 05:45:32 字数 410 浏览 8 评论 0原文

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

在 CI 中可能会做类似的事情：

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

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

有什么关于 Java 中的好方法的建议吗？

原文

I'm looking to write an efficient n-order Markov chain method to generate random text strings given a set of example text. I currently have a Java implementation that uses several layers of Maps, but it's clunky. A suffix array would be perfect for my needs, but I'm not clear if that can be efficiently implemented in Java.

In C I might do something like:

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

This gets gnarly in Java since I'd have to take substrings of exampleText, or turn suffixArray into an array of indices, or something else.

Any suggestions for a good approach to this in Java?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

夏花。依旧 2024-09-19 05:45:32

String [通常]会为您完成此操作。（典型的实现在使用substring创建时共享支持数组，尽管这可能随时发生变化。）

回复收藏 0 原文

浪漫之都 2024-09-19 05:45:32

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

For anyone interested in more efficient ways of constructing the suffix array in Java, I once used a library called jsuffixarrays. The code is here. It offers a range of construction algorithms to choose from and I found it to work very well. E.g. to use the SKEW algorithm you do this:

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();

You can build without the LCP array if don't need that.

回复收藏 0 原文

独孤求败 2024-09-19 05:45:32

您可以从后缀数组中创建一些变体：

第一：

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

You can make some variants form array of suffixes:

First:

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

Second:

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

回复收藏 0 原文

~没有更多了~