14

最近、誰かがC で文字列を逆にするアルゴリズムについて尋ねました。提案されたソリューションのほとんどは、非シングルバイト文字列を扱うときに問題がありました。そこで、特に utf-8 文字列を処理するための優れたアルゴリズムは何かと考えていました。

私は答えとして投稿しているコードを思いつきましたが、他の人のアイデアや提案を見てうれしいです. 私は実際のコードを使用することを好んだので、このサイトで最も人気のある言語の 1 つと思われる C# を選択しましたが、コードが別の言語であっても、合理的である限り気にしません。命令型言語に精通している人なら誰でも理解できます。そして、これはそのようなアルゴリズムを低レベルで実装する方法を確認することを目的としているため (低レベルとは単にバイトを処理することを意味します)、コア コードにライブラリを使用しないようにするという考えです。

ノート：

私はアルゴリズム自体、そのパフォーマンス、および最適化方法に興味があります (i++ を ++i などに置き換えるのではなく、アルゴリズムレベルの最適化を意味します。実際のベンチマークにもあまり興味がありません)。

実際に製品コードや「車輪の再発明」で使用するつもりはありません。これは単なる好奇心と練習用です。

私は C# バイト配列を使用しているので、NUL が見つかるまで文字列を実行せずに文字列の長さを取得できると想定しています。つまり、文字列の長さを見つける複雑さを説明していません。ただし、たとえば C を使用している場合は、コア コードを呼び出す前に strlen() を使用することで、それを除外できます。

編集：

Mike F が指摘しているように、私のコード (およびここに投稿された他の人のコード) は合成文字を扱っていません。ここにあるものについての情報。私はその概念に精通していませんが、それが「組み合わせ文字」、つまり他の「ベース」文字/コードポイントとの組み合わせでのみ有効な文字/コードポイントがあることを意味する場合、そのようなルックアップテーブル文字を使用して、反転時に「グローバル」文字 (「ベース」+「結合」文字) の順序を維持できます。

4

5 に答える 5

13

バイトを反転する 1 つのパスを作成し、次にマルチバイト文字 (UTF8 で簡単に検出される) のバイトを正しい順序に戻す 2 番目のパスを作成します。

これは間違いなく 1 回のパスでインラインで処理できますが、ルーチンがボトルネックにならない限り気にしません。

于 2008-10-13T22:34:52.180 に答える
8

このコードは、入力 UTF-8 文字列が有効で、適切な形式 (マルチバイト文字あたり最大 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 環境 (この場合は Linux インストール) で実行すると、次のようになります。

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

コードが難解すぎる場合は、喜んで明確にします。

于 2008-10-13T23:44:36.220 に答える
6

あなたのアプローチがその場でそれを行う唯一の正気の方法であることに同意してください。

個人的には、UTF8 を扱うすべての関数内で UTF8 を再検証するのは好きではありません。通常は、クラッシュを回避するために必要なことだけを行います。合計すると、コードが大幅に少なくなります。C# はあまり知られていないので、ここでは C で説明します。

( 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 );
}
于 2008-10-13T23:14:00.930 に答える
5

私の最初のアプローチは、次のように要約できます。

1) 単純にバイトを反転する

2) 文字列を逆方向に実行し、utf8 シーケンスを修正します。

不正なシーケンスは 2 番目のステップで処理され、最初のステップで、文字列が「同期」しているかどうか (つまり、正当な先行バイトで始まっているかどうか) を確認します。

編集: 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;
        }
    }
}
于 2008-10-13T22:35:08.497 に答える
-3

最善の解決策:

  1. ワイド文字列に変換
  2. 新しい文字列を逆にする

決して、決して、決して、決して、単一バイトを文字として扱わないでください。

于 2008-10-13T22:36:16.013 に答える