1

一連のサンプルテキストを指定してランダムなテキスト文字列を生成するための効率的なn次マルコフ連鎖法を作成しようとしています。私は現在、マップのいくつかのレイヤーを使用するJava実装を持っていますが、それは不格好です。接尾辞配列は私のニーズにぴったりですが、それがJavaで効率的に実装できるかどうかはわかりません。

CIでは次のようなことをするかもしれません：

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

Javaでは、のサブストリングを取得するexampleTextかsuffixArray、インデックスの配列に変換する必要があるため、これは厄介になります。

Javaでこれに良いアプローチをするための提案はありますか？

4

3 に答える 3

2

String[通常]あなたのためにそれをします。（通常の実装は、で作成されたときにバッキングアレイを共有しますsubstringが、それはいつでも変更される可能性があります。）

于 2010-07-28T04:22:33.760 に答える
2

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アレイなしでビルドできます。

于 2012-02-25T02:35:24.963 に答える
1

接尾辞の配列からいくつかのバリアントを作成できます。

初め：

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

2番：

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;
}
于 2013-04-16T11:16:56.340 に答える