UTF-8 문자열을 제 위치에서 되돌리려면 어떻게해야합니까?

Question

최근 누군가가 algorithm for reversing a string in place in C에 대해 질문했습니다. 제안 된 솔루션의 대부분은 1 바이트가 아닌 문자열을 처리 할 때 문제가있었습니다. 그래서 저는 utf-8 문자열을 다루는 좋은 알고리즘이 무엇인지 궁금합니다.

나는 코드로 대답을 올렸지 만, 다른 사람들의 아이디어 나 제안을 보게되어 기쁩니다. 나는 실제 코드를 사용하기를 선호했기 때문에이 사이트에서 가장 인기있는 언어 중 하나 인 것처럼 C#을 선택했습니다.하지만 코드가 다른 언어로되어 있다면 괜찮습니다. 명령형 언어에 익숙한 사람이라면 누구나 이해할 수 있습니다. 그리고 이것은 그러한 알고리즘이 저수준 (저수준에서 바이트를 다루는 것을 의미 함)에서 어떻게 구현 될 수 있는지를 알기위한 것이므로 핵심 코드에 라이브러리를 사용하지 않는 것이 좋습니다.

참고 :; 난 그것을 최적화 할 수있는 방법을

내가 알고리즘 자체에 관심이 있어요, 그 성능 및 (I 알고리즘 레벨 최적화, 나는 이러한 ++와 ++ 교체하지 의미 실제 벤치 마크에도 관심이 없다).

실제로 프로덕션 코드 또는 "휠체어 다시 작성"에서 사용하는 것은 아닙니다. 이것은 호기심과 운동으로 끝난 것입니다.

Null을 찾을 때까지 문자열을 실행하지 않고 문자열의 길이를 얻을 수 있다고 가정하므로 C# 바이트 배열을 사용하고 있습니다. 즉, 문자열의 길이를 찾는 복잡성을 고려하지 않았습니다. 그러나 예를 들어 C를 사용하는 경우 코어 코드를 호출하기 전에 strlen()을 사용하여 문제를 해결할 수 있습니다.

편집 : 마이크 F가 지적 하듯이

, 내 코드 (그리고 여기에 게시 다른 사람의 코드) 복합 문자로 취급되지 않습니다. 그 사람들에 관한 정보는 here입니다. 나는이 개념에 익숙하지 않지만 "결합 문자"즉, 다른 "기본"문자/코드 포인트와 결합해서 만 유효한 문자/코드 포인트가 있다는 것을 의미한다면, 그러한 되돌릴 때 "전역"문자 ("기본"+ "결합"문자)의 순서를 유지하기 위해 문자를 사용할 수 있습니다.

Answer 1

바이트를 반대로 한 다음, 올바른 순서로 다시 되돌려주는 멀티 바이트 문자 (UTF8에서 쉽게 감지 할 수 있음)의 바이트를 반대로 변환합니다.

이 과정을 한 번에 한 줄로 처리 할 수는 있지만 루틴에 병목 현상이 발생하지 않는 한 신경 쓸 필요가 없습니다.

Answer 2

내 초기 접근 방법은이 방법을 요약함으로써 수 :

1) 역 바이트 순진

2) 뒤쪽으로 문자열을 실행하고 당신이가는대로 UTF8 시퀀스를 수정합니다.

불법 시퀀스는 두 번째 단계에서 처리되며 첫 번째 단계에서는 문자열이 "sync"(즉, 유효 선행 바이트로 시작하는 경우)인지 확인합니다.

편집 : 역에서 바이트를 선도에 대한 검증 기능을 향상() 가장 좋은 해결책

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

:

1. 넓은 문자 문자열
2. 로 변환이 새 문자열을 역

절대, 절대로, 절대로 단일 바이트를 문자로 처리하지 마십시오.

Answer 4

귀하의 접근 방식이 제자리에서 할 수있는 유일한 제법입니다.

개인적으로 나는 그것을 다루는 모든 함수 안에 UTF8을 재 검증하는 것이 싫고, 일반적으로 충돌을 피하기 위해 필요한 것만 수행한다. 그것은 훨씬 적은 코드를 추가합니다. 그래서 여기에 많은 C 번호를 몰라 그것은 C :

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

이 코드는 입력 UTF-8 문자열이 유효하다고 가정한다 (편집 이를 나 strlen 제거하기 위해) 잘 (형성 즉, 대부분의 4 바이트에서 멀티 바이트 당 문자) :

#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; 
} 

이 프로그램 (예를 들어, 이름을 컴파일하는 경우 : so199260.c을)와 UTF-8 환경이 경우 (리눅스 설치를) 실행 :

,536,913를

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

코드가 너무 복잡하면 기꺼이 설명해 드리겠습니다.