Temu duga pengekodan: Mengesahkan jujukan bait UTF-8

Gesaan dan skop

Ini ialah masalah manipulasi bit dan pengekodan aksara. Inputnya ialah tatasusunan bait, bukan rentetan Unicode yang telah dinyahkod. Tentukan sama ada setiap skalar menggunakan 1 hingga 4 bait dan tolak jujukan yang terpotong atau tidak terbentuk dengan betul (malformed). LeetCode 393 menggunakan kekangan yang sama: panjang paling banyak 2 * 10^4, dengan setiap integer menyumbang 8 bit terendahnya. RFC 3629 mentakrifkan bentuk UTF-8 1–4 bait dan julat nilai skalar yang sah.

Perkara yang diuji oleh penemu duga

Menerbitkan bilangan lanjutan daripada corak bait pendahulu (leading byte).
Menyemak awalan lanjutan 10xxxxxx secara ketat.
Menolak bait lanjutan berlebihan, pemotongan dan corak pendahulu lima bait.
Menghasilkan penyelesaian satu laluan dengan masa O(n) dan ruang tambahan O(1).

Penjelasan yang perlu ditanya terlebih dahulu

Sahkan sama ada setiap elemen dijamin berada dalam 0..255; jika tidak, tolak nilai di luar julat terlebih dahulu. Jelaskan juga sama ada tugasan ini hanya menyemak bentuk bait atau mesti menolak pengekodan terlebih panjang (overlong encodings), titik kod surigat (surrogate code points) dan nilai melebihi U+10FFFF. Versi LeetCode memfokuskan pada bentuk bait; penghurai tahap pengeluaran harus menggunakan peraturan nilai skalar RFC 3629 yang lebih ketat.

Jawapan 30 saat

Kekalkan remaining, iaitu bilangan bait lanjutan yang masih diperlukan untuk aksara semasa. Untuk bait pendahulu, gunakan corak bit tingginya untuk menetapkan 0, 1, 2 atau 3; untuk bait lanjutan, wajibkan (byte & 0b11000000) === 0b10000000 dan kurangkan pembilang. Tolak pendahulu yang tidak sah, lanjutan yang tidak dijangka atau akhir input dengan remaining !== 0. Imbasan hanya menyimpan pembilang ini.

Penyelesaian langkah demi langkah

1. Mengenali corak bait pendahulu

0xxxxxxx ialah aksara satu bait; 110xxxxx, 1110xxxx dan 11110xxx memerlukan 1, 2 dan 3 bait lanjutan. Uji awalan dengan topeng: semak 0x80, kemudian 0xE0, 0xF0 dan akhir sekali 0xF8. Jika ujian 0xF8 masih bukan sifar, bait tersebut memulakan bentuk lima bait atau lebih panjang dan mesti ditolak.

2. Mengesahkan bait lanjutan secara dalam talian

Apabila remaining > 0, bait semasa mesti sepadan dengan 10xxxxxx. Kurangkan pembilang selepas semakan yang berjaya. Bait pendahulu ASCII atau bait pendahulu pelbagai bait lain dalam keadaan ini adalah tidak sah serta-merta. Tiada penjejakan ke belakang (backtracking) atau pemotongan (slicing) diperlukan, dan pemotongan dikesan apabila input tamat.

3. Pelaksanaan rujukan

text

isValidUtf8(bytes):
  remaining = 0
  for byte in bytes:
    if byte < 0 or byte > 255: return false
    if remaining > 0:
      if (byte & 0b11000000) != 0b10000000: return false
      remaining -= 1
      continue
    if (byte & 0b10000000) == 0:
      remaining = 0
    else if (byte & 0b11100000) == 0b11000000:
      remaining = 1
    else if (byte & 0b11110000) == 0b11100000:
      remaining = 2
    else if (byte & 0b11111000) == 0b11110000:
      remaining = 3
    else:
      return false
  return remaining == 0

4. Ketegasan tahap pengeluaran

