0

假设 Visual C/C++ 6,我有一个包含 22399 个元素的复杂数据结构,如下所示:

{
{ "(SAME", "AS", "U+4E18)", "HILLOCK", "OR", "MOUND"},
{ "TO", "LICK;", {1, 1, 0}, "TASTE,", "A", "MAT,", "BAMBOO", "BARK"},
{ "(J)", "NON-STANDARD", "FORM", "OF", "U+559C", ",", {1, 1, 0}, "LIKE,", "LOVE,", "ENJOY;", {1, 1, 4}, "JOYFUL", "THING"},
{ "(AN", "ANCIENT", {1, 2, 2}, {1, 2, 3}, "U+4E94)", "FIVE"}, 
...
}

声明这一点的最佳方式是什么?我试过像

char * abbrevs3[22399][] = { ... };

char * abbrevs3[22399][][] = { ... };

但编译抱怨一些慢性的东西。

编辑:数据是某些 Unihan 字符描述的数据库。我一直在探索各种压缩数据的方法。就目前而言,您有 22399 个条目,每个条目可能包含不同数量的字符串,或 { abbrev marker, line where last seen, element of that line where last seen } 的三元组。

顺便说一下 Greg 的说法,我可能需要让每一行包含相同数量的元素,即使其中一些是空字符串。是这样吗?

编辑#2:我突然想到三元组中的一些数值超出了 char 的限制。

4

6 回答 6

4

我会考虑以 XML 或其他结构化形式存储数据,然后读取和解析它,而不是在代码中进行初始化。您在初始化时付出的代价将不仅仅在于易于理解和增加代码的可维护性。我还考虑设计一个特定的数据结构来保存每个条目。

[编辑] 下面的示例尝试复制您的后续描述:

enum EntryType { string = 0, triple = 1 };

typedef struct {
   enum EntryType entry_type;
   union {
      char** string;
      int[3] *triple;
   }
} Entry;

typedef struct {
   Entry *entries;
} Abbreviation;

Abbreviation *abbrevs3;

abbrevs3 = parseAbbreviationData("path-to-abbreviations/abbrevs.xml");
于 2008-10-12T18:33:34.367 回答
3

在 C 中,声明数组时只能省略第一个维度:

char * abbrevs3[][22399] = { ... };

这是因为编译器想知道每个“行”有多大,以便正确布置“列”。我将尺寸放在引号中,因为您可以自由地以任何您希望的方式解释尺寸,但这是二维数组的通常约定。

也就是说,尚不清楚您的数据结构实际上是什么或您尝试将其初始化为什么。您的示例数据似乎没有任何模式。

于 2008-10-12T18:15:57.427 回答
2

我刚刚阅读了您的新帖子并重新阅读了原始帖子,我想我只是完全理解了这里的目标。抱歉拖了这么久,我有点慢。

为了解释这个问题,在原始示例的第 4 行:

{ "(AN", "ANCIENT", {1, 2, 2}, {1, 2, 3}, "U+4E94)", "FIVE"},

您希望将三元组转换为对先前使用的字符串的引用,以尝试压缩数据。那行变成:

{ "(AN", "ANCIENT", "FORM", "OF", "U+4E94)", "FIVE"},

如果目标是压缩,我认为您不会在这里看到太多收益。自引用三元组各有 3 个字节,但被替换的字符串总共只有 8 个字节,计算空终止符,并且您在这一行只保存 2 个字节。那是为了使用字符。由于您的结构如此之大,以至于您将需要使用 int 进行引用,因此您的三元组实际上是 12 个字节,这甚至更糟。在这种情况下,您只能通过替换 12 个或更多 ascii 字符的单词来节省空间。

如果我在这里完全偏离基础,请随意忽略我,但我认为对空格进行标记然后删除重复单词的方法只是一种穷人的Huffman 压缩。Huffman 其中字母表是最长公共子串的列表,或者其他一些标准的文本压缩方法可能会很好地解决这个问题。

如果由于某种原因这不是一个选项,我想我会得到您数据中所有唯一单词的列表并将其用作查找表。然后将所有字符串作为索引列表存储到该表中。您必须使用两个表格,但最终它可能会更简单,并且可以节省您现在用作“缩写标记”的前导 1 所使用的空间。基本上,您的缩写标记将成为单个索引而不是三元组。

