จักรยานอีกรุ่น: เราจัดเก็บสตริง Unicode ขนาดกะทัดรัดกว่า UTF-30 ถึง 60-8%

หากคุณเป็นนักพัฒนาซอฟต์แวร์และต้องเผชิญกับงานในการเลือกการเข้ารหัส Unicode จะเป็นทางออกที่ถูกต้องเกือบทุกครั้ง วิธีการแสดงเฉพาะนั้นขึ้นอยู่กับบริบท แต่ส่วนใหญ่มักจะมีคำตอบสากลที่นี่เช่นกัน - UTF-8 ข้อดีของมันคือมันช่วยให้คุณใช้อักขระ Unicode ทั้งหมดได้โดยไม่ต้องเสียเงิน มากเกินไป ในกรณีส่วนใหญ่จะมีไบต์จำนวนมาก จริงอยู่ สำหรับภาษาที่ใช้มากกว่าตัวอักษรละติน อย่างน้อยก็ควร "ไม่มากเกินไป" สองไบต์ต่ออักขระ. เราจะทำได้ดีกว่านี้โดยไม่ต้องกลับไปใช้การเข้ารหัสยุคก่อนประวัติศาสตร์ที่จำกัดให้เราเหลือเพียง 256 อักขระเท่านั้นหรือไม่

ด้านล่างนี้ฉันเสนอให้ทำความคุ้นเคยกับความพยายามของฉันในการตอบคำถามนี้และใช้อัลกอริธึมที่ค่อนข้างง่ายซึ่งช่วยให้คุณจัดเก็บบรรทัดในภาษาส่วนใหญ่ของโลกโดยไม่ต้องเพิ่มความซ้ำซ้อนที่อยู่ใน UTF-8

ข้อสงวนสิทธิ์ ฉันจะทำการจองที่สำคัญบางประการทันที: โซลูชันที่อธิบายไว้ไม่ได้นำเสนอเป็นการทดแทนแบบสากลสำหรับ UTF-8มันเหมาะสมเฉพาะในกรณีแคบๆ เท่านั้น (ดูข้อมูลเพิ่มเติมด้านล่าง) และไม่ควรใช้เพื่อโต้ตอบกับ API ของบุคคลที่สาม (ผู้ที่ไม่รู้ด้วยซ้ำ) อัลกอริธึมการบีบอัดอเนกประสงค์ (เช่น แฟลต) มักเหมาะสำหรับการจัดเก็บข้อมูลข้อความจำนวนมากในขนาดกะทัดรัด นอกจากนี้ในกระบวนการสร้างโซลูชันของฉันแล้ว ฉันพบมาตรฐานที่มีอยู่ใน Unicode ซึ่งแก้ปัญหาเดียวกันได้ - มันค่อนข้างซับซ้อนกว่า (และมักจะแย่กว่านั้น) แต่ก็ยังเป็นมาตรฐานที่ยอมรับได้ ไม่ใช่แค่ใส่ ด้วยกันบนเข่า ฉันจะบอกคุณเกี่ยวกับเขาด้วย

เกี่ยวกับ Unicode และ UTF-8

เริ่มต้นด้วยคำสองสามคำเกี่ยวกับมันคืออะไร Unicode и UTF-8.

ดังที่คุณทราบ การเข้ารหัสแบบ 8 บิตเคยเป็นที่นิยม ทุกอย่างเป็นเรื่องง่าย: 256 อักขระสามารถกำหนดหมายเลขด้วยตัวเลขตั้งแต่ 0 ถึง 255 และตัวเลขตั้งแต่ 0 ถึง 255 สามารถแสดงเป็นหนึ่งไบต์ได้อย่างชัดเจน หากเราย้อนกลับไปที่จุดเริ่มต้น การเข้ารหัส ASCII ถูกจำกัดไว้ที่ 7 บิต ดังนั้นบิตที่สำคัญที่สุดในการแสดงไบต์จึงเป็นศูนย์ และการเข้ารหัส 8 บิตส่วนใหญ่ก็เข้ากันได้ (แตกต่างกันเฉพาะใน "ด้านบน" เท่านั้น ส่วนหนึ่ง โดยที่บิตที่สำคัญที่สุดคือหนึ่ง )

Unicode แตกต่างจากการเข้ารหัสเหล่านั้นอย่างไร และเหตุใดจึงมีการแสดงเฉพาะจำนวนมากที่เกี่ยวข้อง - UTF-8, UTF-16 (BE และ LE), UTF-32 มาเรียงลำดับกัน

มาตรฐาน Unicode พื้นฐานอธิบายเฉพาะความสอดคล้องระหว่างอักขระ (และในบางกรณี ส่วนประกอบแต่ละตัวของอักขระ) และตัวเลข และมีตัวเลขที่เป็นไปได้มากมายในมาตรฐานนี้ - จาก 0x00 ไปยัง 0x10FFFF (1 ชิ้น) หากเราต้องการใส่ตัวเลขในช่วงดังกล่าวลงในตัวแปร ขนาด 114 หรือ 112 ไบต์ก็ไม่เพียงพอสำหรับเรา และเนื่องจากโปรเซสเซอร์ของเราไม่ได้ออกแบบมาเพื่อทำงานกับตัวเลขสามไบต์มากนัก เราจึงถูกบังคับให้ใช้มากถึง 1 ไบต์ต่ออักขระ! นี่คือ UTF-2 แต่เป็นเพราะ "ความสิ้นเปลือง" ที่ทำให้รูปแบบนี้ไม่เป็นที่นิยม

โชคดีที่ลำดับของอักขระภายใน Unicode ไม่ใช่การสุ่ม ทั้งชุดแบ่งเป็น 17"เครื่องบิน" ซึ่งแต่ละอันมี 65536 (0x10000) «คะแนนรหัส" แนวคิดของ "จุดรหัส" ในที่นี้เป็นเพียง หมายเลขตัวอักษรกำหนดโดย Unicode แต่ดังที่ได้กล่าวไว้ข้างต้นใน Unicode ไม่เพียง แต่จะมีหมายเลขอักขระแต่ละตัวเท่านั้น แต่ยังรวมถึงส่วนประกอบและเครื่องหมายการบริการด้วย (และบางครั้งก็ไม่มีอะไรตรงกับตัวเลขเลย - บางทีอาจเป็นในขณะนี้ แต่สำหรับเราสิ่งนี้ไม่สำคัญนัก) ดังนั้น ถูกต้องมากกว่าเสมอ โดยเฉพาะเกี่ยวกับจำนวนตัวเลข ไม่ใช่สัญลักษณ์ อย่างไรก็ตาม เพื่อความกระชับ ต่อไปนี้ผมมักจะใช้คำว่า "สัญลักษณ์" ซึ่งหมายถึงคำว่า "จุดรหัส"

