二維碼位流長度最小化算法

袁泰凌，徐昆

1. 清華大學(xué)計算機科學(xué)與技術(shù)系，北京 100084； 2. 普適計算教育部重點實驗室，北京 100084

0 引 言

快速響應(yīng)矩陣碼(quick response code，QR code)簡稱二維碼，是一種正方形符號，廣泛應(yīng)用于商品識別、廣告、在線支付和疫情防控等場景。二維碼符號的最小單元是模塊，即深色或淺色的小正方形。二維碼的版本決定了每條邊上的模塊數(shù)量，如圖1所示，二維碼版本越大，每條邊上的模塊數(shù)量越多。

圖1 不同版本的二維碼示意圖Fig.1 QR code examples with different versions((a) version 1; (b) version 6; (c) version 11)

二維碼使用了糾錯碼，因此其對模塊錯誤有一定糾錯能力。減小二維碼的版本能夠在不減小模塊大小的前提下節(jié)省面積，或者在不改變面積的前提下增大模塊大小以提高模塊正確識別的概率。

為了提高二維碼的數(shù)據(jù)容量，現(xiàn)有研究工作主要采用了不兼容標(biāo)準(zhǔn)二維碼的編碼格式。例如使用彩色模塊、修改模塊排布、修改位流編碼步驟等。這些方案都需要使用專門的掃碼器才能讀取?？紤]到掃碼用戶一般有通用的標(biāo)準(zhǔn)二維碼掃碼器，而不一定有專門的掃碼器，因此這些二維碼的普適性較差。如何在兼容二維碼標(biāo)準(zhǔn)的前提下最大化數(shù)據(jù)容量是一個待解決的問題。

與上述研究工作不同的是，本文在符合二維碼標(biāo)準(zhǔn)的前提下最小化位流長度，從而最大化數(shù)據(jù)容量。本文算法輸出的位流與標(biāo)準(zhǔn)算法(國家質(zhì)量技術(shù)監(jiān)督局，2000)、開源編碼器ZXing(https://code. google.com/p/zxing)、商業(yè)編碼器“草料二維碼生成器”(http://cli.im/)相比，長度相同或更短。一方面，信源編碼問題轉(zhuǎn)換為動態(tài)規(guī)劃問題，提出了計算最短位流的算法；另一方面，針對常見的統(tǒng)一資源定位符(uniform resource locators，URL)類型數(shù)據(jù)，進一步減小位流長度，提出了統(tǒng)一資源定位符的最短位流計算算法。

1 相關(guān)工作

關(guān)于二維碼數(shù)據(jù)容量的研究主要分為以下幾類：

1)通過增加模塊的顏色種類提高數(shù)據(jù)容量。包括使用RGB 3個色彩通道表示3倍數(shù)據(jù)(Blasinski等，2013；Meruga等，2015)、使用3種熒光材料表示3倍數(shù)據(jù)(Abdolahi等，2019)、使用4種特定顏色表示log24=2倍數(shù)據(jù)(Melgar等，2012)、使用至多214種顏色表示至多14倍信息(Galiyawala和Pandya，2014)。Yang等人(2018)指出顏色混疊效應(yīng)會導(dǎo)致彩色二維碼較難解碼，并基于支持向量機(support vector machine，SVM)提出一種針對彩色二維碼的解碼算法。賈丹等人(2017)基于k-means算法識別彩色二維碼。由于彩色二維碼是自定義的編碼格式，因此標(biāo)準(zhǔn)二維碼解碼器無法解碼彩色二維碼，而需要使用定制的解碼器。

2)在二維碼中隱藏私有信息。Tkachenko等人(2015，2016)提出的雙級別二維碼(two-level QR codes)在標(biāo)準(zhǔn)二維碼的黑色模塊上添加紋理，其中標(biāo)準(zhǔn)二維碼編碼主要信息，紋理編碼私有信息；標(biāo)準(zhǔn)二維碼解碼器可以讀取主要信息，定制的解碼器可以讀取私有信息。Barron等人(2020)提出的雙重調(diào)制二維碼(dual modulated QR codes)將標(biāo)準(zhǔn)二維碼的黑色模塊由正方形替換成橢圓形，用橢圓的方向編碼隱私信息。標(biāo)準(zhǔn)二維碼解碼器可以讀取公開信息；當(dāng)相機與二維碼距離較近時，定制的解碼器可以從模塊方向中讀取隱私信息。這兩種修改模塊紋理或模塊形狀的方法損害了每個模塊的識別率，使得二維碼的主要信息更難識別。

