Сжать массив с дубликатами

Question

Есть класс Дерево, которое содержит массив геномов. При его росте массив растёт очень быстро. Как его сжать? Подскажите алгоритм действий.

Код дерева:

import java.util.List;
import java.util.ArrayList;

public class Tree {

    private Gene[] genes;
    
    public Tree(Gene[] genes) {
        this.genes = genes;
    }
    
    public Gene[] getGen() {
        return genes;
    }
    
    public void development() {
        List<Gene> newGens = new ArrayList<>();
        for(Gene g : genes) {
            Gene[] arrG = g.newInstructions();
            if(arrG == null) {
                continue;
            }
            for(Gene j : arrG) {
                newGens.add(j);
            }
        }
        int l = newGens.size();
        genes = new Gene[l];
        for(int i = 0; i < l; i++) {
            genes[i] = newGens.get(i);
        }
    }
    
}

Код базового генома:

import java.awt.Color;

public abstract class Gene {
    
    public final String NAME;
    public final Color COLOR;
    public final FormGene FORM;
    public final Direction DIRECTION;
    public final int STEP;
    
    protected Gene(String name, Color color, FormGene form, Direction direction, int step) {
        NAME = name;
        COLOR = color;
        FORM = form;
        DIRECTION = direction;
        STEP = step;
    }
    
    public abstract Gene[] newInstructions();

}

У меня реализованы потомки генома, которые выдают такие результаты:

A
AB
ABABC
ABABCABABCAB  //Повторы есть ABABC ABABC AB -> 2*ABABC 1*AB
ABABCABABCABABABCABABCABABABC //Повторы ABABC ABABC AB ABABC ABABC AB ABABC -> 2*ABABC 1*AB 2*ABABC 1*AB

Сжать нужно массив genes в Tree.

Answer 1

Если речь об эффективной упаковке данных, то вообще не торопитесь с повторами, не важно, массив это, строка, или что-то ещё.

Вначале хорошо бы проанализировать "ёмкость" данных и не пытаться ужать бесполезно потраченное место.

У вас видно, что используется всего 3 символа. Для генов, наверное их будет больше (основных нуклеотидов же вроде 5 и их комбинаций штук 6 всего).

Но в любом случае 3-4 символа можно пронумеровать и поместить в 2 бита (для 5-8 символов понадобится 3 бита):

A - 00
B - 01
С - 10
D - 11

В байт поместится целых четыре таких числа, например BBCA=01011000, оно же 58 в шестнадцатеричном представлении, оно же десятичное 88, и даже представимо в текстовом виде 'X' (будут и непечатаемые, так что текст не стоит рассматривать).

В случае трёхбитного кодирования для упаковки будет удобно использовать три байта - туда уложится 8 штук.

Если хочется, можете считать это словарём, состоящим из 4-буквенных комбинаций.

Так вот, ваша строка ABABCABABCABABABCABABCABABABC без всяких словарей станет таким массивом:

ABAB 0x11
CABA 0x84
BCAB 0x61
ABAB 0x11
CABA 0x84
BCAB 0x61
ABAB 0x11
CAAA 0x80 (добиваем до 4 букв, при известной общей длине это проблемой не будет)

То есть [0x11,0x84,0x61,0x11,0x84,0x61,0x11,0x80]

Как видно, результирующие данные займут в 4 раза меньше места, причем закодировать можно 4, а не 3 символа.

Если же их всегда будет только 3 - можно применить троичную систему счисления и запаковать максимально компактно. Даже в байт помещается уже 5 букв, а не 4. А в четырехбайтовую переменную влезет уже 21 буква.

При кодировании 5 нуклеотидов оптимально использовать пятеричную систему счисления и, например, в 8 байтов уложится 27 букв.

Об этом в более математических терминах изложил Stanislav Volodarskiy в топике, указанном maestro в комментариях.

А уже следующим этапом можно задуматься над формированием словаря. Только и там надо помнить, что если заменять, например 3 байта на 3-байтовое положение в словаре - хрен редьки не слаще. Словарь должен состоять из достаточно длинных слов и их должно быть не сильно много. Другими словами, ссылки на словарь должны быть несоизмеримо короче самих слов, иначе нет смысла. Но это уже лучше почитать про алгоритмы сжатия.

И простите, что это вообще ни разу не ответ на поставленный в топике вопрос ))

БЛОГ НА HUSL

Сжать массив с дубликатами

Ответы (1 шт):