เครื่องบิน Unicode อย่างที่คุณเห็น ส่วนใหญ่ (เครื่องบิน 4 ถึง 13) ยังคงไม่ได้ใช้

สิ่งที่น่าทึ่งที่สุดคือ “เยื่อกระดาษ” หลักทั้งหมดอยู่ในระนาบศูนย์ เรียกว่า "เครื่องบินหลายภาษาขั้นพื้นฐาน" หากบรรทัดมีข้อความในภาษาสมัยใหม่ภาษาใดภาษาหนึ่ง (รวมถึงภาษาจีน) คุณจะไม่เกินระนาบนี้ แต่คุณไม่สามารถตัด Unicode ที่เหลือออกได้เช่นกัน - ตัวอย่างเช่นอิโมจิส่วนใหญ่จะอยู่ที่ส่วนท้ายของ เครื่องบินลำต่อไป”เครื่องบินหลายภาษาเสริม“(มันขยายจาก 0x10000 ไปยัง 0x1FFFF). UTF-16 ทำเช่นนี้: อักขระทุกตัวจะอยู่ภายใน เครื่องบินหลายภาษาขั้นพื้นฐานจะถูกเข้ารหัส “ตามสภาพ” ด้วยตัวเลขสองไบต์ที่สอดคล้องกัน อย่างไรก็ตาม ตัวเลขบางตัวในช่วงนี้ไม่ได้ระบุอักขระเฉพาะเจาะจงเลย แต่ระบุว่าหลังจากคู่ไบต์นี้ เราต้องพิจารณาอีกตัวหนึ่ง - โดยการรวมค่าของสี่ไบต์นี้เข้าด้วยกัน เราจะได้ตัวเลขที่ครอบคลุม ช่วง Unicode ที่ถูกต้องทั้งหมด แนวคิดนี้เรียกว่า “คู่รักอุ้มบุญ”—คุณอาจเคยได้ยินเรื่องนี้มาก่อน

ดังนั้น UTF-16 ต้องการสองหรือ (ในกรณีที่หายากมาก) สี่ไบต์ต่อ "จุดโค้ด" ซึ่งดีกว่าการใช้สี่ไบต์ตลอดเวลา แต่เมื่อเข้ารหัสแบบละติน (และอักขระ ASCII อื่นๆ) จะทำให้เสียพื้นที่ครึ่งหนึ่งของศูนย์ UTF-8 ได้รับการออกแบบมาเพื่อแก้ไขปัญหานี้: ASCII ในนั้นครอบครองเพียงไบต์เดียวเหมือนเมื่อก่อน รหัสจาก 0x80 ไปยัง 0x7FF - สองไบต์ จาก 0x800 ไปยัง 0xFFFF - สามและจาก 0x10000 ไปยัง 0x10FFFF - สี่ ในอีกด้านหนึ่งตัวอักษรละตินกลายเป็นดี: ความเข้ากันได้กับ ASCII กลับมาแล้วและการกระจายจะ "กระจาย" เท่าๆ กันมากขึ้นตั้งแต่ 1 ถึง 4 ไบต์ แต่อนิจจาตัวอักษรอื่นที่ไม่ใช่ภาษาละตินไม่ได้ประโยชน์ในทางใดทางหนึ่งเมื่อเทียบกับ UTF-16 และหลายตัวตอนนี้ต้องใช้สามไบต์แทนที่จะเป็นสอง - ช่วงที่ครอบคลุมโดยบันทึกสองไบต์นั้นแคบลง 32 เท่าด้วย 0xFFFF ไปยัง 0x7FFและทั้งภาษาจีนและจอร์เจียไม่รวมอยู่ในนั้น ซีริลลิกและตัวอักษรอีกห้าตัว - ไชโย - โชคดี 2 ไบต์ต่อตัวอักษร

ทำไมสิ่งนี้ถึงเกิดขึ้น? มาดูกันว่า UTF-8 แสดงถึงรหัสอักขระอย่างไร:

เพื่อแสดงตัวเลขโดยตรง จะใช้บิตที่มีสัญลักษณ์แทนที่นี่ x. จะเห็นได้ว่าในบันทึกแบบสองไบต์มีเพียง 11 บิตดังกล่าว (จาก 16 บิต) บิตนำหน้ามีเพียงฟังก์ชันเสริมเท่านั้น ในกรณีของบันทึกสี่ไบต์ 21 จาก 32 บิตจะถูกจัดสรรให้กับหมายเลขจุดโค้ด - ดูเหมือนว่า 24 ไบต์ (ซึ่งให้ทั้งหมด XNUMX บิต) จะเพียงพอ แต่เครื่องหมายบริการกินมากเกินไป

นี่มันแย่เหรอ? ไม่เชิง. ประการหนึ่ง ถ้าเราใส่ใจเรื่องพื้นที่เป็นอย่างมาก เราก็มีอัลกอริธึมการบีบอัดที่สามารถกำจัดเอนโทรปีและความซ้ำซ้อนส่วนเกินทั้งหมดได้อย่างง่ายดาย ในทางกลับกัน เป้าหมายของ Unicode คือการมอบการเข้ารหัสที่เป็นสากลมากที่สุดเท่าที่จะเป็นไปได้ ตัวอย่างเช่น เราสามารถไว้วางใจบรรทัดที่เข้ารหัสใน UTF-8 ให้กับโค้ดที่เคยใช้งานได้กับ ASCII เท่านั้น และไม่ต้องกลัวว่าจะเห็นอักขระจากช่วง ASCII ที่ไม่มีอยู่จริง (ท้ายที่สุดใน UTF-8 ทั้งหมด ไบต์ที่เริ่มต้นด้วยศูนย์บิต - นี่คือสิ่งที่ ASCII คืออะไร) และหากเราต้องการตัดหางเล็กๆ ออกจากสตริงขนาดใหญ่โดยไม่ได้ถอดรหัสตั้งแต่ต้น (หรือกู้คืนข้อมูลบางส่วนหลังจากส่วนที่เสียหาย) ก็เป็นเรื่องง่ายสำหรับเราที่จะค้นหาออฟเซ็ตที่อักขระเริ่มต้น (ก็เพียงพอแล้ว) เพื่อข้ามไบต์ที่มีคำนำหน้าบิต 10).