3)壓縮輸入數(shù)據(jù)。鄒敏等人(2015)使用Huffman算法壓縮輸入數(shù)據(jù)；Abas等人(2017)使用 Gzip、Zip等多種壓縮算法壓縮輸入數(shù)據(jù)，并將壓縮后的二進制數(shù)據(jù)用base64格式編碼成字符串作為二維碼編碼器的輸入。對于這類編碼算法，標(biāo)準(zhǔn)二維碼解碼器會讀取到壓縮后的數(shù)據(jù)，而不知道如何翻譯這些數(shù)據(jù)。Victor(2012)提出的二維碼和陳元枝等人(2015)提出的二維碼均同時使用了彩色模塊和壓縮數(shù)據(jù)兩項技術(shù)共同提高數(shù)據(jù)容量。楊康等人(2017)基于漢字字頻提出了一種針對漢字的變長編碼方案，這也屬于在信源處對位流編碼方案進行了壓縮。鄭志學(xué)(2020)提出同時使用壓縮和加密兩種技術(shù)生成防偽二維碼。

4)通過自定義模塊排布方式增大編碼區(qū)域的面積占比。Villn等人(2006)提出了一種多級別二維條碼。這種條碼格式?jīng)]有位置探測圖形等功能圖形，因此編碼區(qū)域比標(biāo)準(zhǔn)二維碼更大。具有較大編碼面積并且同時具有較美觀外表的二維條碼格式有PiCode(picture-embedding 2D barcode)(Chen等，2016)和RA Code(robust and aesthetic code)(Chen等，2018)等。

除上述幾類工作外，還有一些旨在提高二維碼容量的研究工作。Yuan等人(2019)提出了雙層二維碼，利用視角差在左右兩個方向顯示不同的二維碼，并且可以用標(biāo)準(zhǔn)二維碼解碼器解碼。但是雙層二維碼要求相機處于特定的角度范圍才能解碼，而且解碼成功率比標(biāo)準(zhǔn)二維碼低。Chou和Wang(2020)提出了嵌套二維碼，在外層二維碼圖案的內(nèi)部嵌入了一個尺寸更小的內(nèi)層二維碼，標(biāo)準(zhǔn)掃碼器可以分別從外層二維碼和內(nèi)層二維碼中獲取不同消息。但是內(nèi)外兩個二維碼的尺寸差異較大，導(dǎo)致較小的二維碼較難解碼，而且用戶不易選擇掃描哪個二維碼。

綜上所述，目前沒有一種方法能在兼容標(biāo)準(zhǔn)二維碼解碼器且不影響糾錯能力的前提下提升數(shù)據(jù)容量。

2 位流編碼格式

本節(jié)介紹二維碼標(biāo)準(zhǔn)GB/T18284-2000(國家質(zhì)量技術(shù)監(jiān)督局，2000)所采用的位流編碼格式。二維碼有40個版本，從版本1到版本40。版本越大，模塊數(shù)量越多，碼字總數(shù)越多。同時，二維碼有4個糾錯等級，即L、M、Q和H，分別代表糾錯能力大約7%、15%、25%和30%。糾錯等級越高，數(shù)據(jù)碼字占碼字總數(shù)的比例越小。對于給定的版本和糾錯等級，數(shù)據(jù)碼字?jǐn)?shù)量可查表得到。每個數(shù)據(jù)碼字表示8個二進制位，因此，位流長度不能超過數(shù)據(jù)碼字?jǐn)?shù)量的8倍。