所以,

const char * words[] = {
    "hello", "world", "goodbye", "cruel"
    };

const int strings[] = {
    { 0, 1 },
    { 2, 3, 1 }
    };

如果你的字符串不是大致均匀的长度,你仍然会失去很多空间。

于 2008-10-13T17:49:22.380 回答
1

我认为这里的问题是您是否可以静态声明 C 样式字符串的多维数组,其中每行有不同数量的字符串。所以,像这样:

const char * arr[][3] =
    {
    {"bla", "bla", "bla"},
    {"bla", "bla" }
    };

在某些语言中,这被称为“锯齿状数组”。在 C 和 C++ 中,您可以这样做,尽管编译器会希望分配空间来存储所有行,就好像它们的长度相同,因此您最终不会初始化第二个数组的第三项。当我在 gcc 上对此进行测试时,该数组中的第三项设置为 NULL,但我不知道您是否可以指望它。

我认为您无法让编译器接受声明为 {1,2,3} 的数组作为 C 样式字符串。即使确实如此,并且您将它们视为字符串,您也会遇到问题,因为它们不是以空值终止的。

我同意其他海报,更好的方法可能是将这些数据存储在 XML、yaml 中,或者可能存储在您从中获取它们的数据库中,并在那里访问它们。如果您确实需要在源文件中静态创建这些,则最好声明一个对您的数据有意义的结构并初始化这些结构的数组。就像是:

typedef struct
{
  const char * somestring;
  const char * someotherstring;
  const unsigned int triple[3];
} Abbreviation;

const Abbreviation abb[] =
  {
    {"First Thing", "Second String", {1,2,3} },
    {"Other Thing", "Some String", {4,5,6} }
  };
于 2008-10-12T19:03:34.413 回答
1

原始数据大约为 1.7MB,它来自其他 2 个文件,一个来自我的雇主,另一个(Unihan.txt,大约 30MB)来自 Unicode Consortium。使用字典查找技术,使用前 128 个最长和最频繁出现的单词的字典,仅将数据大小降低到 1.5MB。我可以通过更智能的单词检测来改进这一点,目前这只是空间上的 VBScript Split()。

我没有任何关于使用准霍夫曼方法得到多小的数据,但我的猜测是它略小于 1MB。我希望将所有这些都放在二进制文件中,而不是作为一个单独的文件(尽管其他人可能会说不好的做法等)。然而,就目前而言,这一切都变得有点太难了,至少在 C 中。如果我可以弄清楚如何在 Euphoria 中创建 BSTR 的变体数组...

编辑:我使用了关于标准 UCN 的字典查找,并且由于字形描述的重复性而效果很好。Unihan 的问题在于你最终得到了对字形含义的描述;"VULGAR FRACTION ONE QUARTER"和之间有定性(和定量!)差异"A KIND OF PUNISHMENT IN HAN DYNASTY, NAME OF CHESSMEN IN CHINESE CHESS GAME(SIMPLIFIED FORM, A VARIANT U+7F75) TO CURSE; TO REVILE; TO ABUSE, TO SCOLD"

因此,从字典查找转向一些更强大的“压缩”技术。

(在有人说“那么 1.7MB 有什么大不了?”之前,我来自一个 16K RAM 很多的时代。无论如何我都有空间限制。)

于 2008-10-14T01:20:44.637 回答
0

传奇似乎还没有结束。我最终把所有东西都变成了一个参差不齐的int. 但是这样就失去了三元组背后的自我参照机制所依赖的项目的概念。

我现在正在考虑使用Euphoria而不是 C,因为它对不规则数组的出色支持。可以使用 Euphoria 构建标准 DLL,一旦我弄清楚如何交回 BSTR 的变体数组并编写 Typelib ...

请注意,我想我可以坚持使用 C 并将三元组存储为一行中的三个整数,并将字符串存储为转换为整数的指针。这将节省我对最初构建自引用字典的 VBScript 的相当大的重写。

于 2008-10-13T15:09:46.540 回答