Pengiraan awalan sahaja menerima beberapa pengekodan terlebih panjang, seperti mewakili nilai dengan tiga bait sedangkan satu bait sudah mencukupi, dan mungkin menerima nilai surigat. Penghurai pengeluaran harus mengumpulkan nilai skalar dan menyemak nilai minimum untuk panjangnya, julat surigat dan siling U+10FFFF; tentukan secara eksplisit sama ada BOM dibenarkan. Nyatakan sempadan latihan terlebih dahulu, kemudian terangkan lanjutan ini daripada mencampurkan peraturan secara senyap.

5. Ujian dan kekompleksan

Liputi [197,130,1] sebagai benar, [235,140,4] sebagai palsu, lanjutan terpencil [128], [226,130] yang terpotong, pendahulu lima bait [248,128,128,128,128] dan tatasusunan kosong. Setiap bait diimbas sekali: masa O(n) dan ruang tambahan O(1), dengan n ialah panjang tatasusunan.

Jawapan model

Saya mengasingkan pengiktirafan bait pendahulu daripada pengesahan bait lanjutan. Pendahulu yang sepadan dengan 0xxxxxxx, 110xxxxx, 1110xxxx atau 11110xxx menetapkan remaining kepada 0, 1, 2 atau 3; keadaan lanjutan hanya menerima 10xxxxxx dan mengurangkan pembilang. Pendahulu lima bait, lanjutan yang tidak dijangka, elemen di luar julat atau akhir input dengan aksara yang tidak lengkap mengembalikan palsu. Pelaksanaannya ialah satu laluan O(n) dengan ruang O(1). Untuk pengeluaran, kumpulkan nilai skalar untuk menolak pengekodan terlebih panjang, surigat dan nilai melebihi U+10FFFF.

Kesilapan biasa

Mengira bait lanjutan tanpa menyemak setiap awalan 10.
Menganggap 111110xx sebagai bentuk lima bait yang sah.
Terlupa semakan akhir remaining dan menerima pemotongan.
Mewakilkan tugas kepada penyahkod bahasa tanpa menunjukkan tak varian (invariant) peringkat bit atau indeks ralat.
Mencampurkan semakan bentuk LeetCode dengan peraturan nilai skalar RFC tanpa menyatakan skopnya.
Menganggap byte sebagai bertanda (signed) dan gagal menormalkannya kepada 0..255 sebelum operasi bit.

Soalan susulan

Bagaimanakah anda akan mengembalikan indeks ralat pertama?

Kembalikan {valid, errorIndex, reason}. Catatkan indeks semasa apabila semakan pendahulu, lanjutan atau akhir input gagal. Keadaan imbasan kekal tidak berubah, jadi pemanggil boleh menyerlahkan bait asal.

Bagaimanakah anda akan menyokong input penstriman berketul (chunked streaming)?

Kekalkan remaining dan keadaan skalar separa dalam objek penghurai antara ketulan (chunks). Sesuatu aksara hanya selesai selepas ketulan kemudian membekalkan semua bait lanjutan; akhir strim dengan remaining != 0 masih merupakan ralat pemotongan.

Mengapa tidak menggunakan ungkapan nalar (regular expression) sahaja?

Ungkapan nalar boleh menyatakan beberapa peraturan awalan, tetapi mesin keadaan (state machine) lebih jelas untuk sempadan ketulan, indeks ralat dan kekangan nilai skalar. Pembilang menggunakan ruang malar untuk input yang panjangnya sewenang-wenangnya dan diperluas secara semula jadi kepada pengesahan yang ketat.

Bagaimanakah anda menolak pengekodan terlebih panjang?

Catatkan panjang jujukan dan nilai terkumpul daripada pendahulu, kemudian syaratkan nilai tersebut memenuhi julat minimum panjang tersebut. Tolak juga 0xD800..0xDFFF dan nilai melebihi 0x10FFFF.

Bagaimanakah anda mengendalikan input bersaiz terlalu besar yang berniat jahat?

Biarkan pemanggil menetapkan had bait, had masa tamat (timeout) dan dasar pensampelan ralat. Penghurai itu sendiri mengekalkan keadaan O(1) dan membuat litar pintas pada ralat pasti yang pertama, jadi input yang tidak sah tidak memerlukan penimbal tambahan.