c++ - 我们如何有效地压缩 DNA 串

Question

DNA 字符串可以是任意长度，包含 5 个字母(A、T、G、C、N)的任意组合。
压缩包含 5 个字母(A、T、G、C、N)的 DNA 字母串的有效方法是什么？不是考虑每个字母表 3 位，我们可以使用更少的位数有效地压缩和检索吗？任何人都可以建议一个有效压缩和检索的伪代码吗？

Answer 1

如果您愿意 (a) 为每个字符设置不同的位大小，并且 (b) 您总是从头开始阅读，而不是从中间开始阅读，则可以。然后，你可以有这样的代码:

• A - 00
• T - 01
• G - 10
• C - 110
• N - 111

从左到右阅读，您只能以一种方式将比特流拆分为字符。您一次读取 2 位，如果它们是“11”，您需要再读取一位才能知道它是什么字符。

This is based on Huffman Coding Algorithm

注意:
我对 DNA 了解不多，但如果字符的概率不相等(即每个 20%)。您应该将最短的代码分配给概率较高的代码。