Làm cách nào để đảo ngược chuỗi UTF-8 tại chỗ?

Question

Gần đây, có người hỏi về số algorithm for reversing a string in place in C. Hầu hết các giải pháp được đề xuất đều gặp sự cố khi xử lý các chuỗi không phải byte đơn. Vì vậy, tôi đã tự hỏi những gì có thể là một thuật toán tốt để đối phó cụ thể với các chuỗi utf-8.

Tôi đã đưa ra một số mã mà tôi đăng tải dưới dạng câu trả lời nhưng tôi rất vui khi thấy ý tưởng hoặc đề xuất của người khác. Tôi thích sử dụng mã thực, vì vậy tôi đã chọn C#, vì nó có vẻ là một trong những ngôn ngữ phổ biến nhất trong trang web này, nhưng tôi không ngại nếu mã của bạn có ngôn ngữ khác, miễn là nó có thể hợp lý được hiểu bởi bất kỳ ai quen thuộc với ngôn ngữ bắt buộc. Và, vì điều này được dự định để xem làm thế nào một thuật toán có thể được thực hiện ở mức độ thấp (bởi mức độ thấp, tôi chỉ có nghĩa là giao dịch với byte), ý tưởng là để tránh sử dụng thư viện cho mã lõi.

Ghi chú:

Tôi quan tâm đến các thuật toán riêng của mình, hiệu quả của nó và làm thế nào nó có thể được tối ưu hóa (Tôi có nghĩa là tối ưu hóa thuật toán cấp, chứ không phải thay thế i ++ với ++ i và đó; Tôi cũng không thực sự quan tâm đến điểm chuẩn thực tế).

Tôi không có ý định sử dụng nó trong mã sản xuất hoặc "phát minh lại bánh xe". Đây chỉ là sự tò mò và tập thể dục.

Tôi đang sử dụng mảng C# byte vì vậy tôi giả sử bạn có thể nhận được độ dài của chuỗi mà không cần chạy mặc dù chuỗi cho đến khi bạn tìm thấy NUL. Tức là, tôi không tính toán độ phức tạp của việc tìm độ dài của chuỗi. Nhưng nếu bạn đang sử dụng C, ví dụ, bạn có thể yếu tố đó bằng cách sử dụng strlen() trước khi gọi mã lõi.

Edit:

Như Mike F chỉ ra, mã của tôi (và mã số của người khác được đăng ở đây) không được đối phó với các nhân vật composite. Một số thông tin về những số here. Tôi không quen với khái niệm này, nhưng nếu điều đó có nghĩa là có "các ký tự kết hợp", nghĩa là các ký tự/điểm mã chỉ hợp lệ với các ký tự/điểm mã "cơ sở" khác, bảng tra cứu của ký tự có thể được sử dụng để bảo vệ thứ tự của ký tự "toàn cầu" ("cơ sở" + "kết hợp" ký tự) khi đảo ngược.

Answer 1

Tôi muốn thực hiện một lần đảo ngược các byte, sau đó một lần vượt qua thứ hai để đảo ngược các byte trong bất kỳ ký tự nhiều byte nào (được dễ dàng phát hiện trong UTF8) về đúng thứ tự của chúng.

Bạn chắc chắn có thể xử lý điều này trong một dòng, nhưng tôi sẽ không bận tâm trừ khi thói quen trở thành một nút cổ chai.

Answer 2

cách tiếp cận ban đầu của tôi có thể tóm tắt bằng cách này:

1) byte Xếp ngây thơ

2) Chạy chuỗi ngược và sửa chữa các chuỗi utf8 như bạn đi.

Trình tự bất hợp pháp được xử lý ở bước thứ hai và trong bước đầu tiên, chúng tôi kiểm tra xem chuỗi có đang được "đồng bộ hóa" hay không (nghĩa là, nếu bắt đầu bằng byte hàng đầu hợp pháp).

EDIT: cải thiện xác nhận cho byte hàng đầu trong Reverse()

class UTF8Utils { 


    public static void Reverse(byte[] str) { 
     int len = str.Length; 
     int i = 0; 
     int j = len - 1; 

     // first, check if the string is "synced", i.e., it starts 
     // with a valid leading character. Will check for illegal 
     // sequences thru the whole string later. 
     byte leadChar = str[0]; 

     // if it starts with 10xx xxx, it's a trailing char... 
     // if it starts with 1111 10xx or 1111 110x 
     // it's out of the 4 bytes range. 
    // EDIT: added validation for 7 bytes seq and 0xff 
     if((leadChar & 0xc0) == 0x80 || 
      (leadChar & 0xfc) == 0xf8 || 
      (leadChar & 0xfe) == 0xfc || 
     (leadChar & 0xff) == 0xfe || 
     leadChar == 0xff) { 

      throw new Exception("Illegal UTF-8 sequence"); 

     } 

     // reverse bytes in-place naïvely 
     while(i < j) { 
      byte tmp = str[i]; 
      str[i] = str[j]; 
      str[j] = tmp; 
      i++; 
      j--; 
     } 
     // now, run the string again to fix the multibyte sequences 
     UTF8Utils.ReverseMbSequences(str); 

    } 