เหตุใดจึงต้องคิดค้นสิ่งใหม่ ๆ ?

ในเวลาเดียวกัน มีบางครั้งที่อัลกอริธึมการบีบอัด เช่น deflate ใช้งานได้ไม่ดี แต่คุณต้องการพื้นที่จัดเก็บสตริงที่มีขนาดกะทัดรัด โดยส่วนตัวแล้วผมประสบปัญหานี้เมื่อคิดจะสร้าง ต้นไม้คำนำหน้าที่ถูกบีบอัด สำหรับพจนานุกรมขนาดใหญ่ที่มีคำศัพท์เป็นภาษาต่างๆ ประการหนึ่งแต่ละคำสั้นมากดังนั้นการบีบอัดจึงไม่ได้ผล ในทางกลับกัน การใช้งานแผนผังที่ฉันพิจารณานั้นได้รับการออกแบบเพื่อให้แต่ละไบต์ของสตริงที่เก็บไว้สร้างจุดยอดของต้นไม้แยกกัน ดังนั้นการลดจำนวนให้เหลือน้อยที่สุดจึงมีประโยชน์มาก ในห้องสมุดของฉัน อัซ.เจส (เช่นใน ไพมอร์ฟีย์2ซึ่งเป็นพื้นฐาน) ปัญหาที่คล้ายกันสามารถแก้ไขได้ง่ายๆ - สตริงที่บรรจุไว้ ดอว์ก-dictionary เก็บไว้ในนั้น CP1251 เก่าดี. แต่ตามที่เข้าใจง่าย วิธีนี้ใช้ได้ผลดีกับตัวอักษรที่มีจำนวนจำกัดเท่านั้น ไม่สามารถเพิ่มบรรทัดในภาษาจีนลงในพจนานุกรมดังกล่าวได้

ฉันต้องการทราบความแตกต่างที่ไม่พึงประสงค์อีกประการหนึ่งที่เกิดขึ้นเมื่อใช้ UTF-8 ในโครงสร้างข้อมูลดังกล่าว รูปภาพด้านบนแสดงให้เห็นว่าเมื่ออักขระถูกเขียนเป็นสองไบต์ บิตที่เกี่ยวข้องกับหมายเลขนั้นจะไม่มาเรียงกัน แต่จะถูกคั่นด้วยบิตคู่หนึ่ง 10 ระหว่างกลาง: 110xxxxx 10xxxxxx. ด้วยเหตุนี้ เมื่อ 6 บิตล่างของไบต์ที่สองล้นในโค้ดอักขระ (เช่น การเปลี่ยนแปลงเกิดขึ้น 10111111 → 10000000) จากนั้นไบต์แรกก็จะเปลี่ยนไปเช่นกัน ปรากฎว่าตัวอักษร "p" แทนด้วยไบต์ 0xD0 0xBFและตัว “r” ถัดไปก็อยู่แล้ว 0xD1 0x80. ในแผนผังคำนำหน้า สิ่งนี้นำไปสู่การแยกโหนดหลักออกเป็นสองส่วน - หนึ่งรายการสำหรับคำนำหน้า 0xD0และอีกอันสำหรับ 0xD1 (แม้ว่าอักษรซีริลลิกทั้งหมดจะสามารถเข้ารหัสได้เพียงไบต์ที่สองเท่านั้น)

ฉันได้อะไร

เมื่อต้องเผชิญกับปัญหานี้ ฉันจึงตัดสินใจฝึกเล่นเกมด้วยบิต และในขณะเดียวกันก็ทำความคุ้นเคยกับโครงสร้างของ Unicode โดยรวมดีขึ้นเล็กน้อย ผลลัพธ์คือรูปแบบการเข้ารหัส UTF-C ("C" สำหรับ กะทัดรัด) ซึ่งใช้จ่ายไม่เกิน 3 ไบต์ต่อจุดโค้ด และบ่อยครั้งมากให้คุณใช้จ่ายเพียงเท่านั้น หนึ่งไบต์พิเศษสำหรับบรรทัดที่เข้ารหัสทั้งหมด. สิ่งนี้นำไปสู่ความจริงที่ว่าในตัวอักษรที่ไม่ใช่ ASCII จำนวนมากการเข้ารหัสดังกล่าวกลับกลายเป็นว่าเป็นเช่นนั้น กะทัดรัดกว่า UTF-30 ถึง 60-8%.

ฉันได้นำเสนอตัวอย่างการใช้งานอัลกอริทึมการเข้ารหัสและถอดรหัสในรูปแบบ ไลบรารี JavaScript และ Goคุณสามารถใช้พวกมันในโค้ดของคุณได้อย่างอิสระ แต่ฉันจะยังคงย้ำว่าในแง่หนึ่งรูปแบบนี้ยังคงเป็น "จักรยาน" และฉันไม่แนะนำให้ใช้มัน โดยไม่รู้ว่าทำไมคุณถึงต้องการมัน. นี่ยังคงเป็นการทดลองมากกว่า "การปรับปรุง UTF-8" อย่างจริงจัง อย่างไรก็ตามโค้ดในนั้นเขียนได้เรียบร้อย กระชับ มีความคิดเห็นและการทดสอบครอบคลุมมากมาย

ผลการทดสอบและการเปรียบเทียบกับ UTF-8

ฉันก็ทำเช่นกัน หน้าสาธิตซึ่งคุณสามารถประเมินประสิทธิภาพของอัลกอริทึมได้ จากนั้นฉันจะบอกคุณเพิ่มเติมเกี่ยวกับหลักการและกระบวนการพัฒนาของมัน