位流包含若干段(segment)，每一段分別編碼了一部分?jǐn)?shù)據(jù)或編碼了附加特性(additional features)。每個編碼數(shù)據(jù)的段分為3部分，從前往后分別是模式指示符(mode indicator)、字符計數(shù)指示符(character count indicator)和數(shù)據(jù)。模式指示符表示這一段采用的編碼模式(mode)。編碼模式共有4種，即數(shù)字模式、字母數(shù)字模式、8位字節(jié)模式和中國漢字模式，占用4位。其中，數(shù)字模式只能編碼數(shù)字；字母數(shù)字模式可以編碼大寫字母、數(shù)字和9種符號；8位字節(jié)模式可以編碼任意二進制數(shù)據(jù)；中國漢字模式只能編碼中國漢字。特別地，中國漢字模式的模式指示符之后有中國漢字子集指示符，長度是4位，只有一種取值0001，表示GB2312 字符集。字符計數(shù)指示符表示這一段編碼數(shù)據(jù)的長度。字符計數(shù)指示符占用的位數(shù)隨模式和二維碼版本變化，可查表得到。在數(shù)字模式下，每3個數(shù)字字符編碼成10位；如果數(shù)據(jù)長度不是3的整數(shù)倍，則剩余的 1個字符編碼成4位，或者剩余的2個字符編碼成7位。字母數(shù)字模式、8位字節(jié)模式和中國漢字模式編碼數(shù)據(jù)所需位數(shù)如表1所示。附加特性有專門的格式，可編碼結(jié)構(gòu)鏈接(structured append)信息、擴充解釋(extended channel interpretation, ECI)信息，不用于編碼字符。本文所稱的位流不包含終止符、填充位和填充碼字。

表1 各模式編碼n個字符所需位數(shù)Table 1 The number of bits to encode n character in each mode /bit

算法和實驗不考慮中國漢字模式，原因如下：1)中國漢字模式與國際二維碼標(biāo)準(zhǔn)不兼容。2)解碼器即使支持中國漢字模式(例如微信和支付寶的掃一掃、開源解碼器ZXing等)，也對含中國漢字模式的二維碼解碼有誤。3)在實驗獲取的2 000多個二維碼中，只有一個二維碼使用中國漢字模式，其他二維碼的漢字是通過代碼頁(例如UTF-8、GB2312等)轉(zhuǎn)換成多個字節(jié)后用8位字節(jié)模式編碼的。

一種簡單的位流編碼算法是使用單一模式編碼所有數(shù)據(jù)，并且盡量使用數(shù)據(jù)位數(shù)少的模式，即數(shù)字模式優(yōu)先，字母數(shù)字模式次之，不能用以上兩種模式編碼時使用8位字節(jié)模式編碼，開源編碼器ZXing使用這種算法。對各種模式和糾錯等級，二維碼標(biāo)準(zhǔn)以表格形式給出了各版本二維碼能容納的字符數(shù)量，編碼器可根據(jù)該表格決定二維碼的版本。劉悅和劉明業(yè)(2005)指出了上述表格中的錯誤。

與使用單一模式相比，在不同模式之間切換可能得到更短的位流。例如，數(shù)字字符可以用3種模式編碼，使用數(shù)字模式編碼的數(shù)據(jù)位數(shù)最少，字母數(shù)字模式編碼的數(shù)據(jù)位數(shù)次之，8位字節(jié)模式編碼的數(shù)據(jù)位數(shù)最多。然而，如果前一個字符使用8位字節(jié)模式編碼，那么切換到數(shù)字模式需要添加模式指示符和字符計數(shù)指示符，反而可能使總體位流變長。最優(yōu)位流編碼需要權(quán)衡總體數(shù)據(jù)位數(shù)和切換模式的開銷。二維碼標(biāo)準(zhǔn)的附錄給出了“位流長度的最優(yōu)化”方法。這是一種基于規(guī)則的方法，根據(jù)連續(xù)同類型字符長度(例如連續(xù)數(shù)字字符數(shù)量)切換模式，但該算法并不是最優(yōu)算法。

3 提出的算法

3.1 位流長度最小化

給定長度為l(l≥1)的輸入數(shù)據(jù)，輸入數(shù)據(jù)的第i個字符記做si(1≤i≤l)，si是8位字節(jié)。目標(biāo)是用最短的位流編碼輸入數(shù)據(jù)。

因此，Di是這6個符號的最小值，即

