1

こんにちは、burrows wheeler transformの最適化に苦労しています。テキスト ファイルを変換しようとしていますが、聖書のような大きなテキスト ファイルの変換には時間がかかりすぎます。

続行する方法について何か考えはありますか？

public BurrowsWheelerTransformEncoder()
{

}

private String originalSuffix(int index, String string)
{
    String temp = (string.substring(index,string.length()) + string.substring(0,index));

    //this bit just 'compresses' each transformation of text by producing
    //a prefix, so 'abracadabra' just becomes 'abrac'
    //this is so minimal amount of memory is used when it is stored in an array

    return temp.substring(0,5)+
    //the last character of the transformation is kept
           temp.charAt(temp.length()-1);
}

private String compressedSuffix(String string)
{
    //this method just 'compresses' original piece of text by producing
    //a prefix, so 'abracadabra' just becomes 'abrac'
    //this is so comprisons won't take so long
    return string.substring(0,5)+string.charAt(string.length()-1);
}

public static void main(String args[]) throws Exception
{
    BurrowsWheelerTransformEncoder encoder = new BurrowsWheelerTransformEncoder();
    BufferedReader input = new BufferedReader(new FileReader("src/compressionalgorithm/texts/manifesto.txt"));

    String text = "";
    //the row in the sorted array where the original text can be found
    int originalRow = 0;
    //system time when program began
    long startTime = System.nanoTime();

    //get text from file
    while(input.ready())
    {
        text += input.readLine();
    }
    //create a new array to hold all transformations
    String[] textArray = new String[text.length()];
    int length = text.length();

    //get individual transformations and put in array
    for(int i = 0; i < text.length(); i++)
    {
        textArray[i] = encoder.originalSuffix(i,text);
        //for debugging large text files, prints progress after every 10k'th 
        //transformation
        if(i%10000==0)
        System.out.println(i+"/"+length);
    }
    //uses java's internal methods to sort the array, presumably 
    //the most efficient way to do the sort (for now)
    Arrays.sort(textArray);

    String compressedOriginalText = encoder.compressedSuffix(text);

    //print the results
    for(int i = 0; i < textArray.length; i++)
    {
        if(textArray[i].equals(compressedOriginalText))
        {
            originalRow = i;
        }
        if(i%100==0)
        {
            System.out.println();
        }
        System.out.print(textArray[i].charAt(textArray[i].length()-1));
    }
    System.out.println("\nThe original transformation of the text was found at row " + originalRow + " of the sorted array.");
    System.out.println("Time elapsed: " + (System.nanoTime() - startTime));
 }
4

2 に答える 2

3

コーディングの場合、文字列配列を実際に作成する必要はありません。代わりに int (またはファイル サイズによっては long) 配列を使用して、回転する文字列が開始するインデックスを格納します。

  • [0 1 2 3 ... n] に初期化された配列を作成します

  • 次のcompareToで配列をソートします（compareTo()元の文字列にアクセスできると仮定しますoriginal）：

    int compareTo(int a, int b){
    int compare, len = original.length();
    do{
        char _a = original.charAt(a), _b = original.charAt(b);
        compare = _a-_b;
        a++; b++;
        if(a>=len)a-=len;
        if(b>=len)b-=len;
    }while(compare==0);
    return compare;
}

  • 配列内の「0」のインデックスに注意し、それを「開始」値として出力に追加します

逆の場合も、聖書と同じ大きさのテキストのテーブル全体を構築することは避けたいと考えています。これは、最初の行と最後の行の同一のトークンが常に同じ順序であるという事実を利用して行うことができます。これは、最初の行がソートされ、トークンが周期的に配置されるためです。最後の行に 3 つの連続する b がある場合、それらの後のトークンがソートされるため、b がソートされます。逆に：

  • 出力トークンをソートします。ソートされたトークンを保存するとともに、各トークンが開始されたインデックスを保存します。したがって、ソートされていないトークン "nbnaaa" の場合、[3 4 5 2 0 1] と "aaabnn" を格納します。重要: このステップでは、安定ソートを使用する必要があります。

  • 前述の「開始」値を使用して、文字列を再構築します。

    string decode(string sorted, int[]index, int start){
    string answer = ""+sorted.charAt(start);
    int next = index[start];
    while(next!=start){
        answer = sorted.charAt(next) + answer;
        next = index[next];
    }
    return answer;
}
于 2011-11-08T18:46:45.013 に答える
1

この行：

    String temp = (string.substring(index,string.length()) + string.substring(0,index));

呼び出すたびに、入力テキスト全体のコピーを作成します。N 文字の入力テキストに対して N 回呼び出すため、アルゴリズムは になりますO(N^2)。

originalSuffixそのコピーを回避するためにメソッドを最適化できるかどうかを確認してください。

于 2011-05-14T07:19:13.713 に答える