Сжатие последовательности?

Question

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

a, a, a, b> a, b

a, b, a, a, c -> a, b, a, a, c (его нельзя сжать в a, b, a, c, потому что таким образоммы теряем, а)

Есть ли какой-нибудь алгоритм, чтобы сделать такую ​​вещь?как называется эта проблема?это сжатие?или что-нибудь еще?Буду очень признателен за любую помощь Спасибо заранее

Answer 1

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

например. (сжатая форма для "данного примера" : -) )

Ниже приведена простая форма, называемая длиной кодирования, короткое RLE:

a,a,a,b,c -> 3a,1b,1c

Как видите, все последующие одинаковые символы сжаты в один.

Вы также можете искать последующие паттерны, которые намного сложнее:

a,b,a,b,a,c --> 2(a,b),1(a),1(c)

Существует множество литературы и веб-источников об алгоритмах сжатия, вы должны использовать их для более глубокого обзора.

Answer 2

Другой хороший алгоритм - Лемпель – Зив – Уэлч

Я нахожу изумительным эту простую функцию Javascript LZW от магов 140 байтов javascript :

function (
    a // String to compress and placeholder for 'wc'.
){

    for (
        var b = a + "Ā", // Append first "illegal" character (charCode === 256).
            c = [], // dictionary
            d = 0, // dictionary size
            e = d, // iterator
            f = c, // w
            g = c, // result
            h; // c

        h = b.charAt(e++);
    )

        c[h] = h.charCodeAt(), // Fill in the dictionary ...
        f = 1 + c[a = f + h] ? a : (g[d++] = c[f], c[a] = d + 255, h); // ... and use it to compress data.

    return g // Array of compressed data.

}

Answer 3

Да, сжатие. Простым алгоритмом будет кодирование по длине прогона. Там также теория информации, которая является основой для алгоритмов сжатия.

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

Итак, если вы кодируете двоичный файл, где последовательность 0101 очень обычная (около 25% входных данных), тогда простое сжатие будет:

0101 = 0
anything else = 1[original 4 bits]

Итак, ввод: 0101 1100 0101 0101 1010 0101 1111 0101
Будет сжат до: 0 11100 0 0 11010 0 11111 0

То есть сжатие 32 бита -> 20 бит.

Важный урок: выбор алгоритма сжатия полностью зависит от ввода. Неправильный алгоритм, и вы, вероятно, увеличите длину данных.

Answer 4

RLE

Answer 5

Мы можем использовать алгоритм сжатия LZW для эффективного и быстрого сжатия текстовых файлов, используя хеш-таблицы.

Answer 6

Если вам не нужно самостоятельно кодировать какое-либо решение, вы можете использовать библиотеку сжатия ZIP для используемого вами языка программирования.

И да, это сжатие данных.