Эффективное отображение для определенного конечного целого набора - PullRequest
Новая
       3

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

5 голосов
/ 06 февраля 2011

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

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

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

Редактировать: Мне не хватало некоторых значений, в частности 0x20Ax, которые не работают с вышеприведенным.

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

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

Ответы [ 4 ]

3 голосов
/ 07 февраля 2011

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

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

1 голос
/ 06 февраля 2011

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

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

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

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

Редактировать: После некоторых экспериментов небольшой скрипт на Perl сообщает мне, что все 577 кодовых точек юникода, которые появляются в одной из кодировок iso-8859, отображаются на разныепозиции при уменьшении по модулю 10007 или 10009.

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

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' /* ₯ */,
};
1 голос
/ 06 февраля 2011

Я знаю, что это некрасиво, но кроме последнего значения все остальные уже уникальны, если учесть младшие 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.

0 голосов
/ 06 февраля 2011

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

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

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

...