Efektywne mapowanie dla określonej skończonej liczby całkowitej ustawić

Question

szukam mały, szybki (w obu kierunkach) bijective mapowanie pomiędzy poniższej listy liczb całkowitych i podzbioru zakresu 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 

oczywistym rozwiązaniem jest:

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

Edit: mi brakuje niektórych wartości, zwłaszcza 0x20Ax, które nie współpracują z powyższych.

Innym oczywistym rozwiązaniem jest tablica przeglądowa, ale bez konieczności niepotrzebnego powiększania, tabela przeglądowa i tak wymagać będzie nieco przegrupowania i podejrzewam, że całe zadanie można lepiej wykonać przy prostym przegrupowaniu bitów.

Dla ciekawskich, te magiczne liczby są jedynymi "dużymi" kodami kodowymi Unicode, które pojawiają się na starszych stronach kodowych ISO-8859 i Windows.

Answer 1

wiem, że jest brzydki, ale z wyjątkiem ostatniej wartości wszyscy inni są już unikatowe jeśli wziąć pod uwagę najniższe 6 bitów, więc można po prostu zbudować i odwrotna mapa:

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

Po tym odwrotność mapy obliczeń dwa przekształcić funkcje

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

funkcja direct(x) powróci liczbę od 0 do 63, a funkcja inverse(x) podano liczbę między 0 a 63 powróci liczbę całkowitą. Dla wszystkich 27 wartości na liście inverse(direct(x)) == x.

Answer 2

Poszedłem na jakąś prostą (i tanią) funkcję skrótu f, którą wybrałeś z rodziny f0, f1, ... takich funkcji, które odwzorowują na wartości 0..255, powiedzmy. Jeśli twoja funkcja hash będzie losowa, przez paradoks urodzin będziesz miał pewne kolizje dla wartości, które cię interesują, ale nie wiele.

Teraz prosty skrypt perl (dowolnego) pozwoli na wstępne przetworzenie danych o stałej wartości w celu zmniejszenia (lub nawet wyeliminowania) kolizji poprzez wybranie odpowiedniej funkcji ze swojego zestawu.

Takie podejście ma tę zaletę, że można odnowić przebieg wstępny, jeśli okaże się, że nie pamiętasz wartości (jak już zrobiłeś) lub jakiś dziwny kraj decyduje się na mapowanie dziwnych znaków Unicode, takich jak €, na zestaw znaków 8-bitowych.

I, BTW, myślę, że ilość znaków specjalnych, które są w niektórych z iso-8859-? zestawy muszą być znacznie większe niż to, co masz, tutaj, nie? Wziąłbym je wszystkie.

Edit: Po wykonaniu kilku eksperymentów trochę skrypt perl mówi mi, że wszystkie 577 Unicode punkty kodowe, które pojawiają się w jednym z kodowaniem iso-8859 map do różnych pozycjach, gdy zmniejszona modulo 10007 lub 10009.

Edit: W poniższej tabeli robi trick, dla ograniczonego zestawu:

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

Metodą prób & błędów doszedłem do następującego algorytmu:

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

Czasami uderzeń evolution inteligentna konstrukcja nawet przy pisaniu kodu;)

Answer 4

Ta metoda wykorzystuje mnożenie w skończonym fie 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() przekształca unikodowym punktów unikalnych 7 bitowych liczb i unmap() nie odwrotnie. Zauważ, że gcc przynajmniej jest w stanie skompilować to do kodu x86, który nie używa żadnych operacji dzielenia, ponieważ moduł jest stałą.