How to split an array of bytes avoiding to truncate in the middle of an unicode extended grapheme cluster

user_4220763 0
Viewed 98

Say we have an arbitrary long array of bytes read with the sysread() Perl function that we have to split in a fixed number of CHARS avoiding to truncate in the middle of an unicode grapheme. As an example, say we have to split an array of bytes in chunks of 5 CHARS and that we have the following byte sequence:

0x61 0x62 0x63 0x64 0x65    0xcc 0x81 0x61 0x62 0x63 0x64 0xe2 0x82 0xac

Reading the last byte of the first 5 bytes (0X65) we get that it is a valid grapheme (char e) and scanning byte per byte the second byte sequence rightward and testing (using the \X matcher) the increasing sequence (first 0xCC, then 0xCC 0x81) we get that the sequence 0xCC 0x81 is also a valid grapheme (a non printable char or a strange space), but the correct grapheme is 0x65 0xCC 0x81 (char é).

My try was, starting from the cut point (e.g. between 5th and 6th byte), to test if the left byte (in our case 0x65) falls or not in the [\xC0-\xFF] range. If NOT: add byte per byte from the right sequence and truncate the sequence when the matcher /^\X$/ returns false and this approach in my tests worked fine.

My problem is that when the last byte of first sequence falls in the range [\xC0-\xFF] it means I might be in the middle of a grapheme and then I go crazy because I can't figure out how to correctly identify the boundaries of the grapheme cluster (as they may be arbitrarily long).

Note 1: I can't UTF-8 encode the whole input file and work at CHAR level because I have to deal with files of some TB and the performance is a must.

Note 2: I read the excellent Tom Chirstiansen's Perl Unicode Cookbook and it helped me a lot to better understand some Unicode basis but not to find a way to solve my problem.

Any help or tip would be really appreciated

PS: Should I consider using the C++ ICU library instead of Perl?

UPDATE I omitted for sake of semplicity that I don't scan the whole file, but I do a parallel processing of fixed length chunks of the file using the sysread() with an offset.. then I use the sysseek() on each chunk boundary to look ahead or backward, searching for the grapheme boundaries.

perl
1 Answers

A working solution is to analyze the surroundings of the byte stream at the cut you want to make. The only limitation is that you must set a maximum length of bytes that can make up a grapheme cluster.

In correspondence with the offset in which the sequence of bytes is to be cut, a range of bytes must be selected which includes the last bytes of the first chunk (equal to the maximum bytes limit set for a grapheme cluster) and as many bytes of the beginning of the next chunk. In this way we can be sure to find at least one complete grapheme cluster within the analyzed bytes.

The module Unicode::GCString is used to identify the grapheme clusters in the range of bytes analyzed.

The program below cuts the sequence of bytes by excess: if the last grapheme cluster of a chunk has bytes in the next chunk, the cut takes place at that point. This means that the last chunk will be a few bytes shorter than the others, but adding some logic can better balance the distribution of bytes. The program is purely demonstrative and does not partition the byte sequence but only prints the offsets in which to truncate the sequence.

binmode STDOUT, ':utf8' ; # avoid wide char warning 
use Encode qw( decode_utf8 encode_utf8 ) ;
use Unicode::GCString ;

# --- Config ---
my $partitions             = 8 ;
my $max_bytes_per_grapheme = 10 ;

# --- Create a byte sequence sample (1000 grapheme cluster) ---
my @graphemes = (
    [ 0x61 ],                                       # a
    [ 0xC2, 0xAE ],                                 # ®
    [ 0x67, 0xCC, 0x88 ],                           # g̈
    [ 0xC3, 0x80, 0xCC, 0x88 ],                     # À̈
    [ 0x6F, 0xCC, 0x88, 0xCC, 0xB2 ],               # ö̲
    [ 0xC6, 0x81, 0xCC, 0x88, 0xCD, 0x9C ],         # Ɓ̈͜
    [ 0x6F, 0xCC, 0x88, 0xCC, 0xB2, 0xCD, 0x9C ]    # ö̲͜
) ;
my @bytes = map { @{ $graphemes[ int rand 7 ] } } ( 1 .. 1000 ) ;

my $index = 0 ;
my $offset = int( @bytes / $partitions ) ;

printf "Bytes: %d - Partitions: %d - Optimal offset: %d\n\n", scalar( @bytes ),$partitions,$offset ;

for ( 1 .. $partitions - 1 ) {

    my $l_index = $index + $offset - $max_bytes_per_grapheme ; # last bytes of partition
    my $r_index = $index + $offset + $max_bytes_per_grapheme ; # first bytes of next partition

    # --- Get bytes slice to analyze ---
    my @bytes_to_analyze = @bytes[ $l_index .. $r_index ] ;

    # --- Decode bytes as UTF-8 string ---
    my $utf8_string = decode_utf8( join '', map chr, @bytes_to_analyze ) ;

    # --- Create GCString object ---
    my $gcstring = Unicode::GCString->new( $utf8_string ) ;

    my $grapheme ;
    my $grapheme_index = 0 ;
   
    # --- Iterate over extended grapheme clusters ---
    while ( $grapheme = $gcstring->next ) {

        my $bytes_count = length( encode_utf8( $grapheme ) ) ;
        die "Grapheme cluster $grapheme is too long: $bytes_count bytes" 
           if $bytes_count > $max_bytes_per_grapheme ; 

        $grapheme_index += $bytes_count ;

        last if $grapheme_index >= $max_bytes_per_grapheme ;
    }

    $index += $offset - $max_bytes_per_grapheme + $grapheme_index ;
    print "Can truncate at grapheme: $grapheme - byte index: $index\n" ;
}

Output:

Bytes: 3957 - Partitions: 8 - Optimal offset: 494

Can truncate at grapheme: g̈ - byte index: 495
Can truncate at grapheme: ö̲͜ - byte index: 995
Can truncate at grapheme: Ɓ̈͜ - byte index: 1493
Can truncate at grapheme: À̈ - byte index: 1989
Can truncate at grapheme: Ɓ̈͜ - byte index: 2487
Can truncate at grapheme: ö̲ - byte index: 2981
Can truncate at grapheme: g̈ - byte index: 3476
user_42207630
Related