Блог

Здравствуйте, у меня возникли некоторые трудности с оптимизацией преобразования Берроуза Уилера. Я пытаюсь преобразовать текстовые файлы, однако преобразование больших текстовых файлов, таких как Библия, занимает слишком много времени.

Есть идеи о том, как действовать дальше?

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

В случае кодирования вам не нужно фактически создавать массив строк — вместо этого используйте массив int (или long в зависимости от размера вашего файла) для хранения индекса, с которого начинается ваша вращающаяся строка.

• Создайте массив, инициализированный в [0 1 2 3 … n]

• отсортируйте массив с помощью следующего сравнения (предположим, 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» в массиве и добавьте его в свой вывод в качестве начального значения

В обратном порядке, опять же, мы хотели бы избежать построения всей таблицы для текста размером с Библию. Мы можем сделать это, используя тот факт, что идентичные токены в первой и последней строке всегда находятся в одном и том же порядке. Это верно, потому что первая строка отсортирована, а токены расположены циклически: для трех последовательных b в последней строке сортируются токены после них, поэтому b сортируются. Итак, чтобы обратить:

• отсортируйте выходные токены. Наряду с сохранением отсортированных токенов, сохраните индекс, с которого начинался каждый токен. Таким образом, для несортированных токенов «nbnaa» необходимо сохранить [3 4 5 2 0 1] и «aaabnn». Важно: для этого шага вы ДОЛЖНЫ использовать стабильную сортировку.

• используйте значение «start», упомянутое ранее, чтобы перестроить строку:

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

Эта строка:

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

собирается создавать копию всего входного текста каждый раз, когда вы его вызываете. Поскольку вы вызываете его N раз для входного текста из N символов, ваш алгоритм будет O(N^2) .

Посмотрите, сможете ли вы оптимизировать originalSuffix метод, чтобы избежать такого копирования.