javascript - 用于压缩类 DNA 字符串的简单紧凑代码

Question

我的应用程序是多项选择测试，其中每个问题的响应结果都是一个 4 字母字符串“eg”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 中解压缩。

Answer 1

您可以将其最小化为 24 lg(24) ~= 111 位或 14 字节。然后要将其编码为 84 个 URL 可接受的字符，您必须将其扩展到至少 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¹⁹。从 84 个 URL 安全字符中选择您最喜欢的 81 个字符。

现在您有 18 个字符代表 24 个答案。除非您没有告诉我们的答案有其他一些限制，否则您不能做得更好。