การกำจัดบิตที่ซ้ำซ้อน

แน่นอนว่าฉันใช้ UTF-8 เป็นพื้นฐาน สิ่งแรกและชัดเจนที่สุดที่สามารถเปลี่ยนแปลงได้คือการลดจำนวนบิตบริการในแต่ละไบต์ ตัวอย่างเช่น ไบต์แรกใน UTF-8 จะเริ่มต้นด้วยอย่างใดอย่างหนึ่งเสมอ 0หรือกับ 11 - คำนำหน้า 10 มีเพียงไบต์ต่อไปนี้เท่านั้นที่มี มาแทนที่คำนำหน้ากัน 11 บน 1และสำหรับไบต์ถัดไป เราจะลบคำนำหน้าออกทั้งหมด อะไรจะเกิดขึ้น?

0xxxxxxx — 1 ไบต์
10xxxxxx xxxxxxxx - 2 ไบต์
110xxxxx xxxxxxxx xxxxxxxx - 3 ไบต์

เดี๋ยวก่อน บันทึกสี่ไบต์อยู่ที่ไหน? แต่มันไม่จำเป็นอีกต่อไป - เมื่อเขียนเป็นสามไบต์ ตอนนี้เรามี 21 บิต ซึ่งเพียงพอสำหรับตัวเลขทั้งหมดจนถึง 0x10FFFF.

เราได้เสียสละอะไรที่นี่? สิ่งที่สำคัญที่สุดคือการตรวจหาขอบเขตอักขระจากตำแหน่งที่กำหนดเองในบัฟเฟอร์ เราไม่สามารถชี้ไปที่ไบต์ใดก็ได้และค้นหาจุดเริ่มต้นของอักขระถัดไปจากไบต์นั้น นี่เป็นข้อจำกัดของรูปแบบของเรา แต่ในทางปฏิบัตินี่แทบไม่จำเป็นเลย โดยปกติแล้วเราจะสามารถรันผ่านบัฟเฟอร์ได้ตั้งแต่เริ่มต้น (โดยเฉพาะเมื่อเป็นเรื่องของบรรทัดสั้นๆ)

สถานการณ์ที่ครอบคลุมภาษาที่มี 2 ไบต์ก็ดีขึ้นเช่นกัน: ตอนนี้รูปแบบสองไบต์ให้ช่วง 14 บิตและรหัสเหล่านี้สูงถึง 0x3FFF. คนจีนโชคไม่ดี (ตัวละครส่วนใหญ่มีตั้งแต่ 0x4E00 ไปยัง 0x9FFF) แต่ชาวจอร์เจียและชนชาติอื่น ๆ มีความสนุกสนานมากกว่า - ภาษาของพวกเขามีขนาด 2 ไบต์ต่ออักขระด้วย

ป้อนสถานะตัวเข้ารหัส

ทีนี้ลองคิดถึงคุณสมบัติของเส้นตรงกัน พจนานุกรมส่วนใหญ่มักประกอบด้วยคำที่เขียนด้วยตัวอักษรเดียวกัน และข้อความอื่นๆ อีกหลายคำก็เป็นเช่นนั้นเช่นกัน เป็นการดีที่จะระบุตัวอักษรนี้เพียงครั้งเดียวแล้วระบุเฉพาะจำนวนตัวอักษรที่อยู่ภายใน มาดูกันว่าการจัดเรียงอักขระในตาราง Unicode จะช่วยเราได้ไหม

ดังที่ได้กล่าวไปแล้ว Unicode แบ่งออกเป็น เครื่องบิน รหัสละ 65536 แต่นี่ไม่ใช่การหารที่มีประโยชน์มาก (อย่างที่บอกไปแล้ว ส่วนใหญ่เราอยู่ในระนาบศูนย์) สิ่งที่น่าสนใจกว่านั้นคือการหารด้วย บล็อก ช่วงเหล่านี้ไม่ได้มีความยาวคงที่อีกต่อไป และมีความหมายมากกว่า โดยตามกฎแล้ว แต่ละช่วงจะรวมอักขระจากตัวอักษรเดียวกัน

บล็อกที่ประกอบด้วยตัวอักษรเบงกาลี น่าเสียดาย ด้วยเหตุผลทางประวัติศาสตร์ นี่คือตัวอย่างของบรรจุภัณฑ์ที่มีความหนาแน่นไม่มาก - อักขระ 96 ตัวกระจัดกระจายอย่างวุ่นวายในจุดรหัสบล็อก 128 จุด

จุดเริ่มต้นของบล็อกและขนาดของบล็อกจะเป็นทวีคูณของ 16 เสมอ - ทำเพื่อความสะดวกเท่านั้น นอกจากนี้ บล็อกจำนวนมากเริ่มต้นและสิ้นสุดด้วยค่าที่เป็นทวีคูณของ 128 หรือ 256 เช่น ตัวอักษรซีริลลิกพื้นฐานใช้พื้นที่ 256 ไบต์จาก 0x0400 ไปยัง 0x04FF. วิธีนี้ค่อนข้างสะดวก: ถ้าเราบันทึกคำนำหน้าเพียงครั้งเดียว 0x04จากนั้นอักขระซีริลลิกใดๆ ก็สามารถเขียนได้ในหนึ่งไบต์ จริงอยู่ ด้วยวิธีนี้ เราจะสูญเสียโอกาสในการกลับไปใช้ ASCII (และอักขระอื่นๆ โดยทั่วไป) ดังนั้นเราจึงทำสิ่งนี้:

1. สองไบต์ 10yyyyyy yxxxxxxx ไม่เพียงแต่แสดงถึงสัญลักษณ์ที่มีตัวเลขเท่านั้น yyyyyy yxxxxxxxแต่ยังมีการเปลี่ยนแปลง ตัวอักษรปัจจุบัน บน yyyyyy y0000000 (เช่น เราจำบิตทั้งหมดได้ ยกเว้นบิตที่มีนัยสำคัญน้อยที่สุด 7 บิต);
2. หนึ่งไบต์ 0xxxxxxx นี่คือลักษณะของตัวอักษรปัจจุบัน เพียงแต่ต้องเพิ่มลงในออฟเซ็ตที่เราจำได้ในขั้นตอนที่ 1 แม้ว่าเราไม่ได้เปลี่ยนตัวอักษร แต่ออฟเซ็ตจะเป็นศูนย์ ดังนั้นเราจึงรักษาความเข้ากันได้กับ ASCII

