2014-09-27 22 views
5

Per this question Ho creato il seguente codice Lua che converte un punto di codice Unicode in una stringa di caratteri UTF-8. C'è un modo migliore per farlo (in Lua 5.1+)? "Migliore" in questo caso significa "drasticamente più efficiente, o, preferibilmente, molto meno righe di codice".Un modo più elegante e più semplice per convertire il punto di codice in UTF-8

Nota: non sto davvero chiedendo un code review di questo algoritmo; Sto chiedendo un algoritmo migliore (o libreria integrata).

do 
    local bytebits = { 
    {0x7F,{0,128}}, 
    {0x7FF,{192,32},{128,64}}, 
    {0xFFFF,{224,16},{128,64},{128,64}}, 
    {0x1FFFFF,{240,8},{128,64},{128,64},{128,64}} 
    } 
    function utf8(decimal) 
    local charbytes = {} 
    for b,lim in ipairs(bytebits) do 
     if decimal<=lim[1] then 
     for i=b,1,-1 do 
      local prefix,max = lim[i+1][1],lim[i+1][2] 
      local mod = decimal % max 
      charbytes[i] = string.char(prefix + mod) 
      decimal = (decimal - mod)/max 
     end 
     break 
     end 
    end 
    return table.concat(charbytes) 
    end 
end 