(1)

用Σm(m∈{n,a,b})表示對應(yīng)模式的字符集，有包含關(guān)系Σn?Σa?Σb。用hm(m∈{n,a,b})表示對應(yīng)模式的模式指示符與字符計數(shù)指示符的位數(shù)之和。

(2)

再考慮第i(2≤i≤l)個字符用數(shù)字模式編碼且是所在段的第k′(k′ ≡ 2 mod 3)個字符的情況。只有當(dāng)?shù)趇-1個字符用數(shù)字模式編碼且是所在段的第k′′(k′′ ≡ 1 mod 3)個字符，且第i個字符沿用該數(shù)字模式段時才可以得到符合條件的編碼，因此

(3)

同理可得

(4)

(5)

(6)

(7)

特別地，對于第1個字符，可得

(8)

至此，位流長度最小化問題已轉(zhuǎn)換為動態(tài)規(guī)劃問題。

引理1 給定版本和輸入數(shù)據(jù)，可以在O(l)時間內(nèi)計算最短位流。

定理1 給定輸入數(shù)據(jù)和糾錯等級，可以在O(l)時間內(nèi)計算最短位流及對應(yīng)的版本。

輸入：數(shù)據(jù)s、糾錯等級ECL，

輸出：位流BS、版本V，

1) function minimum_BS(s,ECL)，

2) forV= 1 to 40 do，

3) ifV∈{1, 10, 27} then，

5) fori= 2 toldo，

7)BS←長度等于Dl的位流，

8) ifDl≤最大位流長度(V,ECL) then，

9) returnBS,V，

10) return 編碼失敗。

3.2 統(tǒng)一資源定位符的最優(yōu)編碼

統(tǒng)一資源定位符通常由協(xié)議(scheme)、主機 (host)和路徑等字段組成。常見的統(tǒng)一資源定位符協(xié)議包括超文本傳輸協(xié)議(hypertext transfer protocol，HTTP)和文件傳輸協(xié)議(file transfer protocol，F(xiàn)TP)等。

根據(jù)RFC(request for comments)1738統(tǒng)一資源定位符規(guī)范，協(xié)議字段對大小寫不敏感。根據(jù)RFC 1035域名規(guī)范，主機字段對大小寫不敏感。因為小寫字母只能用8位字節(jié)模式編碼，而大寫字母既可以用8位字節(jié)模式編碼，又可以用字母數(shù)字模式編碼，所以將對大小寫不敏感的字符轉(zhuǎn)換成大寫字母可以縮短位流長度。例如“http://example.com/”和“HTTP://EXAMPLE.COM/”是等效的統(tǒng)一資源定位符，前者最短位流長度是164，后者最短位流長度是118。

(9)

式中，uc(si)表示si的大寫形式(upper case)，若si不是字母，則定義uc(si)=si。

因為用8位字節(jié)模式編碼轉(zhuǎn)義序列的任一字符一定會使總體位流長度比直接編碼轉(zhuǎn)義字符更長，所以無需考慮轉(zhuǎn)義序列的任一字符由8位字節(jié)模式編碼的情況。因為最短位流的任意相鄰兩段的模式一定不同(否則，將它們合并為一段將更短)，所以無需考慮任意連續(xù)兩段模式相同的情況。用c(si)表示字符si的轉(zhuǎn)義序列末尾屬于數(shù)字字符集的字符數(shù)量，值域是{0,1,2}。對于第i(2≤i≤l)個字符，如果該字符可以轉(zhuǎn)義，則有

(10)

(11)

若c(si)=2，則

(12)

(13)

(14)

若c(si)≥1，則

(15)

(16)

(17)

(18)

若第i個字符屬于字母數(shù)字模式字符集，或者是對大小寫不敏感的字段的小寫字母，則直接用字母數(shù)字模式編碼必然比轉(zhuǎn)義后編碼更短，無需轉(zhuǎn)義優(yōu)化。此外，如果輸入數(shù)據(jù)已經(jīng)經(jīng)過了轉(zhuǎn)義，且第i個字符是轉(zhuǎn)義序列中的字符，則按照規(guī)范不能對si再次轉(zhuǎn)義，不能應(yīng)用轉(zhuǎn)義優(yōu)化；此時si對大小寫不敏感，可以應(yīng)用大小寫不敏感字段優(yōu)化。綜合上述條件，若第i個字符屬于協(xié)議特定部分，且不屬于字母數(shù)字模式字符集，不是轉(zhuǎn)義序列中的字符，不是對大小寫不敏感的字段的小寫字母，則重新定義為

