2

我目前正在为 Windows Mobile 编写一个应用程序,它需要能够从一维条码(配置设置)中获取键值对。需要扫描的条码越少越好。样本输入:

------------------------------
| Key | Value                |    
------------------------------
| 12  | Söme UTF-8 Strîng    |
|  9  | & another string     |
------------------------------

我想到了以下算法:

1.连接键值对并使用Base64对值进行编码

所以我们会得到类似的东西12=U8O2bWUgVVRGLTggU3Ryw65uZw==&9=JiBhbm90aGVyIHN0cmluZw==

2.使用霍夫曼编码压缩数据

为此,我将使用固定的 Huffman 树,并提供以下信息来帮助我压缩数据:

-------------------------------------------
| Enties                       | Priority |    
-------------------------------------------
| =, &                         | High     |
| 0-9                          | Medium   |
| 5-bit Base64 Words (w/o 0-9) | Low      |
-------------------------------------------

3. 从编码数据生成 Code 128B 条码

将 Base96 编码应用于 Huffman 算法生成的比特流,以获得可在 Code 128B 条码中使用的 ASCII 字符。根据需要将生成的字符串拆分为多个条形码。

编写这些步骤对我来说不是问题,但我想对算法的效率和设计有一些反馈。

问题

  • 我是否在某处失去了更好压缩/更短字符串的潜力?
  • 有没有更好的方法来压缩随机 UTF8 编码的数据?
  • 我应该将动态霍夫曼表嵌入到编码数据中吗?
  • 如何考虑 Code 128B 的压缩( a0需要的空间比 a 少&)?
4

3 回答 3

2

一种简单的方法是定义直接映射到 code128 的所有 64 个字符。这将留下 30-40 个可用代码 128 个插槽。在剩余的插槽中定义一些双字符。== =& 0= 1= 2= 3= 4= 5= 6= 7= 8= 9= &0 &1 &2 &2 &5 &5 &6 &7 &8 &9 (重复最后一个字符)= =(双下一个字符) &(双下一个特点)

于 2013-03-09T20:16:27.653 回答
1

经过一番折腾,我们最终选择了这种方式:

1. 将设置编码成字节流

字段值被序列化为字节流,每个字段都有一个标头。标头占用一个字节并包含字段的 ID 和一些有助于减少要传输的数据量的标志。根据字段的类型(例如字符串、数字或 IP 地址),该值被有效地编码到字节流中。例如,IP 地址用 4 个字节编码,而布尔标志直接编码到字段头中。这样,如果需要,我们甚至可以将 SSL 证书编码到流中。由于典型的条形码格式无法传输任意字节值,我们需要在下一步中对字节流进行编码。

2.转换成条码格式

生成的字节数组现在被视为一个大整数,并使用基本编码和字符集转换为目标条形码格式(请参阅此问题)。这样,我们有效地使用条形码格式来传输我们的数据(与 Base64 或其他编码相反)。从得到的字符串中,我们可以将单个条形码大块并添加一些额外的标题信息(例如,必须扫描多少个条形码?数据是否加密?...)。

当在移动设备上扫描条形码时,可以恢复编码字符串并将其转换为相同的大整数。然后可以将此整数视为字节数组,当字段序列化格式已知时可以对其进行解析。

这种方法被证明是非常有效和快速的(我们对 CF 上的BigInteger 实现有些担忧)。

于 2013-09-13T08:11:05.473 回答
0

虽然某些条形码格式具有一组固定的字符,它们可以表示并使用相同数量的空间来保存每个字符,但其他条形码格式要么使用多个字符集,要么使用可变数量的空间来保存每个字符。例如,“经典”代码 39 定义了 43 个字符,每个字符由 43 个符号之一表示,并且根本不能表示任何其他字符,但是还有另一个代码 39 变体,它使用一个符号表示 39 个常见字符,其他字符使用两个字符序列。例如,假设有人想将一堆二进制数据存储在 code-39 条形码中。如果将数据转换为 base-64 格式,则与三个八位字节的原始数据相关的四个字符可能平均需要大约 5 个字符。存储 69 个符号 [base64 中使用的 64 个字符中约有 27 个需要两个符号存储在 code39 中]。如果一个人选择了 32 个字符,每个字符可以用一个符号表示,则可以使用五个八位字节存储 24(或 25)位,每个八位字节存储五个位[一致的每个八位字节有 1.67 个符号,而平均值为 1.89,最坏情况为 2.67 ]。如果使用“经典”代码 39(每个使用一个符号可以表示 43 个字符),甚至可以在六个符号中存储四个八位字节[平均每个八位字节 1.5 个符号]。

针对不同的字符集“优化”了不同的条码格式;有些像 Code 128 有多个字符集,并且可以有效地与使用一个字符集的全部范围的数据一起使用,同时避免使用它之外的字符。我不知道有什么特别推荐的方法来重新格式化数据以优化特定符号系统字符集的使用,但是检查符号系统使用的编码和您的特定要求应该可以帮助您找出最适合您的编码应用。

于 2013-12-05T18:46:03.613 回答