ระบบตัวเลขอสมมาตร ( ANS ) ^{[ ‡ 1 ] [ ‡ 2 ]}เป็นกลุ่มของวิธีการเข้ารหัสเอนโทรปี ที่คิดค้นโดย Jarosław (Jarek) Duda ^{[ ‡ 3 ]}จากมหาวิทยาลัย Jagiellonianซึ่งใช้ในการบีบอัดข้อมูลตั้งแต่ปี 2014 ^{[ ‡ 4 ]}เนื่องจากประสิทธิภาพที่ดีขึ้นเมื่อเทียบกับวิธีการก่อนหน้า^{[ 1 ]} ANS ผสมผสานอัตราส่วนการบีบอัดของการเข้ารหัสเลขคณิต (ซึ่งใช้การกระจายความน่าจะเป็น ที่แม่นยำเกือบทั้งหมด ) เข้ากับต้นทุนการประมวลผลที่คล้ายกับการเข้ารหัส Huffman ^{[ ‡ 1 ]}ในรูปแบบ ANS แบบตาราง (tANS) นี้ ทำได้โดยการสร้างเครื่องสถานะจำกัดเพื่อทำงานกับตัวอักษรขนาดใหญ่โดยไม่ต้องใช้การคูณ^{[ ‡ 2 ]}

ANS ถูกใช้ในคอมเพรสเซอร์Facebook Zstandard ^{[ 2 ] [ 3 ]} (ใช้ในเคอร์เนลLinux ^{[ 4 ]} เบราว์เซอร์Google Chrome ^{[ 5 ]} ระบบปฏิบัติการ Android ^{[ 6 ]}และเผยแพร่เป็น RFC  8478 สำหรับMIME ^{[ 7 ]}และHTTP ^{[ 8 ]} ด้วยเช่นกัน ) คอมเพรสเซอร์Apple LZFSE ^{[ 9 ]} คอมเพรสเซอร์ Google Draco 3D ^{[ 10 ]} (ใช้ในรูปแบบPixar Universal Scene Description ^{[ 11 ]} ) และคอมเพรสเซอร์รูปภาพ PIK ^{[ 12 ]} คอมเพรสเซอร์ CRAM DNA ^{[ 13 ]}จาก ยูทิ ลิตี้SAMtools ^{[ 14 ]} ไลบรารีการบีบอัดความเร็วสูง NVIDIA nvCOMP ^{[ 15 ]} คอมเพรสเซอร์ Dropbox DivANS ^{[ 16 ]} คอมเพรสเซอร์พื้นผิว Microsoft DirectStorage BCPack ^{[ 17 ]} JPEG XLระยะยาว^{[ 18 ]} และ คอมเพรสเซอร์รูปภาพJPEG AI ที่ใช้การเรียนรู้^{[ 19 ]}

