Анализ строки перед преобразованием Барроуза-Уилера?

Question

Если мы рассмотрим это aaabccba как наша входная строка, baaacacb будет выходной строкой после применения преобразования Берроуз-Уилера на входе. наблюдая за выходом, вы увидите, что два слипались c отделены. Понятно, что входная строка даст лучшее сжатие, чем выходная.

Как решить, применять ли преобразование Барроуза-Уилера к входной строке? Можем ли мы сделать какой-то быстрый анализ, чтобы принять решение?

Answer 1

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

Answer 2

Самым простым решением было бы фактически сжать каждую строку и посмотреть, что приведет к наименьшему сжатию.

Если вы не хотите этого делать, вы можете посчитать длину каждой группы:

aaabccba -> aaa b cc b a

    aaa has length 3
    b has length 1
    cc has length 2
    b has length 1
    a has length 1

    there where 3 groups of length 1
    there where 1 group of length 2
    there where 1 group of length 3
                ^

    -> [3, 1, 1]

baaacacb -> b aaa c a c b

    b has length 1
    aaa has length 3
    c has length 1
    a has length 1
    c has length 1
    b has length 1

    there where 5 groups of length 1
    there where 0 groups of length 2
    there where 1 group of length 3
                ^

    -> [5, 0, 1]

• Сравните списки лексикографически: 3 < 5 так [3, 1, 1] < [5, 0, 1] - Выберите самый маленький.

• В качестве альтернативы вы можете изменить списки: [1, 1, 3] > [1, 0, 5] - Выберите самый большой.

• Другим способом сравнить их будет общий счет: 3+1+1=5 < 5+0+1=6, - Выберите один с меньшей суммой.