c=utf8(0x24)  print(c.." is "..#c.." bytes.") --> $ is 1 bytes. 
c=utf8(0xA2)  print(c.." is "..#c.." bytes.") --> ¢ is 2 bytes. 
c=utf8(0x20AC) print(c.." is "..#c.." bytes.") --> € is 3 bytes. 
c=utf8(0xFFFF) print(c.." is "..#c.." bytes.") --> is 3 bytes. 
c=utf8(0x10000) print(c.." is "..#c.." bytes.") --> is 4 bytes. 
c=utf8(0x24B62) print(c.." is "..#c.." bytes.") --> is 4 bytes. 

Mi sento come se ci dovrebbe essere un modo per sbarazzarsi di tutta la bytebits tabella predefinita e loop di solo per trovare la voce corrispondente. A partire dal retro potrei continuamente %64 e aggiungere 128 per formare i byte di continuazione fino a un valore inferiore a 128, ma non riesco a capire come generare elegantemente il preambolo 0/110/1110/11110 da aggiungere.


Edit: Ecco una rielaborazione leggermente migliore, con un'ottimizzazione della velocità. Questa non è una risposta accettabile, tuttavia, poiché l'algoritmo è ancora fondamentalmente la stessa idea e circa la stessa quantità di codice.

do 
    local bytemarkers = { {0x7FF,192}, {0xFFFF,224}, {0x1FFFFF,240} } 
    function utf8(decimal) 
    if decimal<128 then return string.char(decimal) end 
    local charbytes = {} 
    for bytes,vals in ipairs(bytemarkers) do 
     if decimal<=vals[1] then 
     for b=bytes+1,2,-1 do 
      local mod = decimal%64 
      decimal = (decimal-mod)/64 
      charbytes[b] = string.char(128+mod) 
     end 
     charbytes[1] = string.char(vals[2]+decimal) 
     break 
     end 
    end 
    return table.concat(charbytes) 
    end 
end 
+0

Tentativo di eseguire il ciclo, il mio commento finale sopra descrive un algoritmo imperfetto. Ad esempio, Unicode [code point '0x10000'] (http://www.fileformat.info/info/unicode/char/10000/index.htm) richiede quattro byte in UTF-8. Dopo aver spostato a destra di 12 bit (due '/ 64') il valore originale è ridotto a solo 16. Sembra una conoscenza hard-coded sulla relazione tra il valore iniziale, il numero di byte e il preambolo del byte iniziale è fondamentalmente necessario. – Phrogz

risposta

3

Se stiamo parlando di velocità, il modello di utilizzo in uno scenario del mondo reale è molto importante. Ma qui, siamo nel vuoto, quindi procediamo comunque.

Questo algoritmo è probabilmente quello che stai cercando per quando dici cosa che si dovrebbe essere in grado di sbarazzarsi di bytebits:

do 
    local string_char = string.char 
    function utf8(cp) 
    if cp < 128 then 
     return string_char(cp) 
    end 
    local s = "" 
    local prefix_max = 32 
    while true do 
     local suffix = cp % 64 
     s = string_char(128 + suffix)..s 
     cp = (cp - suffix)/64 
     if cp < prefix_max then 
     return string_char((256 - (2 * prefix_max)) + cp)..s 
     end 
     prefix_max = prefix_max/2 
    end 
    end 
end 

Esso include anche alcune altre ottimizzazioni che non sono particolarmente interessante, e per me è circa 2 volte più veloce del codice ottimizzato. (. Come bonus, dovrebbe funzionare tutto il senso fino a U + 7FFFFFFF pure)

Se vogliamo micro-ottimizzare ancora di più, il loop può essere srotolato per:

do 
    local string_char = string.char 
    function utf8_unrolled(cp) 
    if cp < 128 then 
     return string_char(cp) 
    end 
    local suffix = cp % 64 
    local c4 = 128 + suffix 
    cp = (cp - suffix)/64 
    if cp < 32 then 
     return string_char(192 + cp, c4) 
    end 
    suffix = cp % 64 
    local c3 = 128 + suffix 
    cp = (cp - suffix)/64 
    if cp < 16 then 
     return string_char(224 + cp, c3, c4) 
    end 
    suffix = cp % 64 
    cp = (cp - suffix)/64 
    return string_char(240 + cp, 128 + suffix, c3, c4) 
    end 
end 

Questo è circa 5 volte più veloce del tuo codice ottimizzato, ma del tutto inelegante. Penso che i principali guadagni non debbano memorizzare risultati intermedi sullo heap e avere meno chiamate di funzione.

Tuttavia, il più veloce (per quanto posso trovare) approccio non è quello di fare il calcolo a tutti:

do 
    local lookup = {} 
    for i=0,0x1FFFFF do 
    lookup[i]=calculate_utf8(i) 
    end 
    function utf8(cp) 
    return lookup[cp] 
    end 
end 

questo è circa 30 volte più velocemente il codice ottimizzato che può qualificarsi come "drasticamente più efficiente "(sebbene l'uso della memoria sia ridicolo). Tuttavia, non è nemmeno interessante. (Un buon compromesso in alcuni casi potrebbe essere l'uso della memoizzazione.)

Naturalmente, qualsiasi implementazione di pura c dovrebbe essere più veloce di qualsiasi calcolo eseguito in Lua.

+0

Un punto eccellente sulla memoizzazione. Lo aggiungerò sicuramente, grazie! Analizzerò senz'altro il tuo algoritmo e se premierà l'accettazione. – Phrogz

+0

Per quello che vale, anche senza srotolare e memorizzare il codice prova circa 4 volte più veloce del mio sulla mia macchina. (Usando una distribuzione pari al mondo reale di 1000000 punti di codice casuali tra '1' e' 0x10FFFF', e anche tra '1' e' 0x20AC'.) E ho confermato che entrambe le nostre risposte producono gli stessi risultati per tutti il codice punta a '0x10FFFF' (RFC 3629). Molto bene. – Phrogz

3

Lua 5.3 fornisce a basic UTF-8 library, tra i quali la funzione utf8.char è quello che cerchi:

Riceve zero o più numeri interi, converte ciascuno al suo corrispondente UTF-8 sequenza di byte e restituisce una stringa con la concatenazione di tutte queste sequenze.

c = utf8.char(0x24)  print(c.." is "..#c.." bytes.") --> $ is 1 bytes. 
c = utf8.char(0xA2)  print(c.." is "..#c.." bytes.") --> ¢ is 2 bytes. 
c = utf8.char(0x20AC) print(c.." is "..#c.." bytes.") --> € is 3 bytes. 
c = utf8.char(0xFFFF) print(c.." is "..#c.." bytes.") --> is 3 bytes. 
c = utf8.char(0x10000) print(c.." is "..#c.." bytes.") --> is 4 bytes. 
c = utf8.char(0x24B62) print(c.." is "..#c.." bytes.") --> is 4 bytes. 
+0

Questo algoritmo soddisfa probabilmente i criteri del richiedente. –

+0

@TomBlodget Che soddisfa tutti i miei criteri tranne, purtroppo, il requisito per il supporto Lua 5.1. – Phrogz

+0

@Phrogz Puoi riscriverlo in Lua, anche se senza la libreria bit32 non sembra elegante. –

Problemi correlati