ในทำนองเดียวกันสำหรับรหัสที่ต้องการ 3 ไบต์:

1. สามไบต์ 110yyyyy yxxxxxxx xxxxxxxx ระบุสัญลักษณ์ด้วยตัวเลข yyyyyy yxxxxxxx xxxxxxxx, เปลี่ยน ตัวอักษรปัจจุบัน บน yyyyyy y0000000 00000000 (จำได้ทุกอย่างยกเว้นน้อง. 15 บิต) และทำเครื่องหมายในช่องที่เราอยู่ในขณะนี้ ยาว โหมด (เมื่อเปลี่ยนตัวอักษรกลับเป็นไบต์คู่เราจะรีเซ็ตแฟล็กนี้)
2. สองไบต์ 0xxxxxxx xxxxxxxx ในโหมดยาวจะเป็นอักขระของตัวอักษรปัจจุบัน ในทำนองเดียวกัน เราเพิ่มมันด้วยออฟเซ็ตจากขั้นตอนที่ 1 ข้อแตกต่างเพียงอย่างเดียวคือตอนนี้เราอ่านได้ XNUMX ไบต์ (เพราะเราเปลี่ยนมาใช้โหมดนี้)

ฟังดูดี: แม้ว่าตอนนี้เราต้องเข้ารหัสอักขระจากช่วง Unicode 7 บิตเดียวกัน แต่เราใช้จ่ายเพิ่ม 1 ไบต์ที่จุดเริ่มต้น และรวมเป็น XNUMX ไบต์ต่ออักขระ

ทำงานจากเวอร์ชันก่อนหน้าอันใดอันหนึ่ง มันมักจะเอาชนะ UTF-8 อยู่แล้ว แต่ยังมีช่องว่างให้ปรับปรุง

มีอะไรแย่กว่านั้น? ประการแรก เรามีเงื่อนไข กล่าวคือ ออฟเซ็ตตัวอักษรปัจจุบัน และช่องทำเครื่องหมาย โหมดยาว. สิ่งนี้จำกัดเราเพิ่มเติม: ขณะนี้อักขระเดียวกันสามารถเข้ารหัสแตกต่างกันในบริบทที่ต่างกันได้ ตัวอย่างเช่น การค้นหาสตริงย่อยจะต้องกระทำโดยคำนึงถึงสิ่งนี้ ไม่ใช่เพียงการเปรียบเทียบไบต์เท่านั้น ประการที่สอง ทันทีที่เราเปลี่ยนตัวอักษร การเข้ารหัสอักขระ ASCII ก็กลายเป็นเรื่องไม่ดี (และนี่ไม่ใช่แค่ตัวอักษรละตินเท่านั้น แต่ยังรวมถึงเครื่องหมายวรรคตอนพื้นฐานรวมถึงการเว้นวรรคด้วย) - พวกเขาต้องการเปลี่ยนตัวอักษรอีกครั้งเป็น 0 นั่นคือ อีกหนึ่งไบต์เพิ่มเติม (และอีกไบต์หนึ่งเพื่อกลับไปยังจุดหลักของเรา)

ตัวอักษรหนึ่งตัวดี สองอักษรดีกว่า

ลองเปลี่ยนคำนำหน้าบิตของเราสักหน่อย โดยบีบเข้าไปอีก XNUMX ถึง XNUMX คำที่อธิบายไว้ข้างต้น:

0xxxxxxx — 1 ไบต์ในโหมดปกติ, 2 ไบต์ในโหมดยาว
11xxxxxx — 1 ไบต์
100xxxxx xxxxxxxx - 2 ไบต์
101xxxxx xxxxxxxx xxxxxxxx - 3 ไบต์

ขณะนี้ในเร็กคอร์ดแบบสองไบต์จะมีบิตโค้ดที่พร้อมใช้งานน้อยกว่าหนึ่งตัวที่ชี้ขึ้นไป 0x1FFFและไม่ 0x3FFF. อย่างไรก็ตาม มันยังคงใหญ่กว่าโค้ด UTF-8 แบบไบต์คู่อย่างเห็นได้ชัด ภาษาทั่วไปส่วนใหญ่ยังคงพอดี การสูญเสียที่เห็นได้ชัดเจนที่สุดก็หลุดออกไป ฮิระงะนะ и คาตาคานะชาวญี่ปุ่นเศร้าใจ

รหัสใหม่นี้คืออะไร? 11xxxxxx? นี่คือ "คลัง" ขนาดเล็กที่มีอักขระ 64 ตัว ซึ่งมาเติมเต็มตัวอักษรหลักของเรา ดังนั้นฉันจึงเรียกมันว่าตัวช่วย (ผู้ช่วย) ตัวอักษร เมื่อเราสลับตัวอักษรปัจจุบัน ชิ้นส่วนของตัวอักษรเก่าจะกลายเป็นตัวอักษรเสริม ตัวอย่างเช่น เราเปลี่ยนจาก ASCII เป็น Cyrillic - ตอนนี้ที่ซ่อนมีอักขระ 64 ตัว ตัวอักษรละติน ตัวเลข ช่องว่าง และลูกน้ำ (การแทรกบ่อยที่สุดในข้อความที่ไม่ใช่ ASCII) เปลี่ยนกลับเป็น ASCII - และส่วนหลักของอักษรซีริลลิกจะกลายเป็นตัวอักษรเสริม

ด้วยการเข้าถึงตัวอักษรสองตัว เราจึงสามารถจัดการกับข้อความจำนวนมากโดยมีค่าใช้จ่ายน้อยที่สุดในการสลับตัวอักษร (เครื่องหมายวรรคตอนส่วนใหญ่มักจะทำให้กลับไปเป็น ASCII แต่หลังจากนั้น เราจะได้อักขระที่ไม่ใช่ ASCII จำนวนมากจากตัวอักษรเพิ่มเติม โดยไม่มี สลับอีกครั้ง)

