Привет, Habr! Я учусь на программиста в Питерском Политехе. Одно из моих заданий в курсовой работе было написание консольной утилиты. Решил поделиться своим небольшим опытом.

Для начала представлю вам саму формулировку задания, которое мне необходимо было выполнить:

Реализовать сжатие RLE (run-length encoding). Продумать алгоритм сжатия и формат файла, при котором сжатие «неудачных» данных не приводит к большому увеличению размера файла.

Command Line:
pack-rle [-z|-u] [-out outputname.txt] inputname.txt

Упаковывает -z или распаковывает -u указанный в аргументе командной строки текстовый файл. Выходной файл указывается как -out outputname.txt, по умолчанию имя формируется из входного файла с добавлением расширения.

Кроме самой программы, следует написать автоматические тесты к ней.


Сам алгоритм:
Кодирование длин серий (англ. run-length encoding, RLE) или кодирование повторов — алгоритм сжатия данных, заменяющий повторяющиеся символы (серии) на один символ и число его повторов. Серией называется последовательность, состоящая из нескольких одинаковых символов. При кодировании (упаковке, сжатии) строка одинаковых символов, составляющих серию, заменяется строкой, содержащей сам повторяющийся символ и количество его повторов.
Строка: WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWBWWWW
Превращается в строку: 9W3B24W1B4W
Однако я чуть улучшил алгоритм, убрав добавление 1 перед одиночным символом, чтобы избежать ситуации, когда сжатая строка длиннее исходной. («TBTB» -> «1T1B1T1B» «TBTB»)

Итак, приступим


Для начала я решил написать основную логику программы. Начнем с упаковщика.

Файл PackRLE.kt

//словарь для цифр, так как они у нас используются, как служебные символы
private val dictionary = mutableListOf('¦', 'A', 'A', 'A', 'A', 'A', 'A', '?', 'E','E')

fun encode(string: String): String {
    if (string == "") return ""

    //создаём StringBuilder
    val result = StringBuilder()
    //счётчик каждого отдельного символа
    var count = 0
    //предыдущий символ
    var prev = string[0]
    //перебираем символы
    for (char in string) {
        if (char != prev) {
            //как только встретили другой символ, выполняем этот код
            //если символов в строке больше одного
            //добавляем счётчик. 
            if (count > 1) result.append(count)
            //отдельная обработка цифр, так как они у нас используются как служебные 
            if (prev.isDigit()) result.append(dictionary.elementAt(prev - '0')) else result.append(prev)
            count = 0
            prev = char
        }
        count++
    }
    //повтор кода для обработки последнего символа
    if (count > 1) result.append(count)
    if (prev.isDigit()) result.append(dictionary.elementAt(prev - '0')) else result.append(prev)
    return result.toString()
}

Распаковщик:

fun decode(str: String): String {
    val result = StringBuilder()
    var i = 0
    while (i in str.indices) {
        //подстрока содержащая длину последовательности
        val times = str.substring(i).takeWhile { it.isDigit() }
        //times.count() - даёт понять сколько значное число определяет длину
        val count = times.count()
        //прибавляем это значение к текущему индексу, чтобы получить индекс символа
        //и ищем его в dictionary, чтобы определить цифру ли мы закодировали или другой символ
        val index = dictionary.indexOf(str[i + count])
        //если это цифра (index != -1), то вычисляем цифру
        val char = if (index != -1) '0' + index else str[i + count]
        //записываем символ в строку
        //times.toIntOrNull() вернёт null, если в times записано не число, либо строка пустая
        //?: 1 вместо null даст нам 1
        repeat(times.toIntOrNull() ?: 1) { result.append(char) }
        i += 1 + count
    }
    return result.toString()
}

Теперь напишем main() с функцией, отвечающей за взаимодействие с файлами:

fun main(args: Array<String>) {
    Parser.main(args)
}

fun packRLE(pack: Boolean, inputFile: String, outputFile: String?) {
    //разбиваем файл на строки
    val inputStrings = File(inputFile).readLines()
    //открываем выходной файл для записи
    val outputStream = File(outputFile ?: inputFile).bufferedWriter()
    outputStream.use {
        for (string in inputStrings) {
            //перебираем строки и отдаём каждую кодировать/декодировать
            val newString = if (pack) encode(string) else decode(string)
            //записываем строку в файл
            it.write(newString)
            it.newLine()
        }
    }
    //выводим на консоль сообщение
    println("Pack-rle: "+ if (pack) "pack" else {"unpack"}+" successful")
}

Теперь подробнее про парсер

Parser.main(args)

Я использовал готовую библиотеку args4j с некоторыми изменениями под свои задачи.

Файл Parser.java

public class Parser {
    //опция распаковка, по умолчанию false, не может быть вызвана одновременно с -z
    @Option(name = "-u", usage = "unpacking file", forbids = {"-z"})
    private boolean unpack = false;

    //опция упаковка, по умолчанию false, не может быть вызвана одновременно с -u
    @Option(name = "-z", usage = "packing file", forbids = {"-u"})
    private boolean pack = false;

    //опция выходной файл
    @Option(name = "-out", usage = "output to this file (default: inputname.txt)", metaVar = "OUTPUT")
    private String out;

    //остальные аргументы
    @Argument
    private List<String> arguments = new ArrayList<String>();

    public static void main(String[] args) {
        new Parser().parseArgs(args);
    }

    public void parseArgs(String[] args) {
        CmdLineParser parser = new CmdLineParser(this);
        try {
            //пытаемся пропарсить
            parser.parseArgument(args);
            //если аргументы в строке некорректные 
            //выводим соответствующее сообщение об ошибке
            if (arguments.isEmpty() || (!pack && !unpack) || (!arguments.get(0).equals("pack-rle") || arguments.size() != 2)) {
                System.err.println("Error entering arguments (for correct input, see the example)");
                System.err.println("pack-rle [options...] arguments...");
                parser.printUsage(System.err);
                System.err.println("\nExample: pack-rle [-u|-z] [-out outputname.txt] inputname.txt");
                //кидаем исключение для того, чтобы мы могли сделать тесты
                throw new IllegalArgumentException("");
            }
        } catch (CmdLineException e) {
            //обработка исключения, предусмотренного библиотекой
            System.err.println(e.getMessage());
            System.err.println("pack-rle [options...] arguments...");
            parser.printUsage(System.err);
            System.err.println("\nExample: pack-rle [-u|-z] [-out outputname.txt] inputname.txt");
            //аналогично
            throw new IllegalArgumentException("");
        }
        //передаём имя входного файла
        String input = arguments.get(1);
        //передаём нашей основной функции парсированные агрументы
        PackRLEKt.packRLE(pack, input, out);
    }
}

На этом в принципе всё. На тестах особо останавливаться не буду. Сделаны с помощью библиотеки junit. Единственное, что возможно стоит некоторого внимания, так это функция assertFileContent в файле PackRLETest.kt:

private fun assertFileContent(expectedFile: String, actualFile: String): Boolean {
        val expected = File(expectedFile).readLines()
        val actual = File(actualFile).readLines()
        for (i in actual.indices) {
            if (expected[i] != actual[i]) return false
        }
        return expected.size == actual.size
    }

Я не считаю себя супер крутым кодером, поэтому с радостью прочту все ваши комментарии по поводу улучшения и оптимизации кода.

Готовый проект тут.

Источники


  1. Wikipedia
  2. Args4j