แนวคิดพื้นฐานคือการเข้ารหัสข้อมูลลงในจำนวนธรรมชาติเพียงจำนวนเดียว${\displaystyle x}$[ ^{‡ 2 ]}ในระบบเลขฐานสองมาตรฐาน เราสามารถเพิ่มบิต^ได้${\displaystyle s\in \{0,1\}}$ข้อมูลถึง${\displaystyle x}$โดยการต่อท้าย${\displaystyle s}$ในตอนท้ายของ${\displaystyle x}$ซึ่งทำให้เราได้${\displaystyle x'=2x+s}$สำหรับตัวเข้ารหัสเอนโทรปีแล้ว วิธีนี้จะเหมาะสมที่สุดหาก${\displaystyle \Pr(0)=\Pr(1)=1/2}$ANS ขยายกระบวนการนี้ไปใช้กับชุดสัญลักษณ์ใดๆ ก็ได้${\displaystyle s\in S}$พร้อมด้วยการกระจายความน่าจะเป็นที่เกี่ยวข้อง${\displaystyle (p_{s})_{s\in S}}$ใน ANS หากข้อมูลจาก${\displaystyle s}$ถูกแนบมาด้วย${\displaystyle x}$ส่งผลให้${\displaystyle x'}$, แล้ว${\displaystyle x'\approx x\cdot p_{s}^{-1}}$ในทำนองเดียวกัน${\displaystyle \log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s})}$, ที่ไหน${\displaystyle \log _{2}(x)}$คือจำนวนบิตของข้อมูลที่จัดเก็บอยู่ในตัวเลข${\displaystyle x}$, และ${\displaystyle \log _{2}(1/p_{s})}$คือจำนวนบิตที่อยู่ในสัญลักษณ์นั้น${\displaystyle s}$[ ^{‡ 2 ]}

สำหรับกฎการเข้ารหัส เซตของจำนวนธรรมชาติจะถูกแบ่งออกเป็นเซตย่อยที่ไม่ซ้ำกันซึ่งสอดคล้องกับสัญลักษณ์ที่แตกต่างกัน–เหมือนกับการแบ่งเป็นจำนวนคู่และจำนวนคี่ แต่มีความหนาแน่นที่สอดคล้องกับการกระจายความน่าจะเป็นของสัญลักษณ์ที่จะเข้ารหัส จากนั้นจึงเพิ่มข้อมูลจากสัญลักษณ์เข้าไป ${\displaystyle s}$เข้าสู่ข้อมูลที่จัดเก็บไว้แล้วในหมายเลขปัจจุบัน${\displaystyle x}$เราไปที่หมายเลข${\displaystyle x'=C(x,s)\approx x/p}$เป็นตำแหน่งของ${\displaystyle x}$การปรากฏตัวครั้งที่ - จาก${\displaystyle s}$เซตย่อยที่ -th ^{[ ‡ 2 ]}

มีวิธีอื่นในการนำไปใช้ในทางปฏิบัติได้แก่สูตรทางคณิตศาสตร์โดยตรงสำหรับขั้นตอนการเข้ารหัสและการถอดรหัส (uABS และ rANS) หรือสามารถใส่พฤติกรรมทั้งหมดลงในตารางได้ (tANS) ^{[ ‡ 1 ]}การปรับค่าใหม่ใช้เพื่อป้องกัน ${\displaystyle x}$ไปสู่ค่าอนันต์–การถ่ายโอนบิตที่สะสมไปยังหรือจากบิตสตรีม^{[ ‡ 2 ]} 

สมมติว่าเราต้องการเข้ารหัสลำดับของเลขศูนย์และเลขหนึ่งจำนวน 1,000 ตัว ซึ่งจะต้องใช้พื้นที่ 1,000 บิตในการจัดเก็บโดยตรง อย่างไรก็ตาม หากทราบว่าลำดับดังกล่าวมีเลขศูนย์เพียง 1 ตัวและเลขหนึ่ง 999 ตัว ก็เพียงพอที่จะเข้ารหัสตำแหน่งของเลขศูนย์ ซึ่งใช้พื้นที่เพียง 1 บิตเท่านั้น${\displaystyle \lceil \log _{2}(1000)\rceil \approx 10}$ใช้บิตจำนวนน้อยลงแทนที่จะเป็น 1000 บิตตามเดิม

โดยทั่วไป ลำดับที่มีความยาวดังกล่าว${\displaystyle n}$ประกอบด้วย${\displaystyle pn}$ศูนย์และ${\displaystyle (1-p)n}$หนึ่ง ด้วยความน่าจะเป็นบางประการ${\displaystyle p\in (0,1)}$เรียกว่าการรวมกันโดยใช้การประมาณของสเตอร์ลิงเราจะได้จำนวนเชิงอะซิมโทติกของพวกมันเป็น

${\displaystyle {n \choose pn}\approx 2^{nh(p)}{\text{ สำหรับ n ที่มีค่ามาก }}n{\text{ และ }}h(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p),}$

เรียกว่าเอนโทรปีของแชนนอน^{[ 20 ]}

ดังนั้น ในการเลือกหนึ่งลำดับดังกล่าว เราจึงต้องการประมาณ${\displaystyle nh(p)}$บิต มันยังคงเป็น${\displaystyle n}$บิต ถ้า${\displaystyle p=1/2}$อย่างไรก็ตาม มันอาจจะเล็กกว่านั้นมากก็ได้ ตัวอย่างเช่น เราต้องการเพียงแค่${\displaystyle \approx n/2}$บิตสำหรับ${\displaystyle p=0.11}$.

ตัวเข้ารหัสเอนโทรปีช่วยให้สามารถเข้ารหัสลำดับของสัญลักษณ์โดยใช้บิตเอนโทรปีของแชนนอนโดยประมาณต่อสัญลักษณ์ ตัวอย่างเช่น ANS สามารถใช้โดยตรงเพื่อแจงนับชุดค่าผสม: กำหนดจำนวนธรรมชาติที่แตกต่างกันให้กับลำดับของสัญลักษณ์แต่ละลำดับที่มีสัดส่วนคงที่ในลักษณะที่เกือบจะเหมาะสมที่สุด^{[ ‡ 2 ]}

ตรงกันข้ามกับชุดการเข้ารหัส การกระจายความน่าจะเป็นนี้มักจะแตกต่างกันไปในโปรแกรมบีบอัดข้อมูล ด้วยเหตุนี้ เอนโทรปีของแชนนอนจึงสามารถมองได้ว่าเป็นค่าเฉลี่ยถ่วงน้ำหนัก: สัญลักษณ์ของความน่าจะเป็น${\displaystyle p}$ประกอบด้วย${\displaystyle \log _{2}(1/p)}$บิตของข้อมูล ระบบเลขฐานสิบหก (ANS) เข้ารหัสข้อมูลลงในจำนวนธรรมชาติเพียงจำนวนเดียว${\displaystyle x}$ซึ่งตีความได้ว่าประกอบด้วย${\displaystyle \log _{2}(x)}$ข้อมูลย่อย การเพิ่มข้อมูลจากสัญลักษณ์ความน่าจะเป็น${\displaystyle p}$เพิ่มเนื้อหาข้อมูลนี้ให้มากขึ้น${\displaystyle \log _{2}(x)+\log _{2}(1/p)=\log _{2}(x/p)}$ดังนั้น ตัวเลขใหม่ที่ประกอบด้วยข้อมูลทั้งสองอย่างควรจะเป็น${\displaystyle x'\approx x/p}$[ ^{‡ 2 ]}

ลองนึกภาพว่ามีข้อมูลบางอย่างถูกเก็บไว้ในจำนวนธรรมชาติ${\displaystyle x}$ตัวอย่างเช่น ลำดับบิตของการขยายเลขฐานสอง เพื่อเพิ่มข้อมูลจากตัวแปรเลขฐานสอง${\displaystyle s}$เราสามารถใช้ฟังก์ชันการเขียนโค้ดได้${\displaystyle x'=C(x,s)=2x+s}$ซึ่งจะเลื่อนบิตทั้งหมดขึ้นไปหนึ่งตำแหน่ง และวางบิตใหม่ไว้ในตำแหน่งที่มีค่าน้อยที่สุด ทีนี้มาดูฟังก์ชันการถอดรหัสกัน${\displaystyle D(x')=(\lfloor x'/2\rfloor ,\mathrm {mod} (x',2))}$ช่วยให้สามารถเรียกดูข้อมูลก่อนหน้าได้${\displaystyle x}$และส่วนเพิ่มเติมนี้:${\displaystyle D(C(x,s))=(x,s),\ C(D(x'))=x'}$เราสามารถเริ่มต้นด้วย${\displaystyle x=1}$สถานะเริ่มต้น จากนั้นใช้${\displaystyle C}$ใช้ฟังก์ชันกับบิตที่ต่อเนื่องกันของลำดับบิตจำกัดเพื่อให้ได้ผลลัพธ์สุดท้าย${\displaystyle x}$หมายเลขที่เก็บลำดับทั้งหมดนี้ จากนั้นใช้${\displaystyle D}$ฟังก์ชันนี้ทำงานหลายครั้งจนกระทั่ง${\displaystyle x=1}$ช่วยให้สามารถเรียกกลับลำดับบิตในลำดับย้อนกลับได้^{[ ‡ 2 ]}

วิธีการข้างต้นเหมาะสมที่สุดสำหรับการกระจายความน่าจะเป็นแบบสม่ำเสมอ (สมมาตร) ของสัญลักษณ์${\displaystyle \Pr(0)=\Pr(1)=1/2}$ANS ขยายความให้เหมาะสมที่สุดสำหรับรูปแบบการแจกแจงความน่าจะเป็นแบบไม่สมมาตรของสัญลักษณ์ใดๆ ที่เลือกไว้:${\displaystyle \Pr(s)=p_{s}}$. ในขณะที่${\displaystyle s}$ในตัวอย่างข้างต้นคือการเลือกระหว่างเลขคู่และเลขคี่${\displaystyle C(x,s)}$ใน ANS การแบ่งจำนวนธรรมชาติแบบคู่/คี่จะถูกแทนที่ด้วยการแบ่งออกเป็นเซตย่อยที่มีความหนาแน่นสอดคล้องกับการกระจายความน่าจะเป็นที่กำหนดไว้${\displaystyle \{p_{s}\}_{s}}$: จนถึงตำแหน่ง${\displaystyle x}$มีอยู่ประมาณ${\displaystyle xp_{s}}$การปรากฏของสัญลักษณ์${\displaystyle s}$[ ^{‡ 2 ]}

ฟังก์ชันการเข้ารหัส${\displaystyle C(x,s)}$ส่งคืน${\displaystyle x}$การปรากฏครั้งที่ - จากชุดย่อยดังกล่าวที่สอดคล้องกับสัญลักษณ์${\displaystyle s}$ข้อสมมติเรื่องความหนาแน่นนั้นเทียบเท่ากับเงื่อนไขดังกล่าว${\displaystyle x'=C(x,s)\approx x/p_{s}}$โดยสมมติว่าเป็นจำนวนธรรมชาติ${\displaystyle x}$ประกอบด้วย${\displaystyle \log _{2}(x)}$ข้อมูลเล็กๆ น้อยๆ${\displaystyle \log _{2}(C(x,s))\approx \log _{2}(x)+\log _{2}(1/p_{s})}$ดังนั้นจึงเป็นสัญลักษณ์แห่งความน่าจะเป็น${\displaystyle p_{s}}$ถูกเข้ารหัสโดยมีเนื้อหาอยู่ภายใน${\displaystyle \approx \log _{2}(1/p_{s})}$บิตของข้อมูลตามที่ต้องการจากตัวเข้ารหัสเอนโทรปี [ ^{‡ 2 ]}

สำหรับการเข้ารหัส Huffman การปรับเปลี่ยนการกระจายความน่าจะเป็นของ tANS นั้นมีต้นทุนค่อนข้างสูง ดังนั้นจึงมักใช้ในสถานการณ์คงที่ โดยปกติจะใช้กับ รูปแบบ Lempel–Ziv บาง รูปแบบ (เช่น ZSTD, ^{[ 2 ]} LZFSE ^{[ 9 ]} ) ในกรณีนี้ ไฟล์จะถูกแบ่งออกเป็นบล็อกโดยแต่ละบล็อกจะนับความถี่ของสัญลักษณ์อย่างอิสระ จากนั้นหลังจากประมาณค่า (การหาปริมาณ) จะเขียนลงในส่วนหัวของบล็อกและใช้เป็นการกระจายความน่าจะเป็นแบบคงที่สำหรับ tANS ^{[ ‡ 1 ]} 

ในทางตรงกันข้าม rANS มักใช้แทนการเข้ารหัสช่วง ที่เร็วกว่า ( เช่นCRAM ^{[ 13 ]} LZNA, Draco ^{[ 10 ]} ) ต้องใช้การคูณ แต่มีประสิทธิภาพด้านหน่วยความจำมากกว่าและเหมาะสมสำหรับการปรับเปลี่ยนการกระจายความน่าจะเป็นแบบไดนามิก^{[ ‡ 2 ]}

การเข้ารหัสและการถอดรหัสของ ANS ดำเนินการในทิศทางตรงกันข้าม ทำให้เป็นสแต็กสำหรับสัญลักษณ์ ความไม่สะดวกนี้มักจะได้รับการแก้ไขโดยการเข้ารหัสในทิศทางย้อนกลับ หลังจากนั้นจึงสามารถถอดรหัสไปข้างหน้าได้^{[ ‡ 2 ]}สำหรับการพึ่งพาบริบท เช่นแบบจำลองมาร์คอฟตัวเข้ารหัสจำเป็นต้องใช้บริบทจากมุมมองของการถอดรหัสในภายหลัง สำหรับการปรับตัว ตัวเข้ารหัสควรดำเนินการไปข้างหน้าก่อนเพื่อค้นหาความน่าจะเป็นที่จะใช้ (ทำนาย) โดยตัวถอดรหัสและจัดเก็บไว้ในบัฟเฟอร์ จากนั้นเข้ารหัสในทิศทางย้อนกลับโดยใช้ความน่าจะเป็นที่จัดเก็บไว้ในบัฟเฟอร์^{[ ‡ 2 ]}

สถานะสุดท้ายของการเข้ารหัสจำเป็นสำหรับการเริ่มต้นการถอดรหัส ดังนั้นจึงต้องจัดเก็บไว้ในไฟล์บีบอัด ค่าใช้จ่ายนี้สามารถชดเชยได้โดยการจัดเก็บข้อมูลบางอย่างไว้ในสถานะเริ่มต้นของตัวเข้ารหัส ตัวอย่างเช่น แทนที่จะเริ่มต้นด้วยสถานะ "10000" ให้เริ่มต้นด้วยสถานะ "1****" โดยที่ "*" คือบิตที่จัดเก็บเพิ่มเติม ซึ่งสามารถเรียกคืนได้เมื่อสิ้นสุดการถอดรหัส หรืออีกทางหนึ่ง สถานะนี้สามารถใช้เป็นค่าตรวจสอบความถูกต้องได้โดยการเริ่มต้นการเข้ารหัสด้วยสถานะคงที่ และทดสอบว่าสถานะสุดท้ายของการถอดรหัสเป็นไปตามที่คาดไว้หรือไม่^{[ ‡ 2 ]}

ผู้เขียนอัลกอริธึม ANS และรูปแบบต่างๆ เช่น tANS และ rANS ตั้งใจให้ผลงานของเขาสามารถเข้าถึงได้ฟรีในโดเมนสาธารณะด้วยเหตุผลด้านมนุษยธรรม เขาไม่ได้แสวงหาผลกำไรจากผลงานเหล่านี้ และได้ดำเนินการเพื่อให้แน่ใจว่าผลงานเหล่านี้จะไม่กลายเป็น "กับดักทางกฎหมาย" หรือถูกจำกัด หรือถูกแสวงหาผลกำไรจากผู้อื่น^{[ 1 ]}ในปี 2015 Google ได้เผยแพร่สิทธิบัตรในสหรัฐอเมริกาและทั่วโลกสำหรับ "การเข้ารหัสสัมประสิทธิ์ ans โทเค็นบูลีนแบบผสม" ^{[ 22 ]}ในขณะนั้น ศาสตราจารย์ Duda ได้รับคำขอจาก Google ให้ช่วยในเรื่องการบีบอัดวิดีโอ ดังนั้นเขาจึงมีความรู้ความเข้าใจอย่างลึกซึ้งในด้านนี้ โดยมีผู้เขียนต้นฉบับคอยให้ความช่วยเหลือ

ดูดาไม่พอใจที่ (บังเอิญ) ค้นพบเจตนาสิทธิบัตรของ Google เนื่องจากเขาระบุชัดเจนว่าต้องการให้เป็นสาธารณสมบัติ และได้ช่วยเหลือ Google โดยเฉพาะบนพื้นฐานนั้น^{[ 1 ]}ต่อมาดูดาได้ยื่นคำขอของบุคคลที่สาม^{[ ‡ 5 ]}ต่อสำนักงานสิทธิบัตรของสหรัฐอเมริกาเพื่อขอให้ปฏิเสธ สำนักงานสิทธิบัตรของสหรัฐอเมริกาปฏิเสธคำขอในปี 2018 และต่อมา Google ก็ละทิ้งสิทธิบัตรดังกล่าว^{[ 23 ]}

ในเดือนมิถุนายน พ.ศ. 2562 ไมโครซอฟต์ได้ยื่นคำขอสิทธิบัตรชื่อ "คุณสมบัติของการเข้ารหัสและการถอดรหัสระบบตัวเลขแบบไม่สมมาตรตามช่วง" ^{[ 24 ]}สำนักงานสิทธิบัตรสหรัฐฯ (USPTO) ได้ออกคำปฏิเสธขั้นสุดท้ายของคำขอเมื่อวันที่ 27 ตุลาคม พ.ศ. 2563 ^{[ 24 ]}อย่างไรก็ตาม เมื่อวันที่ 2 มีนาคม พ.ศ. 2564 ไมโครซอฟต์ได้ยื่นคำชี้แจงต่อ USPTO โดยระบุว่า "ผู้ยื่นคำขอไม่เห็นด้วยกับคำปฏิเสธดังกล่าว" ^{[ 25 ]}เพื่อขอให้ศาลพิจารณาคำปฏิเสธขั้นสุดท้ายอีกครั้งภายใต้โครงการ "After Final Consideration Pilot 2.0" ^{[ 26 ]}หลังจากการพิจารณาใหม่ USPTO ได้อนุมัติคำขอเมื่อวันที่ 25 มกราคม พ.ศ. 2565 ^{[ 24 ]}

• การเข้ารหัสเอนโทรปี
• การเข้ารหัสฮัฟฟ์แมน
• การเข้ารหัสเลขคณิต
• การเข้ารหัสช่วง
• ตัวบีบอัดข้อมูล Facebook ของ Zstandard
• คอมเพรสเซอร์LZFSE Apple

• Duda, Jarek (2 พฤศจิกายน 2008). "การเข้ารหัสที่เหมาะสมที่สุดบนโครงข่ายแบบไม่ต่อเนื่องที่มีข้อจำกัดที่ไม่เปลี่ยนแปลงตามการเลื่อนตำแหน่งโดยใช้อัลกอริธึมทางสถิติ". arXiv : 0710.3861 [ cs.IT ].ซึ่งอาจเป็นการกล่าวถึง ANS ครั้งแรกสุด
• สถาปัตยกรรมฮาร์ดแวร์ประสิทธิภาพสูงสำหรับการเข้ารหัสเอนโทรปีของระบบตัวเลขอสมมาตร SM Najmabadi, Z. Wang, Y. Baroud, S. Simon, ISPA 2015
• ตัวเข้ารหัสเอนโทรปีรุ่นใหม่การนำเอนโทรปีสถานะจำกัด (FSE) มาใช้ใน tANS โดย Yann Collet
• rygorous/ryg_ransการนำ rANS ไปใช้โดย Fabian Giesen
• jkbonfield/rans_staticการใช้งาน rANS และการเข้ารหัสเลขคณิตอย่างรวดเร็วโดย James K. Bonfield
• โปรแกรมบีบอัด DNA CRAM 3.0 (rANS ลำดับที่ 1) (ส่วนหนึ่งของSAMtools ) โดยสถาบันชีวสารสนเทศแห่งยุโรป
• การนำไปใช้สำหรับ Google VP10
• การใช้งานสำหรับ Google WebP
• ไลบรารีการบีบอัดข้อมูล 3 มิติ Google Draco
• aom_dsp - aom - การนำ Git มาใช้ใน Googleเพื่อสนับสนุนAlliance for Open Media
• การบีบอัดข้อมูลโดยใช้ระบบตัวเลขอสมมาตร - โครงการสาธิตของ Wolframโครงการสาธิตของ Wolfram
• GST: พื้นผิวบีบอัดแบบพิเศษที่ถอดรหัสได้ด้วย GPU GST: พื้นผิวบีบอัดแบบพิเศษที่ถอดรหัสด้วย GPU
• หนังสือ Understanding Compressionโดย A. Haecky และ C. McAnlis