Эффективного отображения для конкретного конечных целого набора

Question

Я ищу маленькие, быстрое (в обоих направлениях) биективное отображение между следующим списком целых чисел и подмножеством диапазона 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 

Одно очевидное решение:

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

Edit: я пропускал некоторые ценности, в частности 0x20Ax, которые не работают с вышесказанным.

Еще одно очевидное решение - это таблица поиска, но без необходимости делать ее излишне большой, таблица поиска потребует некоторой перестановки бит в любом случае, и я подозреваю, что вся задача может быть лучше выполнена с простой перестановкой бит.

Для любознательных, эти магические числа являются единственными «большими» кодами Unicode, которые отображаются в устаревших ISO-8859 и кодовых страницах Windows.

Answer 1

Я знаю, что это некрасиво, но за последнее значение, кроме всех остальных уже уникальны, если учесть низкие 6 бит, так что вы можете построить и обратное отображение:

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

После этого обратного отображения вычисления два преобразования функции

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

функция direct(x) возвращает число в диапазоне от 0 до 63, а функция inverse(x) дано число от 0 до 63 будет возвращать целое число. Для всех 27 значений в вашем списке inverse(direct(x)) == x.

Answer 2

Я бы выбрал простую (и дешевую) хеш-функцию f, которую вы выбрали из семейства f0, f1, ... таких функций, которые соответствуют значениям 0..255. Если ваша хеш-функция будет случайной, то в парадоксальности дня вы столкнетесь с некоторыми коллизиями для интересующих вас ценностей, но не для многих.

Теперь простой скрипт perl (любого) позволит вам предварительно обработать ваши данные с фиксированной стоимостью, чтобы уменьшить (или даже устранить) коллизии, выбрав соответствующую функцию из вашего набора.

Этот подход имеет то преимущество, что вы можете возобновить прогон предварительной обработки, если узнаете, что вы забыли значение (как вы уже это сделали), или какая-то странная страна решает сопоставить странные символы юникода, например, 8-символьный набор символов.

И, кстати, я думаю, количество специальных символов, которые находятся в некоторых из iso-8859-? наборы должны быть намного больше, чем у вас, здесь нет? Я возьму их всех.

Edit: После выполнения некоторых экспериментов немного Перл говорит мне, что все точки 577 Юникода код, которые появляются в одном из изо-8859 кодировок карты в различные положения, когда уменьшаются по модулю 10007 или 10009.

Edit: Следующая таблица делает трюк, для ограниченного набора:

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

Методом проб & ошибок, я пришел к следующему алгоритму:

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

Иногда, эволюция ударов интеллектуальная конструкция даже при написании кода;)

Answer 4

Этот метод использует умножение в конечном Поле:

#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() преобразует точки Юникода к уникальным 7 битных чисел, и unmap() делает обратное. Обратите внимание, что gcc по крайней мере способен скомпилировать это код x86, который не использует никаких операций деления, поскольку модуль является константой.