โบนัส: นำหน้าตัวอักษรย่อย 11xxxxxx และเลือกออฟเซ็ตเริ่มต้นให้เป็น 0xC0เราได้รับความเข้ากันได้บางส่วนกับ CP1252 กล่าวอีกนัยหนึ่ง ข้อความยุโรปตะวันตกจำนวนมาก (แต่ไม่ใช่ทั้งหมด) ที่เข้ารหัสใน CP1252 จะมีลักษณะเหมือนกันใน UTF-C

อย่างไรก็ตามมีปัญหาเกิดขึ้นที่นี่: จะรับตัวเสริมจากตัวอักษรหลักได้อย่างไร? คุณสามารถคงออฟเซ็ตเดิมไว้ได้ แต่ - อนิจจา - โครงสร้าง Unicode กำลังเล่นกับเราอยู่แล้ว บ่อยครั้งที่ส่วนหลักของตัวอักษรไม่ได้อยู่ที่จุดเริ่มต้นของบล็อก (เช่น อักษรตัวใหญ่ของรัสเซีย "A" มีรหัส 0x0410แม้ว่าบล็อกซีริลลิกจะเริ่มต้นด้วยก็ตาม 0x0400). ดังนั้นเมื่อนำอักขระ 64 ตัวแรกไปซ่อนแล้ว เราอาจสูญเสียการเข้าถึงส่วนท้ายของตัวอักษร

เพื่อแก้ไขปัญหานี้ ฉันได้ดำเนินการผ่านบางบล็อกที่เกี่ยวข้องกับภาษาต่าง ๆ ด้วยตนเอง และระบุการชดเชยของตัวอักษรเสริมภายในบล็อกหลักสำหรับบล็อกเหล่านั้น โดยทั่วไปแล้ว ตัวอักษรละตินจะเรียงลำดับใหม่เหมือน base64

สัมผัสสุดท้าย

สุดท้ายเราลองคิดว่าเราจะปรับปรุงอะไรได้อีกบ้าง

โปรดทราบว่ารูปแบบ 101xxxxx xxxxxxxx xxxxxxxx ให้คุณเข้ารหัสตัวเลขได้สูงสุด 0x1FFFFFและ Unicode สิ้นสุดเร็วกว่านี้ที่ 0x10FFFF. กล่าวอีกนัยหนึ่ง จุดโค้ดสุดท้ายจะแสดงเป็น 10110000 11111111 11111111. ดังนั้นเราสามารถพูดได้ว่าถ้าไบต์แรกอยู่ในรูปแบบ 1011xxxx (ที่ไหน xxxx มากกว่า 0) หมายความว่าอย่างอื่น ตัวอย่างเช่นคุณสามารถเพิ่มอักขระอีก 15 ตัวที่นั่นซึ่งพร้อมสำหรับการเข้ารหัสในหนึ่งไบต์ตลอดเวลา แต่ฉันตัดสินใจที่จะทำแตกต่างออกไป

ลองดูที่บล็อก Unicode ที่ต้องใช้สามไบต์ตอนนี้ โดยพื้นฐานแล้วดังที่กล่าวไปแล้วเหล่านี้เป็นตัวอักษรจีน - แต่เป็นการยากที่จะทำอะไรกับพวกมันมี 21 ตัว แต่ฮิระงะนะและคาตาคานะก็บินไปที่นั่นด้วย - และมีจำนวนไม่มากอีกต่อไปน้อยกว่าสองร้อยตัว และเนื่องจากเราจำภาษาญี่ปุ่นได้ จึงมีอิโมจิด้วย (อันที่จริงพวกมันกระจัดกระจายอยู่ในหลาย ๆ ที่ใน Unicode แต่บล็อกหลักอยู่ในช่วง 0x1F300 - 0x1FBFF). หากลองนึกถึงความจริงที่ว่าตอนนี้มีอิโมจิที่รวบรวมจากจุดโค้ดหลายจุดพร้อมกัน (เช่น อิโมจิ ‍‍‍ ประกอบด้วยรหัสมากถึง 7 รหัส!) ดังนั้นจึงเป็นเรื่องน่าเสียดายอย่างยิ่งที่ต้องใช้สามไบต์ในแต่ละรหัส (7 × 3 = 21 ไบต์เพื่อเห็นแก่ไอคอนเดียวซึ่งเป็นฝันร้าย)

ดังนั้นเราจึงเลือกช่วงที่เลือกไว้สองสามช่วงซึ่งสอดคล้องกับอิโมจิ ฮิระงะนะ และคาตาคานะ จากนั้นจัดหมายเลขใหม่เป็นรายการต่อเนื่องรายการเดียว และเข้ารหัสเป็นสองไบต์แทนที่จะเป็นสาม:

1011xxxx xxxxxxxx

เยี่ยมมาก: อีโมจิ ‍‍‍ ที่กล่าวมาข้างต้นประกอบด้วยจุดโค้ด 7 จุด ใช้เวลา 8 ไบต์ใน UTF-25 และเราก็ปรับให้พอดี 14 (สองไบต์สำหรับแต่ละจุดโค้ด) อย่างไรก็ตาม Habr ปฏิเสธที่จะแยกแยะมัน (ทั้งในตัวแก้ไขแบบเก่าและในตัวแก้ไขใหม่) ดังนั้นฉันจึงต้องแทรกรูปภาพลงไป

ลองแก้ไขปัญหาอีกข้อหนึ่ง ดังที่เราจำได้ว่าตัวอักษรพื้นฐานนั้นโดยพื้นฐานแล้ว สูง 6 บิตซึ่งเราจำไว้และยึดติดกับโค้ดของสัญลักษณ์ที่ถอดรหัสถัดไป ในกรณีตัวอักษรจีนที่อยู่ในบล็อก 0x4E00 - 0x9FFFนี่คือบิต 0 หรือ 1 ซึ่งไม่สะดวกนัก: เราจะต้องสลับตัวอักษรระหว่างสองค่านี้อย่างต่อเนื่อง (เช่น ใช้จ่ายสามไบต์) แต่โปรดทราบว่าในโหมดยาวจากโค้ดนั้นเราสามารถลบจำนวนอักขระที่เราเข้ารหัสโดยใช้โหมดสั้น (หลังจากเทคนิคทั้งหมดที่อธิบายไว้ข้างต้นนี่คือ 10240) - จากนั้นช่วงของอักษรอียิปต์โบราณจะเปลี่ยนเป็น 0x2600 - 0x77FFและในกรณีนี้ ตลอดช่วงทั้งหมดนี้ 6 บิตที่สำคัญที่สุด (จาก 21) จะเท่ากับ 0 ดังนั้นลำดับของอักษรอียิปต์โบราณจะใช้สองไบต์ต่ออักษรอียิปต์โบราณ (ซึ่งเหมาะสมที่สุดสำหรับช่วงขนาดใหญ่ดังกล่าว) โดยไม่มี ทำให้เกิดการสลับตัวอักษร