(19)

定理2 給定統(tǒng)一資源定位符和糾錯等級，可以在O(l)時間內(nèi)計算大小寫和轉(zhuǎn)義意義下等效的位流中最短的位流及對應(yīng)的版本。

輸入：數(shù)據(jù)s、糾錯等級ECL，

輸出：位流BS、版本V，

1 function minimum_BS_improved(s,ECL)，

2 if is_not_URL(s) then，

3 return minimum_BS(s,ECL)，

4 forV= 1 to 40 do，

5 ifV∈{1, 10, 27} then，

7 fori= 2 toldo，

10BS←長度等于Dl的位流，

11 ifDl≤最大位流長度(V,ECL) then，

12 returnBS,V，

13 return 編碼失敗。

4 實 驗

4.1 參與比較的算法

二維碼標(biāo)準(zhǔn)中的位流長度最優(yōu)化算法(以下簡稱標(biāo)準(zhǔn)算法)定義了字母數(shù)字模式專有子集ΣbΣa以及字符模式專有子集ΣaΣn。編碼時，根據(jù)當(dāng)前字符所屬的字符集(或?qū)Ｓ凶蛹?及連續(xù)的來自相同字符集(或來自相同專有子集)的字符數(shù)量切換編碼模式。例如輸入數(shù)據(jù)“abc123456def”，編碼第4個字符時，因為連續(xù)6個字符屬于數(shù)字字符集，因此切換到數(shù)字模式，位流長度比全部用8位字節(jié)模式編碼短2位。標(biāo)準(zhǔn)算法有可能陷入局部最優(yōu)。例如輸入數(shù)據(jù)“1234567Ab”，用數(shù)字模式編碼“1234567”，用8位字節(jié)模式編碼“Ab”是最優(yōu)的；但是標(biāo)準(zhǔn)算法使用字母數(shù)字模式編碼“A”，用8位字節(jié)模式編碼“b”。標(biāo)準(zhǔn)算法與最優(yōu)編碼相比，增加了字母數(shù)字模式的模式指示符4位、字符計數(shù)指示符9位，只減少了數(shù)據(jù)位數(shù)2位，總體位流長度增加了4+9-2=11。除中國漢字模式外，二維碼標(biāo)準(zhǔn)GB/T18284：2000中的位流長度最優(yōu)化算法與國際二維碼標(biāo)準(zhǔn)ISO/IEC18004:2000相同。因為國際二維碼標(biāo)準(zhǔn)已更新為ISO/IEC18004:2015，位流長度最優(yōu)化算法有所改進，所以實驗對比的標(biāo)準(zhǔn)算法是國際標(biāo)準(zhǔn)ISO/IEC18004:2015。

開源編解碼器ZXing的位流編碼算法比較簡單。該算法使用單一編碼模式，如果所有字符都屬于Σn，則使用數(shù)字模式編碼；否則，如果所有字符都屬于Σa，則使用字母數(shù)字模式編碼；否則，使用8位字節(jié)模式編碼。以下將這種使用單一編碼模式編碼所有數(shù)據(jù)的算法稱為單模算法。

據(jù)黑盒測試，商業(yè)編碼器“草料二維碼生成器”的位流編碼算法是對于所有輸入數(shù)據(jù)都使用8位字節(jié)模式編碼。因為這種算法輸出的位流一定不比單模算法短，所以實驗不比較這種算法。

單模算法、標(biāo)準(zhǔn)算法和最小化算法對幾種特定的輸入數(shù)據(jù)編碼的位流長度如表2所示。

表2 3種算法輸出位流長度舉例Table 2 Examples of output bit stream length of three algorithms /bit

4.2 二維碼測試集

