نظام عددي غير متناظر

النظام العددي غير متناظر أو النظام العددي اللامتماثل (بالإنجليزية: Asymmetric Numeral Systems)‏ اختصارا (ANS)[1] هي أحد الطرق في عائلة الترميز الإنتروبي للضغط غير المنقوص، طرحت لأول مرة من قبل جاروسلو جاكر دوبا [2] من جامعة ياغيلونيا.

بدءا من العام 2014[3] استخدمت الانظمة العددية اللامتماثلة على نطاق واسع، نتيجة لتفوق سرعة التنفيذ مقارنة بالطرق السابقة بحوالي 30 ضعف.[4]ANS تدمج نسبة ضغط الترميز الحسابي (و الذي يستخدم احتمال توزيع دقيق نوعا ما) مع تكلفة معالجة قريبة من ترميز هوفمان، ANS يعتمد على الأرشفة وذلك ببناء آلة ذات حالات منتهية «ضمن جداول ANS Tables اختصارا (TANS)» لتعالج أبجدية كبيرة دون الحاجة للمضاعفة.

أهم مستخدمي ANS حاليا، منصة الضغط الخاصة بفيسبوك زدستاندر[5][6]، إضافة لنواة أنظمة لينكس،[7] وأندرويد[8] الصادرة برقم طلب تعليق RFC8478 لنظم امتدادات البريد المتعددة MIME[9]، وضمن بروتوكول HTTP[10] ، إضافة لمنصة الضغط الخاصة بأبل LZFSE[11]، وفي إمتدادات JPEG XL.

المبدأ

الفكرة الاساسية هي ترميز المعلومات إلى اعداد طبيعية $x$ ولوغارتم ثنائي قياسي حيث يمكن إضافة بت $s\in \{0,1\}$ من المعلومات إلى $x$ بإلحاق $s$ بنهاية $x$ والذي يعطينا $x'=2x+s$ لكل مرمز إنتروبي، فيكون الحل الامثل للمعادلة السابقة عندما $\Pr(0)=\Pr(1)=1/2$ حيث ان ANS يولد عملية تمثيل الخصائص للرموز $s\in S$ ذو توزيع إحتمالي $(p_{s})_{s\in S}$ ، لوغارتم ANS لنتيجة المعلومات الملحقة من $s$ إلى $x$ سيعطى بالعلاقة $x'$ ، فيكون $x'\approx x\cdot p_{s}^{-1}$ ، وبشكل مكافئ يمكن القول $\log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s})$ ، حيث $\log _{2}(x)$ عدد بتات المعلومات المخزنة في $x$ و $\log _{2}(1/p_{s})$ عدد البتات المحتواة في الرمز $s$ .

انظر أيضا

ترميز إنتروبي

ترميز هوفمان

المراجع

Duda, Jarek؛ Tahboub, Khalid؛ Gadgil, Neeraj J.؛ Delp, Edward J. (2015-05)، "The use of asymmetric numeral systems as an accurate replacement for Huffman coding"، 2015 Picture Coding Symposium (PCS)، IEEE، doi:10.1109/pcs.2015.7170048، ISBN 978-1-4799-7783-3، مؤرشف من الأصل في 26 أغسطس 2020. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)
"Jarosław Duda"، th.if.uj.edu.pl، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.
Buchloh, Benjamin H. D. (2019-05)، "New York's Other Factory: The Whitney Independent Study Program"، October، 168: 3–4، doi:10.1162/octo_a_00342، ISSN 0162-2870، مؤرشف من الأصل في 26 أغسطس 2020. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)
"Exxon Accused of Trying to Mislead Public"، Physics Today، 2007، doi:10.1063/pt.5.020739، ISSN 1945-0699، مؤرشف من الأصل في 26 أغسطس 2020.
Shun, Julian؛ Dhulipala, Laxman؛ Blelloch, Guy E. (2015-04)، "Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+"، 2015 Data Compression Conference، IEEE، doi:10.1109/dcc.2015.8، ISBN 978-1-4799-8430-5، مؤرشف من الأصل في 26 أغسطس 2020. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)
Hendrickson, W. A.؛ Ward, K. B. (27 أكتوبر 1975)، "Atomic models for the polypeptide backbones of myohemerythrin and hemerythrin"، Biochemical and Biophysical Research Communications، 66 (4): 1349–1356، doi:10.1016/0006-291x(75)90508-2، ISSN 1090-2104، PMID 5، مؤرشف من الأصل في 02 أبريل 2020.
"Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook - Phoronix"، www.phoronix.com، مؤرشف من الأصل في 25 يوليو 2019، اطلع عليه بتاريخ 25 أغسطس 2020.
"fs/btrfs/zstd.c - kernel/common - Git at Google"، android.googlesource.com، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.
"RFC 8478 - Zstandard Compression and the application/zstd Media Type"، datatracker.ietf.org، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.
"Hypertext Transfer Protocol (HTTP) Parameters"، www.iana.org، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.
"Apple Open-Sources its New Compression Algorithm LZFSE"، InfoQ (باللغة الإنجليزية)، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.

بوابة رياضيات
بوابة تقانة
بوابة برمجيات

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Duda, Jarek؛ Tahboub, Khalid؛ Gadgil, Neeraj J.؛ Delp, Edward J. (2015-05)، "The use of asymmetric numeral systems as an accurate replacement for Huffman coding"، 2015 Picture Coding Symposium (PCS)، IEEE، doi:10.1109/pcs.2015.7170048، ISBN 978-1-4799-7783-3، مؤرشف من الأصل في 26 أغسطس 2020. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)

[2] "Jarosław Duda"، th.if.uj.edu.pl، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.

[3] Buchloh, Benjamin H. D. (2019-05)، "New York's Other Factory: The Whitney Independent Study Program"، October، 168: 3–4، doi:10.1162/octo_a_00342، ISSN 0162-2870، مؤرشف من الأصل في 26 أغسطس 2020. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)

[4] "Exxon Accused of Trying to Mislead Public"، Physics Today، 2007، doi:10.1063/pt.5.020739، ISSN 1945-0699، مؤرشف من الأصل في 26 أغسطس 2020.

[5] Shun, Julian؛ Dhulipala, Laxman؛ Blelloch, Guy E. (2015-04)، "Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+"، 2015 Data Compression Conference، IEEE، doi:10.1109/dcc.2015.8، ISBN 978-1-4799-8430-5، مؤرشف من الأصل في 26 أغسطس 2020. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |تاريخ= (مساعدة)

[6] Hendrickson, W. A.؛ Ward, K. B. (27 أكتوبر 1975)، "Atomic models for the polypeptide backbones of myohemerythrin and hemerythrin"، Biochemical and Biophysical Research Communications، 66 (4): 1349–1356، doi:10.1016/0006-291x(75)90508-2، ISSN 1090-2104، PMID 5، مؤرشف من الأصل في 02 أبريل 2020.

[7] "Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook - Phoronix"، www.phoronix.com، مؤرشف من الأصل في 25 يوليو 2019، اطلع عليه بتاريخ 25 أغسطس 2020.

[8] "fs/btrfs/zstd.c - kernel/common - Git at Google"، android.googlesource.com، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.

[9] "RFC 8478 - Zstandard Compression and the application/zstd Media Type"، datatracker.ietf.org، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.

[10] "Hypertext Transfer Protocol (HTTP) Parameters"، www.iana.org، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.

[11] "Apple Open-Sources its New Compression Algorithm LZFSE"، InfoQ (باللغة الإنجليزية)، مؤرشف من الأصل في 26 أغسطس 2020، اطلع عليه بتاريخ 25 أغسطس 2020.