ทางเลือกอื่น: SCSU, BOCU-1

ผู้เชี่ยวชาญ Unicode ที่เพิ่งอ่านชื่อบทความมักจะรีบเตือนคุณว่าในบรรดามาตรฐาน Unicode นั้นโดยตรง รูปแบบการบีบอัดมาตรฐานสำหรับ Unicode (SCSU) ซึ่งอธิบายวิธีการเข้ารหัสคล้ายกับที่อธิบายไว้ในบทความมาก

ฉันยอมรับอย่างตรงไปตรงมา: ฉันได้เรียนรู้เกี่ยวกับการมีอยู่ของมันหลังจากที่ฉันจมอยู่กับการเขียนการตัดสินใจเท่านั้น ถ้าฉันรู้เรื่องนี้ตั้งแต่เริ่มต้น ฉันคงจะพยายามเขียนการนำไปปฏิบัติแทนที่จะคิดแนวทางของตัวเองขึ้นมา

สิ่งที่น่าสนใจคือ SCSU ใช้แนวคิดที่คล้ายคลึงกับที่ฉันคิดขึ้นมาเองมาก (แทนที่จะใช้แนวคิดเรื่อง "ตัวอักษร" พวกเขาใช้ "หน้าต่าง" และมีแนวคิดให้เลือกมากกว่าที่ฉันมี) ในขณะเดียวกันรูปแบบนี้ก็มีข้อเสียเช่นกัน: มันใกล้กับอัลกอริธึมการบีบอัดมากกว่าการเข้ารหัสเล็กน้อย โดยเฉพาะอย่างยิ่ง มาตรฐานให้วิธีการแสดงหลายวิธี แต่ไม่ได้ระบุวิธีการเลือกวิธีที่เหมาะสมที่สุด - สำหรับสิ่งนี้ ตัวเข้ารหัสจะต้องใช้การวิเคราะห์พฤติกรรมบางประเภท ดังนั้นตัวเข้ารหัส SCSU ที่ผลิตบรรจุภัณฑ์ที่ดีจะซับซ้อนและยุ่งยากกว่าอัลกอริทึมของฉัน

สำหรับการเปรียบเทียบ ฉันถ่ายโอนการใช้งาน SCSU ที่ค่อนข้างง่ายไปยัง JavaScript - ในแง่ของปริมาณโค้ดมันเทียบได้กับ UTF-C ของฉัน แต่ในบางกรณีผลลัพธ์ก็แย่กว่าสิบเปอร์เซ็นต์ (บางครั้งอาจเกินนั้น แต่ ไม่มาก) ตัวอย่างเช่น ข้อความในภาษาฮีบรูและกรีกถูกเข้ารหัสโดย UTF-C ดีกว่า SCSU 60% (อาจเป็นเพราะตัวอักษรกะทัดรัด)

ฉันจะเพิ่มแยกกันว่านอกเหนือจาก SCSU แล้ว ยังมีอีกวิธีหนึ่งในการแสดง Unicode แบบกะทัดรัด - โบซียู-1แต่มีจุดมุ่งหมายเพื่อความเข้ากันได้ของ MIME (ซึ่งฉันไม่ต้องการ) และใช้วิธีการเข้ารหัสที่แตกต่างออกไปเล็กน้อย ฉันยังไม่ได้ประเมินประสิทธิภาพของมัน แต่สำหรับฉันแล้วดูเหมือนว่าไม่น่าจะสูงกว่า SCSU

การปรับปรุงที่เป็นไปได้

อัลกอริทึมที่ฉันนำเสนอไม่ได้เป็นแบบสากลโดยการออกแบบ (นี่อาจเป็นจุดที่เป้าหมายของฉันแตกต่างจากเป้าหมายของ Unicode Consortium มากที่สุด) ฉันได้กล่าวไปแล้วว่ามันได้รับการพัฒนาสำหรับงานเดียวเป็นหลัก (การจัดเก็บพจนานุกรมหลายภาษาในแผนผังคำนำหน้า) และคุณสมบัติบางอย่างอาจไม่เหมาะสมกับงานอื่น ๆ แต่ความจริงที่ว่ามันไม่ใช่มาตรฐานอาจเป็นข้อดีได้ - คุณสามารถปรับเปลี่ยนให้เหมาะกับความต้องการของคุณได้อย่างง่ายดาย.

ตัวอย่างเช่น ในทางที่ชัดเจน คุณสามารถกำจัดการมีอยู่ของสถานะ ทำการเข้ารหัสแบบไร้สัญชาติ - แค่อย่าอัปเดตตัวแปร offs, auxOffs и is21Bit ในตัวเข้ารหัสและตัวถอดรหัส ในกรณีนี้ จะไม่สามารถบรรจุลำดับอักขระที่มีตัวอักษรเดียวกันได้อย่างมีประสิทธิภาพ แต่จะมีการรับประกันว่าอักขระเดียวกันนั้นจะถูกเข้ารหัสด้วยไบต์เดียวกันเสมอ โดยไม่คำนึงถึงบริบท

นอกจากนี้ คุณสามารถปรับแต่งตัวเข้ารหัสเป็นภาษาที่ต้องการได้โดยการเปลี่ยนสถานะเริ่มต้น - ตัวอย่างเช่น เน้นที่ข้อความภาษารัสเซีย ตั้งค่าตัวเข้ารหัสและตัวถอดรหัสที่จุดเริ่มต้น offs = 0x0400 и auxOffs = 0. สิ่งนี้สมเหตุสมผลอย่างยิ่งในกรณีของโหมดไร้สัญชาติ โดยทั่วไปจะคล้ายกับการใช้การเข้ารหัสแบบ XNUMX บิตแบบเก่า แต่จะไม่มีการถอดความสามารถในการแทรกอักขระจาก Unicode ทั้งหมดตามต้องการ

