mappatura efficiente per un particolare intero insieme finito

Question

Sto cercando un piccolo, veloce (in entrambe le direzioni) corrispondenza biunivoca tra la seguente lista di numeri interi e un sottoinsieme della gamma 0-127:

0x200C, 0x200D, 0x200E, 0x200F, 
0x2013, 0x2014, 0x2015, 0x2017, 
0x2018, 0x2019, 0x201A, 0x201C, 
0x201D, 0x201E, 0x2020, 0x2021, 
0x2022, 0x2026, 0x2030, 0x2039, 
0x203A, 0x20AA, 0x20AB, 0x20AC, 
0x20AF, 0x2116, 0x2122 

una soluzione ovvia è:

y = x>>2 & 0x40 | x & 0x3f; 
x = 0x2000 | y<<2 & 0x100 | y & 0x3f; 

Edit: mi mancava alcuni dei valori, in particolare 0x20Ax, che non funzionano con quanto sopra.

Un'altra soluzione ovvia è una tabella di ricerca, ma senza renderla inutilmente grande, una tabella di ricerca richiederebbe comunque un po 'di riarrangiamento e sospetto che l'intero compito possa essere meglio realizzato con un riarrangiamento bit semplice.

Per i curiosi, quei numeri magici sono gli unici codepoint Unicode "grandi" che appaiono nelle legacy ISO-8859 e nelle codepage di Windows.

Answer 1

so che è brutto, ma tranne che per l'ultimo valore tutti gli altri sono già unico se si considera più bassi 6 bit, in modo da poter semplicemente costruire e mappa inversa:

int ints[] = {0x200C, 0x200D, 0x200E, 0x200F, 
       0x2013, 0x2014, 0x2015, 0x2017, 
       0x2018, 0x2019, 0x201A, 0x201C, 
       0x201D, 0x201E, 0x2020, 0x2021, 
       0x2022, 0x2026, 0x2030, 0x2039, 
       0x203A, 0x20AA, 0x20AB, 0x20AC, 
       0x20AF, 0x2116, 0x2122}; 

int invmap[64]; 

void mkinvmap() 
{ 
    for (int i=0; i<26; i++) 
     invmap[ints[i]&63] = ints[i]; 
    invmap[0] = 0x2122; 
} 

Dopo questo inversa mappa calcolo i due trasformare funzioni sono

int direct(int x) { return x==0x2122 ? 0 : (x & 63); } 
int inverse(int x) { return invmap[x]; } 

la funzione direct(x) restituirà un numero compreso tra 0 e 63, e la funzione inverse(x) dato un numero compreso tra 0 e 63 restituirà un numero intero. Per tutti i 27 valori nella lista inverse(direct(x)) == x.

Answer 2

Vorrei optare per una semplice (ed economica) funzione di hash f che si sceglie da una famiglia f0, f1, ... di tali funzioni che corrispondono ai valori 0..255, ad esempio. Se la tua funzione di hash fosse casuale, dal paradosso del compleanno avresti delle collisioni per i valori che ti interessano, ma non molti.

Ora un semplice script perl (di qualsiasi tipo) consentirà di preelaborare i dati a valore fisso per ridurre (o persino eliminare) le collisioni scegliendo una funzione appropriata dal set.

Questo approccio ha il vantaggio che è possibile rinnovare la corsa di pre-elaborazione se si scopre di aver dimenticato un valore (come già fatto) o qualche strano paese decide di mappare caratteri unicode bizzarri come € in un set di caratteri da 8 bit.

E, BTW, penso che la quantità di caratteri speciali presenti in alcuni iso-8859-? i set devono essere molto più grandi di quello che hai, qui, no? Li prenderei tutti.

Edit: Dopo aver fatto alcuni esperimenti un piccolo script perl mi dice che tutti i punti di codice Unicode 577 che appaiono in una delle codifiche iso-8859 mappano posizioni diverse quando ridotto modulo 10007 o 10009.

Edit: La tabella seguente fa il trucco, per la serie limitata:

