动态规划示例:寻找 QR 码的***编码

介绍

最近,竞争性编程在现实生活中帮助了我。

作为我爱好的一部分,我正在创建一个 Python 包来生成 rMQR 码,它们是矩形 QR 码。其中”对数据进行编码,使位串最短我对这个过程使用了动态编程。作为一个在大学做竞技编程的人,我很高兴专业的竞赛有用,所以写这篇文章作为例子分享。阐述了动态规划的DP表的定义、转换的方法以及解的还原,并用图和实现。它没有解释动态规划本身。整个实现是你可以在

本文中出现的 rMQR 码规范的描述是 ISO 标准。它基于。寻找***编码的算法本身不是规范的一部分,并且是原创的。

*二维码是 DENSO WAVE INCORPORATED 的注册商标。

rMQR码的知识

首先,我将简要解释一下本文所需要的rMQR码的知识。

版本

QR 码的每个尺寸都有一个名称,称为版本。特别是对于 rMQR 码,版本会根据垂直单元格和水平单元格的数量而变化。此版本写为“R$C_v$x$C_H$”,其中 $C_v$ 是垂直单元格的数量,$C_H$ 是水平单元格的数量。例如,具有 7 个垂直单元格和 99 个水平单元格的版本将是“R7x99”。

纠错级别

您可以在编码数据时选择纠错级别。可以使用两种类型的 rMQR 码:15% 可校正 M 和 30% 可校正 H。您也可以在版本末尾添加纠错级别并写入。例如,写“R7x99-M”。对于同一版本,纠错级别越高,可存储的字符数越少。

编码方式

rMQR码编码数据时可以指定编码方式。可以使用数字、字母数字、字节、汉字。通过适当地指定模式,可以缩短编码位串的长度。

模式名称 可以使用的字符类型 编码效率 数字 0-9 每 3 位 10 位 字母数字 0-9 A-Z \s $ % * + - . / : 每 2 个字符 11 位 字节 任何字符 每个字符 8 位 汉子 Shift-JIS 中的 0x8140 ~ 0x9FFC 或 0xE040 ~ 0xEBBF 每个字符 13 位

数字模式是一种可以有效编码数字的模式。一个数字的每 3 位数字可以用 10 位表示。如果最后一组小于 3 位,则 1 位用 4 位表示,2 位用 7 位表示。

字母数字模式是一种可以高效编码数字、大写字母和 9 个符号的模式。每两个字符可以用 11 位表示。如果最后一组少于 2 个字符,则 6 位表示每个字符。

字节模式是一种按原样存储字节字符串的模式。因此可以对任何字符进行编码。

汉字模式是一种可以有效编码汉字的模式,汉字是 Shift-JIS 中的双字节字符。每个字符可以用 13 位表示。

部分

编码可以通过分成多个段来完成。可以为每个段切换模式。段由三部分组成:模式指示符、字符计数指示符和数据。例如,下图显示了“123Abc”被分成两段并编码的情况。第 1 段以数字模式编码“123”。第 2 段以字节模式对“Abc”进行编码。组合的两个段的编码比特流的总长度为 47。

寻找***编码的问题

在 rMQR 码中,可以将数据分成多个段并进行编码。此时,”编码后如何分段以获得最短的比特流”。可编码的最大数据量为 361 个字符是。

您可能认为根据字符类型的切换,简单地将段从一端划分到另一端会更好,但这种方法不一定是最短的。这是因为需要为段的开头提供称为模式指示符和字符计数指示符的元数据。

让我们考虑使用具体示例“123Abc”。下图总结了每个字符可以使用的编码模式。 “123”支持Numeric、Alphanumeric和Byte,“A”支持Alphanumeric和Byte,“bc”只支持Byte。

由于需要附加元数据,使用相同的编码模式对相邻段进行编码是低效的。因此,有四种类型的分类作为候选解:“123Abc”、“123|Abc”、“123A|bc”和“123|A|bc”。下图显示了“123|Abc”和“123A|bc”的实际位串,请比较一下。在这种情况下,***的分割是“123|Abc”。

解决方案

将其视为“一次编码一个字符”。从广义上讲,有两种模式,其中所讨论字符的编码模式与前一个字符的编码模式相同或不同。如果模式相同,长度只会增加一个字符。当模式改变时,一个字符的长度和元数据会增加。如果我们将成本视为增加一个字符的位数,我们可以将其视为与背包问题相同的方式。

DP计算 DP表定义

定义 DP 表如下:

dp[n][mode][unfilled_length] := 先頭からn文字を取り出し、最後の文字のエンコードモードがmodeモードであり、
                                最後のグループのビット数がunfilled_lengthのとき、最小となるエンコード後のビット列の文字数

mode 是一个从 0 到 3 的数字,对应于编码模式。这里,0 => 数字,1 => 字母数字,2 => 字节,3 => 汉字。 unfilled_length 是最后一组中的字符数。例如,数字模式以 3 位数字分隔组,因此unfilled_length 第 5 个字符变为 2。这是计算一个字符增加时增加的位数所必需的。

初始化

为了便于实现,我们将 DP 表的初始状态定义如下。通过只将元数据的长度放在n=0中,实现会更容易,因为后续实现的情况会更少。

dp[0][mode][0] = modeモードにおけるメタデータの長さ

实现看起来像这样。

MAX_CHARACTER = 360
INF = 100000
dp = [[[INF for n in range(3)] for mode in range(4)] for length in range(MAX_CHARACTER + 1)]
parents = [[[-1 for n in range(3)] for mode in range(4)] for length in range(MAX_CHARACTER + 1)]

