Сжатие / кодирование строк с ограниченными символами в Python

Question

Я пытался найти способ кодирования строк ограниченных символов для сжатия данных, а также найти уникальные «идентификаторы» для каждой строки.

У меня есть несколько миллионов строк, каждая из которых содержит около280 ~ 300 символов каждая, но не более четырех букв (A, T, C и G). Я задавался вопросом, не будет ли более простого способа их кодировать, используя меньше памяти, учитывая, что они должны быть легко закодированы, используя «базовую четверку», но не знаю, как это проще сделать. Я рассмотрел использование циклов for в Python, где я перебрал бы каждую строку, а затем нашел правильное значение для каждой буквы, используя словарь, и умножил его на значение из четырех оснований. Пример:

base_dict = {
    'A' : 0,
    'T' : 1,
    'C' : 2,
    'G' : 3
} # These are the four bases of DNA, each assigned a different numeric value

strings_list = [ 
'ATCG', 
'TGGGGAATATTGCACAATGGGGGAAACCCTGATGCAGCGACGCCGCGTGAGCGAAGAAGTATTTCGGTATGTAAAGCTCTATCAGCAGGGAAGAAAATGACGGTACCTGACTAAGAAGCCCCGGCTAACTACGTGCCAGCAGCCGCGGTAATACGTAGGGGGCAAGCGTTATCCGGATTTACTGGGTGTAAAGGGAGCGTAGACGGGACAGCAAGTCTGATATGAAAGGCGGGGGCTCAACCCCCGGACTGCATTGGAAACTGCTGGCCTGGAGTACCGGAGG',
'GGGGGGGGGG' 
] # A few sample DNA sequences

for string in strings_list:
    encoded_number = 0
    for i in range(len(string)):
        letter = string[i]
        encoded_number += (4**i) * base_dict[letter]
    print('String {} = {}'.format(string, encoded_number))

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

binary = '{0:b}'.format(encoded_number)

Но, хотя он вернул мне двоичное значение, он сделал бы это в виде строки. Попытка преобразовать его в двоичном всегда дает ошибку из-за огромного размера целого числа (при использовании фактических символов струнные 280 +), так как длинная строка выше приведет к огромному числу (230124923583823837719192000765784020788478094239354720336304458517780079994251890530919145486338353514167796587078005476564902583371606379793061574009099280577109729494013):

1010 *

Я бы хотел знать, является ли это наиболее эффективным способом кодирования строк ограниченных символов , например, или , если есть какой-то лучший способ , а также, если есть любые другие способы, которые я мог бы использовать, чтобы сжать эти данные еще больше , в то же время все еще имея возможность обратить окончательное число / двоичный файл обратно в мою строку. Кроме того, есть ли вообще способ преобразовать его в двоичный формат вместо целого числа или строки? Помогает ли это в сохранении данных?

Кроме того, Каков был бы наиболее краткий способ сокращения целого / двоичного значения для читаемого человеком значения (до новой более короткой строки) ? Использование целых чисел или двоичных файлов, кажется, сохраняет данные, и я смогу хранить эти строки, используя меньше памяти (и также передавать данные быстрее), но если я хочу создать краткие строки, читаемые пользователем, что будет лучшим вариантом? Есть ли способ, которым я мог бы закодировать обратно в строку, но используя всю таблицу ASCII, чтобы использовать намного меньше символов?

Было бы очень полезно иметь возможность уменьшить мои 300-символьные строки на более маленькие, 86-символьные строки (учитывая, что в таблице ASCII доступно 128 символов и 4 ^ 300 ~ = 128 ^ 86).

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

TL; DR, суммируя несколько вопросов, которые явозникли проблемы с:

1. Каков наиболее эффективный способ кодирования строк ограниченных символов? (В приведенном выше примере есть пример, это лучший способ?)
2. Есть ли другие способы сжатия строк, которые можно использовать наряду с кодированием ограниченных символов, для дальнейшего сжатия данных?
3. Можно ли преобразовать большие целые числа (4 ^ 300) в двоичные, не вызывая переполнения? Как?
4. Какой наиболее эффективный способ преобразования двоичных значений, чисел или строк ограниченных символов (в этой ситуации это в основном то же самое, что я пытаюсь преобразовать одну в другую) в небольшие сжатые строки (пользовательскиеудобочитаемо, поэтому чем меньше, тем лучше)

Answer 1

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

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

Другая версия этого - разбить строку на 8-буквенные куски, превратив каждый из них в 32-разрядное целое число;затем выписать последовательность целых чисел (в двоичном виде). ​​

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

NB ваше преобразование потеряет лидирующие нули, такие как "AAAAGCTGA";это будет воссоздано как "GCTGA". Вам нужно будет указать ожидаемую длину строки.

---

Чтобы выполнить простой метод chunk-convert, обратитесь к предоставленной мной ссылке.

Для методов сжатия изучите сжатие (котороемы предполагаем, что вы сделали до публикации здесь, в соответствии с правилами размещения). В Linux используйте сжатие файлов, поставляемое с ОС (вероятно, gzip).

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