為了獲取實際場景的二維碼圖像，實驗使用百度、搜狗、360、谷歌、必應(yīng)(國內(nèi)版和國際版)和雅虎等圖像搜索引擎分別搜索“二維碼”和“QR Code”，搜索日期是2021年2月3日。對下載的每幅圖像使用開源解碼器ZXing解碼。部分圖像無法解碼，原因主要包括：圖像主體內(nèi)容不是二維碼、圖片含多個二維碼導(dǎo)致解碼器無法定位、二維碼污損或遮擋和二維碼模塊規(guī)格不標(biāo)準(zhǔn)等。位流互異或糾錯等級互異的二維碼均視為互異的二維碼。去除ZXing無法解碼的圖像后，得到2 289個互異的二維碼。再去除1個含中國漢字模式的二維碼、6個含Kanji模式(一種只在國際標(biāo)準(zhǔn)里定義的模式)的二維碼后，測試集包含2 282個互異的二維碼。根據(jù)二維碼數(shù)據(jù)是否為統(tǒng)一資源定位符，將測試集劃分為非URL測試集和URL測試集。非URL測試集包含603個二維碼，URL測試集包含1 679個二維碼。實驗只考慮了協(xié)議為http、https、ftp、ftps、mailto的統(tǒng)一資源定位符。測試集中位流長度屬于各區(qū)間的二維碼樣本數(shù)量如圖2所示。

圖2 測試集位流長度分布Fig.2 Distribution of bit stream length in the test set

4.3 位流長度與版本的優(yōu)化效果

對測試集中的每個二維碼分別重新編碼。部分二維碼包含附加特性。在重新編碼過程中，所有附加特性段保留原樣，且附加特性段在字符數(shù)據(jù)中的位置保持不變。表3和表4比較了標(biāo)準(zhǔn)算法、單模算法、位流長度最小化算法和統(tǒng)一資源定位符的最優(yōu)編碼算法輸出的位流的平均長度，以及各算法輸出的位流長度相較標(biāo)準(zhǔn)算法有所減小的二維碼數(shù)量占測試集的比例。由于位流長度的減小需要通過二維碼版本的減小才能反映到最終印刷品的面積或印刷質(zhì)量上，因此表中還給出了各編碼算法輸出的二維碼版本相較標(biāo)準(zhǔn)算法有所減小的二維碼占比，其中標(biāo)準(zhǔn)算法輸出的版本等于1的二維碼不計入分母。實驗數(shù)據(jù)表明，對于非URL測試集(包含603個二維碼，其中419個二維碼標(biāo)準(zhǔn)算法輸出的版本大于1)，本文算法將平均位流長度減小了0.4%，減小了其中55個(9.1%)二維碼的位流長度，減小了其中5個(1.2%)二維碼的版本；對于URL測試集(包含1 679個二維碼，其中1 657個二維碼標(biāo)準(zhǔn)算法輸出的版本大于1)，本文算法將平均位流長度減小了13.9%，減小了1 652個(98.4%)二維碼的位流長度，減小了525個(31.7%)二維碼的版本。圖3給出了本文提出算法輸出的二維碼版本比標(biāo)準(zhǔn)算法小的示例。

表3 在非URL測試集上位流長度或版本減小的二維碼占比Table 3 The ratio of QR codes of which bit stream length or version can be reduced on the test set with non-URL data

表4 在URL測試集上位流長度或版本減小的二維碼占比Table 4 The ratio of QR codes of which bit stream length or version can be reduced on the test set with URL data

圖3 本文提出算法減小二維碼版本的示例Fig.3 QR code examples of which version is reduced by the proposed algorithm((a)initial QR code;(b)standard algorithm;(c)minimization algorithm;(d)URL minimization algorithm)

4.4 掃碼成功率的優(yōu)化效果