ข้อเสียเปรียบอีกประการหนึ่งที่กล่าวถึงก่อนหน้านี้คือในข้อความขนาดใหญ่ที่เข้ารหัสใน UTF-C ไม่มีวิธีที่รวดเร็วในการค้นหาขอบเขตอักขระที่ใกล้เคียงกับไบต์ที่กำหนดเองมากที่สุด หากคุณตัดส่วนสุดท้าย เช่น 100 ไบต์ออกจากบัฟเฟอร์ที่เข้ารหัส คุณอาจเสี่ยงต่อการได้รับขยะที่คุณไม่สามารถทำอะไรกับมันได้ การเข้ารหัสไม่ได้ออกแบบมาเพื่อจัดเก็บบันทึกหลายกิกะไบต์ แต่โดยทั่วไปสามารถแก้ไขได้ ไบต์ 0xBF ต้องไม่ปรากฏเป็นไบต์แรก (แต่อาจเป็นไบต์ที่สองหรือสาม) ดังนั้นเมื่อเข้ารหัส คุณสามารถแทรกลำดับได้ 0xBF 0xBF 0xBF ทุกๆ เช่น 10 KB - จากนั้น หากคุณต้องการค้นหาขอบเขต ก็เพียงพอแล้วที่จะสแกนชิ้นส่วนที่เลือกจนกว่าจะพบเครื่องหมายที่คล้ายกัน ต่อจากอันสุดท้าย 0xBF รับรองว่าเป็นจุดเริ่มต้นของตัวละคร (เมื่อถอดรหัส แน่นอนว่าจะต้องละเว้นลำดับสามไบต์นี้)

ข้อสรุปถึง

หากคุณอ่านมาไกลขนาดนี้ ยินดีด้วย! ฉันหวังว่าคุณจะได้เรียนรู้สิ่งใหม่ ๆ (หรือรีเฟรชความทรงจำของคุณ) เช่นเดียวกับฉันเกี่ยวกับโครงสร้างของ Unicode

หน้าสาธิต ตัวอย่างภาษาฮิบรูแสดงให้เห็นถึงข้อดีเหนือทั้ง UTF-8 และ SCSU

การวิจัยที่อธิบายไว้ข้างต้นไม่ควรถือเป็นการรุกล้ำมาตรฐาน อย่างไรก็ตาม โดยทั่วไปแล้วฉันพอใจกับผลงานของตัวเอง ดังนั้นฉันจึงพอใจกับผลงานเหล่านั้น หุ้น: ตัวอย่างเช่น ไลบรารี JS ที่ย่อขนาดมีน้ำหนักเพียง 1710 ไบต์ (และแน่นอนว่าไม่มีการขึ้นต่อกัน) ดังที่ได้กล่าวไปแล้วสามารถติดตามผลงานของเธอได้ที่ หน้าสาธิต (ยังมีชุดข้อความที่สามารถเปรียบเทียบกับ UTF-8 และ SCSU ได้)

สุดท้ายนี้ ฉันจะดึงความสนใจอีกครั้งไปยังกรณีที่ใช้ UTF-C ไม่คุ้มค่า:

• หากบรรทัดของคุณยาวพอ (ตั้งแต่ 100-200 ตัวอักษร) ในกรณีนี้ คุณควรคำนึงถึงการใช้อัลกอริธึมการบีบอัด เช่น การยุบตัว
• ถ้าคุณต้องการ ความโปร่งใสของ ASCIIนั่นคือ เป็นสิ่งสำคัญสำหรับคุณที่ลำดับที่เข้ารหัสไม่มีรหัส ASCII ที่ไม่ได้อยู่ในสตริงดั้งเดิม ความจำเป็นในการดำเนินการนี้สามารถหลีกเลี่ยงได้ หากเมื่อโต้ตอบกับ API ของบริษัทอื่น (เช่น ทำงานกับฐานข้อมูล) คุณส่งผลการเข้ารหัสเป็นชุดไบต์นามธรรม และไม่ใช่สตริง มิฉะนั้นคุณอาจเสี่ยงต่อการเกิดช่องโหว่ที่ไม่คาดคิด
• หากคุณต้องการค้นหาขอบเขตอักขระอย่างรวดเร็วโดยใช้ออฟเซ็ตที่กำหนดเอง (เช่น เมื่อส่วนหนึ่งของบรรทัดเสียหาย) ซึ่งสามารถทำได้โดยการสแกนบรรทัดจากจุดเริ่มต้นเท่านั้น (หรือใช้การแก้ไขที่อธิบายไว้ในส่วนก่อนหน้า)
• หากคุณต้องการดำเนินการกับเนื้อหาของสตริงอย่างรวดเร็ว (จัดเรียงค้นหาสตริงย่อยในนั้นต่อกัน) ซึ่งจำเป็นต้องถอดรหัสสตริงก่อน ดังนั้น UTF-C จะช้ากว่า UTF-8 ในกรณีเหล่านี้ (แต่เร็วกว่าอัลกอริธึมการบีบอัด) เนื่องจากสตริงเดียวกันจะถูกเข้ารหัสด้วยวิธีเดียวกันเสมอ จึงไม่จำเป็นต้องมีการเปรียบเทียบการถอดรหัสที่แน่นอน และสามารถทำได้แบบไบต์ต่อไบต์

ปรับปรุง: ผู้ใช้งาน ไทโยมิทช์ ในความคิดเห็นด้านล่าง โพสต์กราฟที่เน้นขีด จำกัด การบังคับใช้ของ UTF-C มันแสดงให้เห็นว่า UTF-C มีประสิทธิภาพมากกว่าอัลกอริธึมการบีบอัดทั่วไป (รูปแบบของ LZW) ตราบใดที่สตริงที่แพ็กสั้นกว่า ~140 ตัวอักษร (อย่างไรก็ตามฉันทราบว่ามีการเปรียบเทียบในข้อความเดียวสำหรับภาษาอื่นผลลัพธ์อาจแตกต่างกัน)


ที่มา: will.com