wchar_t const uniqTable[91] = { 
[0x7] = L'\u2116' /* № */, 
[0xD] = L'\uFFFD' /* � */, 
[0xE] = L'\u200C' /* ‌ */, 
[0xF] = L'\u200D' /* ‍ */, 
[0x10] = L'\u200E' /* ‎ */, 
[0x11] = L'\u200F' /* ‏ */, 
[0x13] = L'\u2122' /* ™ */, 
[0x15] = L'\u2013' /* – */, 
[0x16] = L'\u2014' /* — */, 
[0x17] = L'\u2015' /* ― */, 
[0x19] = L'\u2017' /* ‗ */, 
[0x1A] = L'\u2018' /* ‘ */, 
[0x1B] = L'\u2019' /* ’ */, 
[0x1C] = L'\u201A' /* ‚ */, 
[0x1E] = L'\u201C' /* “ */, 
[0x1F] = L'\u201D' /* ” */, 
[0x20] = L'\u201E' /* „ */, 
[0x22] = L'\u2020' /* † */, 
[0x23] = L'\u2021' /* ‡ */, 
[0x24] = L'\u2022' /* • */, 
[0x28] = L'\u2026' /* … */, 
[0x32] = L'\u2030' /* ‰ */, 
[0x3B] = L'\u2039' /* ‹ */, 
[0x3C] = L'\u203A' /* › */, 
[0x51] = L'\u20AA' /* ₪ */, 
[0x52] = L'\u20AB' /* ₫ */, 
[0x53] = L'\u20AC' /* € */, 
[0x56] = L'\u20AF' /* ₯ */, 
}; 

Answer 3

Con prove & errore, sono arrivato al seguente algoritmo:

#include <assert.h> 
#include <stdio.h> 

static const unsigned CODES[] = { 
    0x200C, 0x200D, 0x200E, 0x200F, 
    0x2013, 0x2014, 0x2015, 0x2017, 
    0x2018, 0x2019, 0x201A, 0x201C, 
    0x201D, 0x201E, 0x2020, 0x2021, 
    0x2022, 0x2026, 0x2030, 0x2039, 
    0x203A, 0x20AA, 0x20AB, 0x20AC, 
    0x20AF, 0x2116, 0x2122 
}; 

static unsigned enc(unsigned value) 
{ 
    return (value & 0x3F) + (value & 0x180)/4; 
} 

static unsigned dec(unsigned value) 
{ 
    return 0x2000 + value + ((value & 0x40) >> 6) * 3 * 
     (0x20 + (value & 0x10) * 2 + (value & 0x20)); 
} 

int main(void) 
{ 
    const unsigned *const END = CODES + sizeof CODES/sizeof *CODES; 
    const unsigned *current = CODES; 
    for(; current < END; ++current) 
    { 
     printf("%04x -> %02x -> %04x\n", 
      *current, enc(*current), dec(enc(*current))); 

     assert(enc(*current) < 0x80); 
     assert(dec(enc(*current)) == *current); 
    } 

    return 0; 
} 

A volte, battiti evoluzione design intelligente anche durante la scrittura del codice;)

Answer 4

Questo metodo utilizza la moltiplicazione in un diagramma finito ld:

#define PRIME 0x119 
#define OFFSET1 0x00f 
#define OFFSET2 0x200c 
#define OFFSET3 (OFFSET2 - OFFSET1) 
#define MULTIPLIER 2 
#define INVERSE 0x8d 

unsigned map(unsigned n) 
{ 
    return ((n - OFFSET3) * MULTIPLIER) % PRIME; 
} 

unsigned unmap(unsigned m) 
{ 
    return ((m * INVERSE) + PRIME - OFFSET1) % PRIME + OFFSET2; 
} 

map() converte i punti unicode per le uniche numeri 7 bit, e unmap() fa il contrario. Notare che gcc è in grado di compilare questo codice x86 che non utilizza alcuna operazione di divisione, poiché il modulo è una costante.