for mode in range(len(encoders)):
    # エンコードモードに対応するクラス
    encoder_class = encoders[mode]
    # メタデータのうち文字数インジケーターはバージョンによって長さが変わる
    character_count_indicator_length = qr_version["character_count_indicator_length"][encoder_class]
    dp[0][mode][0] = encoder_class.length("", character_count_indicator_length)
    parents[0][mode][0] = (0, 0, 0)
过渡

从n、mode、length 过渡到所有模式。

例如,下图为“123Abc”的数据计算DP表的结果。由于n=6的最小值是最优的位串长度,所以(n, mode, unfilled_length) = (6, 2, 0)的情况下的47是最小的位串长度。。

下图显示了 DP 表中的转换示例。绿色箭头显示在数字模式下最多编码 3 个字符时的转换。同样,蓝色对应字母数字模式的编码,红色对应字节模式的编码。在 Numeric 模式下,unfilled_length 从 0→1→2→0... 变化,因为 3 个字符被视为一组。在字母数字模式下,2 个字符被视为 1 组,因此 unfilled_length 从 0→1→0... 变化。

for n in range(0, len(data)):
    for mode in range(4):
        for unfilled_length in range(3):
            if dp[n][mode][unfilled_length] == INF:
                continue

            for new_mode in range(4):
                if not encoders[new_mode].is_valid_characters(data[n]):
                    continue

				# エンコードモードに対応するクラス
                encoder_class = encoders[new_mode]
                # メタデータのうち文字数インジケーターはバージョンによって長さが変わる
                character_count_indicator_length = qr_version["character_count_indicator_length"][encoder_class]
                
                if new_mode == mode:
                    # モードが変わらない場合
                    if encoder_class == encoder.NumericEncoder:
                        new_length = (unfilled_length + 1) % 3
                        cost = 4 if unfilled_length == 0 else 3
                    elif encoder_class == encoder.AlphanumericEncoder:
                        new_length = (unfilled_length + 1) % 2
                        cost = 6 if unfilled_length == 0 else 5
                    elif encoder_class == encoder.ByteEncoder:
                        new_length = 0
                        cost = 8
                    elif encoder_class == encoder.KanjiEncoder:
                        new_length = 0
                        cost = 13
                else:
                    # モードが変わる場合
                    if encoder_class in [encoder.NumericEncoder, encoder.AlphanumericEncoder]:
                        new_length = 1
                    elif encoder_class in [encoder.ByteEncoder, encoder.KanjiEncoder]:
                        new_length = 0
                    cost = encoders[new_mode].length(data[n], character_count_indicator_length)

                if dp[n][mode][unfilled_length] + cost < dp[n + 1][new_mode][new_length]:
                    dp[n + 1][new_mode][new_length] = dp[n][mode][unfilled_length] + cost
                    parents[n + 1][new_mode][new_length] = (n, mode, unfilled_length)
溶液回收

然后从派生的 DP 表中恢复解决方案。使用parents 表来恢复解决方案。这是在计算 DP 表时记录最小值更新时的转换前状态到转换后状态的表。就代码而言,这是部分:

if self.dp[n][mode][unfilled_length] + cost < self.dp[n + 1][new_mode][new_length]:
    self.dp[n + 1][new_mode][new_length] = self.dp[n][mode][unfilled_length] + cost
    self.parents[n + 1][new_mode][new_length] = (n, mode, unfilled_length) # 遷移前の状態を記録しておく

使用此表,可以通过从最优解的状态向后跟踪父表来恢复解。在“123Abc”的例子中,得到如下所示的轨迹。

实现看起来像这样。

path = []
index = best_index
while index[0] != 0:
    path.append(index)
    index = parents[index[0]][index[1]][index[2]]
path.reverse()
合并段

最后,在得到的解中,将具有相同编码方式的相邻区域作为一个片段。具有相同模式的段显然是不利的,因为更改段会提供元数据。

segments = []
current_segment_data = ""
current_mode = -1
for p in path:
    if current_mode == -1:
        current_mode = p[1]
        current_segment_data += data[p[0] - 1]
    elif current_mode == p[1]:
        current_segment_data += data[p[0] - 1]
    else:
        segments.append({"data": current_segment_data, "encoder_class": encoders[current_mode]})
        current_segment_data = data[p[0] - 1]
        current_mode = p[1]
if current_mode != -1:
    segments.append({"data": current_segment_data, "encoder_class": encoders[current_mode]})
综上所述

我们介绍了如何使用动态规划找到 rMQR 码的***编码。能够将我的大学竞争性编程经验应用于现实世界的问题真是太好了。当我开始竞争性编程时,我有一个问题,“即使使用动态编程找到了最小成本,我如何才能找到具体的解决方案?”我们希望此示例将帮助您了解找到特定解决方案所需的一系列步骤。

这是创建作为主题的 rMQR 代码的包的存储库。如果你喜欢它,如果你能给我一颗星,我将不胜感激!

请注意,此算法假定 rMQR 码中可编码的最大字符数为 361 个字符。也许有更有效的算法。如果您想出这样的算法,请在评论中告诉我们!

R17x139 可存储的字符数,数字模式,纠错级别 M

原创声明:本文系作者授权爱码网发表,未经许可,不得转载;

原文地址:https://www.likecs.com/show-308624591.html

32人参与, 0条评论 登录后显示评论回复

你需要登录后才能评论 登录/ 注册