Декодирование bitString с использованием таблицы кодов Хаффмана Java - PullRequest
0 голосов
/ 08 ноября 2018

Цель состоит в том, чтобы преобразовать bitString в простой текст, используя кодовую таблицу Хаффмана,

r=000
h=001
o=01
w=100
d=1010
e=1011
l=11

Я сохранил таблицу кодов Хаффмана в двух разных String[] массивах:

String[] ch = {"r", "h", "o", "w", "d", "e", "l"};
String[] b = {"000", "001", "01", "100", "1010", "1011", "11"};

Согласно таблице кодов Хаффмана следующая битовая строка эквивалентна строке "helloworld".

String bits = "001101111110110001000111010";

Теперь я хочу пройтись по каждому набору битов, чтобы найти соответствующий ему символ:

StringBuilder sb = new StringBuilder();

for(int i = 0; i < bits.length(); i++) {
    if(bits.substring(0, b[i].length()).equals(b[i])) {
        sb.append(ch[i]);
        bits = bits.substring(b[i].length());
    }
}

Проблема здесь в том, что каждый раз, когда найдено совпадение, я не могу найти способ «сбросить» цикл и вернуться к b[0], чтобы я мог проверить b[i] с самого начала.

1 Ответ

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

Вам нужно прочитать в исходных данных «бит» за «бит» и каждый раз проверять, является ли он сейчас действительным кодом Хаффмана. Вместо массивов я предлагаю использовать Map (в качестве альтернативы вы можете настроить древовидную структуру и проходить, хотя и шаг за шагом), в противном случае производительность становится очень медленной, потому что для каждого бита приходится проходить весь массив целиком. время.

Вот пример использования таблицы кодов Хаффмана:

import java.util.HashMap;


public class HuffmanDecoder {
    private static HashMap<String, String> huffMap = new HashMap<>();

    static {
        huffMap.put("000", "r");
        huffMap.put("001", "h");
        huffMap.put("01", "o");
        huffMap.put("100", "w");
        huffMap.put("1010", "d");
        huffMap.put("1011", "e");
        huffMap.put("11", "l");
    }

    public final static void main(String[] args) {
        char[] bits = "001101111110110001000111010".toCharArray();

        StringBuffer result = new StringBuffer();
        StringBuffer temp = new StringBuffer();
        for (int i = 0; i < bits.length; i++) {
            temp.append(bits[i]);
            String val = huffMap.get(temp.toString());
            if (val == null) {
                continue;
            }
            result.append(val);
            temp.setLength(0);
        }

        System.out.println(result);
    }
}

Как только правильный код найден, соответствующее декодированное значение добавляется в буфер результатов, и временный буфер сбрасывается. Отсутствует некоторая обработка ошибок при получении данных, которая не приводит к действительному значению кода, но реализация которого зависит от фактического кода, например, для SFF-данных (факсимильных изображений) декодер продолжает считывание, пока не достигнет маркера конца строки.

...