Простой и компактный код для сжатия ДНК-подобных строк

Мое приложение - это тест с несколькими вариантами выбора, где для каждого вопроса ответ получается в виде строки из 4 букв «например, GTAC или ATGC или CATG и т. Д. Всегда есть только 24 вопроса. так что конечный результат что-то вродеПростой и компактный код для сжатия ДНК-подобных строк

GTAC CATG TACG GACT GTAC CATG TACG GACT GTAC CATG TACG GACT GTAC CATG TACG GACT GTAC CATG TACG GACT GTAC CATG TACG GACT

так есть 4! = 24 возможности для каждого ответа , Я мог бы сопоставить каждую возможность с буквой A-X, и это сократило бы ее до строки размером 24 буквы, но я считаю, что должен быть простой способ довести ее до 6 символов.

Результаты будут отправлены через HTTP-запрос, поэтому мне нужно его сжать в виде буквенно-цифровой строки, например base64, но не обязательно base64.

Данные - это просто строка, как указано выше, или я могу поместить ее в любом формате в соответствии с вашим циклом. Я ищу что-то вроде 10-строчного алгоритма сжатия. Я сжимаю в javascript и распаковываю в php.

источник

2013-12-11 AwokeKnowing

Base64 раздувает ваши данные. Нет причин для этого, когда ваши данные находятся в домене [A, T, G, C,] – mccainz

Wow! Оверкилл много? – AbraCadaver

@mccainz да, я это понимаю. Я имею в виду, что мы можем сжать его в буквенно-цифровую строку, а base64 - хорошая стартовая точка для 64 юридических символов – AwokeKnowing

Минимум вы можете получить его до 24 lg (24) ~ = 111 бит или 14 байтов. Чтобы затем закодировать это до 84 допустимых символов, вам нужно будет расширить его до 18 символов. 24 lg (24)/lg (84) = 17,2. Предполагая, что все 24 варианта возможны для каждого из 24 ответов, тогда нет способа получить его менее 18 символов. Конечно, не шесть.

Ваша схема кодирования в 24 символа кажется мне прекрасной. Прибыль 18 из 24 не кажется дополнительной сложностью. Однако, если вы ...

Разделить ответы на восемь групп по три. Для каждой группы из трех, считайте это трехзначным базовым номером 24, который будет иметь диапазон 0..13823. Это будет соответствовать 14 бит. Восемь из них - это 14 байт или 112 бит.

Теперь вытащите 19 бит за раз. Будет шесть наборов, причем последний набор имеет только 17 бит. Для каждого набора из 19 кодируйте его как трехзначный базовый номер 81, испускающий три символа, защищенных URL. 81 > 2 . Выберите из 81 символа из 84 URL-безопасных символов, которые вам больше всего нравятся.

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

источник

2013-12-12 03:20:10

группы из 3 и 14 бит - это именно то, что я придумал. И я отправил аналогичную вещь в кодовый гольф, и результат был 18 символов, хотя он просто использовал 64 символа. Я, вероятно, просто придерживаюсь 24 букв, которые будут работать лучше для кластеризации машинного обучения. – AwokeKnowing

Это не возможно только с 64 символами. –

проверить это. это код гольфа, где парень выходит с 18 символами, используя 64: http://codegolf.stackexchange.com/questions/15831/compressing-a-dna-like-string – AwokeKnowing

Простой и компактный код для сжатия ДНК-подобных строк

ответ

Смежные вопросы