實驗對比了參考二維碼(指標(biāo)準(zhǔn)算法生成的二維碼)與最小二維碼在不同模糊程度下的掃碼成功率。用標(biāo)準(zhǔn)差為σ的二維高斯核對二維碼圖像進行模糊；其中，圖像的分辨率為300 × 300像素，二維碼占據(jù)圖像正中間的200 × 200像素。分別統(tǒng)計2 282幅參考二維碼圖像和2 282幅最小二維碼圖像的掃碼成功數(shù)量，統(tǒng)計結(jié)果如圖4所示。實驗數(shù)據(jù)表明，當(dāng)σ在[1.7, 5.5]范圍時，本文算法將掃碼成功圖像數(shù)量提高了10幅以上；當(dāng)σ在[3.6, 4.8]范圍時，本文算法將掃碼成功圖像數(shù)量提高了100幅以上。

圖4 掃碼成功圖像數(shù)量與高斯核的標(biāo)準(zhǔn)差的關(guān)系Fig.4 The number of successfully scanned images against kernel standard deviation of Gaussian blur

4.5 統(tǒng)一資源定位符的最優(yōu)編碼的消融實驗

統(tǒng)一資源定位符的最優(yōu)編碼算法包含兩個優(yōu)化：1)大小寫不敏感字段優(yōu)化(式(6))；2)轉(zhuǎn)義優(yōu)化(式(8))。實驗在URL測試集上測試了4種優(yōu)化組合輸出的位流長度和二維碼版本相較標(biāo)準(zhǔn)算法減小的二維碼占比，實驗結(jié)果如表5所示。實驗數(shù)據(jù)表明，單獨進行大小寫不敏感字段優(yōu)化或轉(zhuǎn)義優(yōu)化都有優(yōu)化效果。同時啟用兩項優(yōu)化時，得到的平均位流長度最小，位流長度減小和版本減小的二維碼占比最大。對于URL測試集，最小化算法只將平均位流長度減小了0.5%，而URL最優(yōu)編碼算法將平均位流長度減小了13.9%；最小化算法只減小了175個(10.4%)二維碼的位流長度，而URL最優(yōu)編碼算法減小了1 652個(98.4%)二維碼的位流長度；最小化算法只減小了21個(1.3%)二維碼的版本，而URL最優(yōu)編碼算法減小了525個(31.7%)二維碼的版本。

4.6 運行時間

實驗平臺的CPU是Intel Core i7-10700，內(nèi)存大小為32 GB；算法用C++實現(xiàn)。對于非URL測試集中的每個輸入數(shù)據(jù)，重復(fù)調(diào)用位流長度最小化算法10 000次，并記錄這10 000次運行時間的平均值。運行時間與輸入數(shù)據(jù)的長度的關(guān)系如圖5所示。實驗使用相同的方法測試了URL最優(yōu)編碼算法對URL測試集中的數(shù)據(jù)進行編碼的時間，如圖6所示。

圖5 非URL數(shù)據(jù)的編碼時間與數(shù)據(jù)長度的關(guān)系Fig.5 Encoding time against data length for non-URL data

圖6 URL數(shù)據(jù)的編碼時間與數(shù)據(jù)長度的關(guān)系Fig.6 Encoding time against data length for URL data

5 結(jié) 論

本文解決了二維碼位流長度最小化問題，提出的二維碼位流長度最小化算法可以計算最短位流。對于URL類型數(shù)據(jù)，URL最優(yōu)編碼算法進一步減小了位流長度，可以計算出大小寫和轉(zhuǎn)義意義下等效的統(tǒng)一資源定位符的最短位流。實驗結(jié)果表明，本文算法輸出的位流長度最短，輸出的二維碼版本最小，在一些實際場景中可以減小二維碼的版本，并且具有運算速度快的特點，其時間復(fù)雜度的上界與輸入數(shù)據(jù)長度呈線性關(guān)系。此外，本文算法易于使用，用戶只需輸入數(shù)據(jù)和糾錯等級即可，無需調(diào)節(jié)任何參數(shù)。

需要說明的是，本文只針對二維碼提出了位流長度最小化算法。Data Matrix和PDF417等其他條碼類型也使用與二維碼類似的編碼結(jié)構(gòu)，但是編碼細(xì)節(jié)存在差異，本文算法不能直接用于其他條碼類型的位流編碼。

在未來的工作中，可將本文算法的思路經(jīng)適配后用于最小化Data Matrix和PDF417等其他條碼類型的位流長度。同時，本文算法思路對于其他條碼類型是否有效也有待驗證。