logo标签列表

一个特定有限整数集的高效映射

cunicodemappingbit-manipulation
5

我正在寻找一种小而快速（在两个方向上）的双射映射，将以下整数列表映射到范围为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;

编辑：我错过了一些值，特别是0x20Ax，这些值与上面的值不兼容。

另一个明显的解决方案是查找表，但是如果没有使它变得不必要地大，查找表仍然需要一些位重新排列，我怀疑整个任务可以通过简单的位重新排列更好地完成。

对于好奇的人来说，这些神奇的数字是唯一出现在传统ISO-8859和Windows代码页中的“大” Unicode 代码点。

http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm - Ignacio Vazquez-Abrams
顺便提一下，到子集的双射映射被称为单射 ;) - Christoph
4个回答
3

这种方法使用有限域中的乘法：

#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代码，因为模数是一个常量。

你是手动解决的还是用工具做的？这绝对是迄今为止对我提出的问题最优雅的回答，尽管我可能最终会像Jens所说的那样，使用一个两级映射来处理这些集合中的所有字符。 - R.. GitHub STOP HELPING ICE
@R.：我选择了0x119作为第一个大于0x2122 - 0x200c的质数，然后编写了一个简短的C程序来暴力破解OFFSET1和MULTIPLIER值，以获得最窄的范围。由于该范围小于0x7f，因此我在那里停止并计算了2模0x119的乘法逆元。如果0x119不起作用，我将转向下一个更高的质数。 - caf
一个好的、干净的方法来解决问题；奇怪的是，尽管我的临时算法看起来非常丑陋，但它似乎比你的解码函数表现得更好... - Christoph
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之间的数字，而给定0到63之间的数字的函数inverse(x)将返回一个整数。对于列表中的所有27个值，inverse(direct(x)) == x。
1

我会选择一些简单（且便宜）的哈希函数f，你可以从一个家族f0，f1，...中选择这样的函数，它们映射到值0..255。如果您的哈希函数是随机的，根据生日悖论，您将对您感兴趣的值有一些冲突，但不多。

现在，一个简单的perl（或其他语言）脚本将允许您预处理您的固定值数据，通过从您的集合中选择适当的函数来减少（甚至消除）冲突。

这种方法的优点是，如果您发现自己忘记了某个值（就像您已经做过的那样），或者某个奇怪的国家决定将奇怪的Unicode字符（如€）映射到8位字符集中，您可以更新预处理运行。

顺便说一句，我认为一些iso-8859-？集中的特殊字符数量必须比您这里拥有的要大得多，不是吗？我会把它们全部拿走。

编辑：经过一些实验，一个小perl脚本告诉我，出现在iso-8859编码中的所有577个unicode代码点在对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' /* ₯ */,
};
iso-8859-*和windows代码页中的大多数字符都在其各自字母表的范围内（西里尔文、希腊文、希伯来文、扩展拉丁文等），但我使用了比必要更大的表格来容纳一些罕见的U+2xxx代码（欧元符号、商标符号、智能引号等）。 - R.. GitHub STOP HELPING ICE
好的，我明白了。但是，与其必须迭代不同的字符集，我会选择一种通用解决方案来捕获它们。如果您查看https://secure.wikimedia.org/wikipedia/en/wiki/ISO/IEC_8859中的表格，那里并没有太多字符集。但也许您需要在比我想象的更大的东西中对它们进行哈希运算，10位应该可以很好地解决问题。 - Jens Gustedt
实际上，对于大多数传统字符集而言，每个条目的10位足够了，除了那些丑陋的U + 2xxx情况。我问题中的0-127来自这样一个事实：没有高字节可以映射到ASCII，所以我可以在此范围内重用数字作为U + 2xxx字符的重定向。 - R.. GitHub STOP HELPING ICE
你是在说哪个577？模10007或10009的减少似乎不会让它们变得非常小；我已经做得比那更好了。 - R.. GitHub STOP HELPING ICE
所有出现在iso-8859中的代码点。我没有测试到那时候所有的质数，但是4000范围内的一些数字不行，而这两个数字可以。如果你只针对你感兴趣的代码点进行这样的测试，你可能会找到一个更小的质数。然后，是的，这将为您提供一个有很多空白的第一级表，但是您可以只存储您感兴趣的值0..127或者其他。 - Jens Gustedt
@R：使用91可以解决包含你所寻找的值的集合问题。请查看我的编辑。 - Jens Gustedt
0

通过不断尝试，我得出了以下算法：

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

有时候，在编写代码时，进化甚至会战胜智能设计；）
enc 的输出比 127 大很多。 - R.. GitHub STOP HELPING ICE
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接