Как я могу оптимизировать декодирование Хаффмана? - PullRequest
Новая
       10

Как я могу оптимизировать декодирование Хаффмана?

0 голосов
/ 11 ноября 2018

Итак, я пытался декодировать, используя huffman, и у меня есть эта рабочая функция, но она имеет ужасную временную и пространственную сложность. До сих пор я читал каждый байт, получал каждый бит и добавлял его в currentBitString. Затем я перевернул строку и добавил ее к огромной строке, которая в основном содержит все байтовые данные для файла. После этого я прослеживал гигантскую строку и искал код Хаффмана, а затем, если он совпадал, я записывал в файл. Этот код занимает около 60 секунд для декодирования 200 КБ, что очень плохо, но я не совсем уверен, как его улучшить? Я знаю, что могу для начала записать в файл более одного байта за раз, но, похоже, это не улучшило время, когда я пытался? 

         public static void decode(File f) throws Exception {

    BufferedInputStream fin = new BufferedInputStream(new FileInputStream(f));
    int i = f.getName().lastIndexOf('.');
    String extension="txt";
    String newFileName=f.getName().substring(0, i)+extension;
    File nf = new File(newFileName);
    BufferedOutputStream fw = new BufferedOutputStream(new FileOutputStream(nf));
    int c;
    byte bits;
    byte current;
    String currentBitString="";
    String bitString="";
    //read each byte from file, reverse it, add to giant bitString
    //reads ALL BYTES
    while( (c=fin.read())!=-1 ) {
        current=(byte) c;
        currentBitString="";
        bits=0;
        for(int q=0;q<8;q++) {
            bits=getBit(current,q);
            currentBitString+=bits;
        }
        StringBuilder bitStringReverse=new StringBuilder(currentBitString);
        bitString+=bitStringReverse.reverse().toString();
    }
    currentBitString="";
    boolean foundCode=false;
    for(int j=0;j<bitString.length();j++) {
        currentBitString+=bitString.charAt(j);
        for(int k=0;k<nodes.length;k++) {
            //nodes is an array of huffman nodes which contains the the byte 
            //data and the huffman codes for each byte
            if(nodes[k].code.compareTo(currentBitString.trim())==0) {
                fw.write(nodes[k].data);    
                foundCode=true;
                break;
            }
        }
        if(foundCode) {
            currentBitString="";
            foundCode=false;
        }

    }
    fw.flush();
    fw.close();
    fin.close();

}

вот функция gitBit 

        public static byte getBit(byte ID, int position) {
        // return cretin bit in selected byte
        return (byte) ((ID >> position) & 1);
        }

вот члены данных класса HuffmanNode (массив узлов - это массив HuffmanNodes) 

       public class HuffmanNode{
       byte data;
       int repetitions;
       String code;
       HuffmanNode right;
       HuffmanNode left;
       }

Ответы [ 2 ]

0 голосов
/ 11 ноября 2018

  1. Не читайте все это в память.Обработайте ваши коды так, как они встречаются.Считайте достаточное количество битов для декодирования следующего кода, декодируйте его, сохраните неиспользованные биты для последующего кода, повторите.

  2. Не используйте строки символов для представления битов, где вы представляетеодин бит на символ.Используйте биты для представления битов.Смена, и, и или операторы - это то, что вы должны использовать.В качестве битового буфера у вас будет целое число со всеми битами, которые вам понадобятся для декодирования следующего кода.

  3. Не выполнять поиск по всем длинам кода, а внутри этого линейногопоиск всех кодов, чтобы найти ваш код!Мне было бы трудно придумать более медленный подход.Вы должны использовать спуск по дереву или поиск по таблице для декодирования.Если вы сначала сгенерируете канонический код Хаффмана , существует простой подход поиска, который можно реализовать.См. puff.c для примера.Подход в учебнике (который медленнее, чем в puff.c) состоит в том, чтобы построить одно и то же дерево Хаффмана на принимающей стороне и постепенно переходить вниз по этому дереву, пока не дойдете до символа.Изобразите символ и повторите.

Вы должны быть способны обработать 200 КБ сжатого ввода за несколько миллисекунд на одном ядре современного процессора.

0 голосов
/ 11 ноября 2018

Вы можете заменить конкатенацию строки += на StringBuilder. Это распределяет меньше объектов и уменьшает нагрузку на сборщик мусора. 

int c;
StringBuilder bitString = new StringBuilder();
//read each byte from file, reverse it, add to giant bitString
//reads ALL BYTES
while ((c = fin.read()) != -1) {
    byte current = (byte) c;
    StringBuilder currentBitString = new StringBuilder();
    for (int q = 0; q < 8; q++) {
        byte bits = getBit(current, q);
        currentBitString.append(bits);
    }
    bitString.append(currentBitString.reverse());
}

Вместо помещения кодов и данных в массив nodes здесь следует использовать HashMap. Вы сравниваете код, перебирая весь массив, пока не найдете правильное соответствие. В среднем это n/2 звонков на String#equals() за единицу. С HashMap вы уменьшаете это до ~ 1.

Заполните карту данными для кодов в качестве ключей. 

Map<String, Integer> nodes = new HashMap<>();
nodes.put(code, data);

Доступ к данным с карты 

boolean foundCode = false;
for (int j = 0; j < bitString.length(); j++) {
    currentBitString.append(bitString.charAt(j));
    Integer data = nodes.get(currentBitString.toString().trim());
    if (data != null) {
        fw.write(data);
        foundCode = true;
    }
    if (foundCode) {
        currentBitString = new StringBuilder();
        foundCode = false;
    }
}
...