    private static void ReverseMbSequences(byte[] str) { 
     int i = str.Length - 1; 
     byte leadChar = 0; 
     int nBytes = 0; 

     // loop backwards thru the reversed buffer 
     while(i >= 0) { 
      // since the first byte in the unreversed buffer is assumed to be 
      // the leading char of that byte, it seems safe to assume that the 
      // last byte is now the leading char. (Given that the string is 
      // not out of sync -- we checked that out already) 
      leadChar = str[i]; 

      // check how many bytes this sequence takes and validate against 
      // illegal sequences 
      if(leadChar < 0x80) { 
       nBytes = 1; 
      } else if((leadChar & 0xe0) == 0xc0) { 
       if((str[i-1] & 0xc0) != 0x80) { 
        throw new Exception("Illegal UTF-8 sequence"); 
       } 
       nBytes = 2; 
      } else if ((leadChar & 0xf0) == 0xe0) { 
       if((str[i-1] & 0xc0) != 0x80 || 
        (str[i-2] & 0xc0) != 0x80) { 
        throw new Exception("Illegal UTF-8 sequence"); 
       } 
       nBytes = 3; 
      } else if ((leadChar & 0xf8) == 0xf0) { 
       if((str[i-1] & 0xc0) != 0x80 || 
        (str[i-2] & 0xc0) != 0x80 || 
        (str[i-3] & 0xc0) != 0x80 ) { 
        throw new Exception("Illegal UTF-8 sequence"); 
       } 
       nBytes = 4; 
      } else { 
       throw new Exception("Illegal UTF-8 sequence"); 
      } 

      // now, reverse the current sequence and then continue 
      // whith the next one 
      int back = i; 
      int front = back - nBytes + 1; 

      while(front < back) { 
       byte tmp = str[front]; 
       str[front] = str[back]; 
       str[back] = tmp; 
       front++; 
       back--; 
      } 
      i -= nBytes; 
     } 
    } 
} 

Answer 3

Giải pháp tốt nhất:

1. Chuyển đổi sang một char chuỗi rộng
2. Đảo ngược chuỗi mới

Không bao giờ, không bao giờ, không bao giờ, không bao giờ coi các byte đơn là ký tự.

Answer 4

Đồng ý rằng cách tiếp cận của bạn là cách duy nhất để làm điều đó tại chỗ.

Cá nhân tôi không thích xác thực lại UTF8 bên trong mọi chức năng liên quan đến nó và thường chỉ làm những gì cần thiết để tránh sự cố; nó cho biết thêm ít mã hơn rất nhiều. Dunno nhiều C# Và đây chính là trong C:

(sửa để loại bỏ strlen)

void reverse(char *start, char *end) 
{ 
    while(start < end) 
    { 
     char c = *start; 
     *start++ = *end; 
     *end-- = c; 
    } 
} 

char *reverse_char(char *start) 
{ 
    char *end = start; 
    while((end[1] & 0xC0) == 0x80) end++; 
    reverse(start, end); 
    return(end+1); 
} 

void reverse_string(char *string) 
{ 
    char *end = string; 
    while(*end) end = reverse_char(end); 
    reverse(string, end-1); 
} 

Answer 5

Mã này giả định rằng các đầu vào UTF-8 chuỗi là hợp lệ và cũng được hình thành (tức là tối đa 4 byte mỗi multibyte ký tự):

#include "string.h" 

void utf8rev(char *str) 
{ 
    /* this assumes that str is valid UTF-8 */ 
    char *scanl, *scanr, *scanr2, c; 

    /* first reverse the string */ 
    for (scanl= str, scanr= str + strlen(str); scanl < scanr;) 
     c= *scanl, *scanl++= *--scanr, *scanr= c; 

    /* then scan all bytes and reverse each multibyte character */ 
    for (scanl= scanr= str; c= *scanr++;) { 
     if ((c & 0x80) == 0) // ASCII char 
      scanl= scanr; 
     else if ((c & 0xc0) == 0xc0) { // start of multibyte 
      scanr2= scanr; 
      switch (scanr - scanl) { 
       case 4: c= *scanl, *scanl++= *--scanr, *scanr= c; // fallthrough 
       case 3: // fallthrough 
       case 2: c= *scanl, *scanl++= *--scanr, *scanr= c; 
      } 
      scanr= scanl= scanr2; 
     } 
    } 
} 

// quick and dirty main for testing purposes 
#include "stdio.h" 

int main(int argc, char* argv[]) 
{ 
    char buffer[256]; 
    buffer[sizeof(buffer)-1]= '\0'; 

    while (--argc > 0) { 
     strncpy(buffer, argv[argc], sizeof(buffer)-1); // don't overwrite final null 
     printf("%s → ", buffer); 
     utf8rev(buffer); 
     printf("%s\n", buffer); 
    } 
    return 0; 
} 

Nếu bạn biên dịch chương trình này (tên ví dụ: so199260.c) và chạy nó trên một môi trường UTF-8 (một cài đặt Linux trong trường hợp này):

$ so199260 γεια και χαρά français АДЖИ a♠♡♢♣b 
a♠♡♢♣b → b♣♢♡♠a 
АДЖИ → ИЖДА 
français → siaçnarf 
χαρά → άραχ 
και → ιακ 
γεια → αιεγ 

Nếu mã quá khó hiểu, tôi sẽ vui vẻ làm rõ.