2

我想提取Google N-Gram 数据集以用于某些商品硬件。问题是这些小型服务器无法处理需要存储的数据大小。

这让我开始思考其他基于文本的大型系统（如 WordNET 或搜索引擎）如何处理这个问题。我想知道是否有一种方法可以规范化数据，但仍使其成为可搜索的格式？

回到 N-Gram，我的想法是将 1-Gram 中的所有单词与 ID 一起存储在数据库中。然后使用该 ID 在 +2 Gram 链中创建关系，就像在社交网络中跟踪朋友关系一样 - 两个 id 作为行。

TABLE Words
{
    id
    word
}

TABLE TWOGRAM
{
    first_word_id
    second_word_id
}

TABLE THREEGRAM
{
    first_word_id
    second_word_id
    third_word_id
}

TABLE FOURGRAM
{
    first_word_id
    second_word_id
    third_word_id
    forth_word_id
}

有没有更有效的方法以紧凑的方式存储所有这些数据？

也许不是压缩文本，而是可以对单词对（或序列）进行散列处理，以实现更小的存储大小，同时仍然可以像密码一样进行搜索。

4

2 回答 2

1

处理这种情况的典型方法是将数据分块成小块（例如 2K 行），按列对块内的数据进行分组，然后使用快速压缩算法压缩转换后的块。节省的费用可能非常可观。

[编辑] 根据要求提供更多细节：这里的目标是处理小的压缩数据块，因此有必要将内存需求保持在合理的水平。“合理”取决于您的目标系统，这就是为什么它可能是 256 行、2K 或 8K。

然而，每一行都有几个字段。所以直接压缩不会带来显着的节省（例如，zip 是“仅”x5）。幸运的是，这些字段之间的分隔符是众所周知的（0x09），因此可以检索每个字段的开始和结束。

这个想法是将所有“字段 1”组合在一起，然后是“字段 2”，然后是“字段 3”，依此类推。如果从 .csv 文件中提取的块是 2K 行，我们知道每种类型都有 2K 字段。

然后，一个简单的快速压缩算法将在这个转换后的结构上创造奇迹。相关性非常强，因为连续的字段往往有很多共同点。对于此类数据，10 倍压缩比不足为奇。谷歌 N-Gram 数据集可能更受欢迎。

由于您的目标是将尽可能多的数据保存到内存中以进行搜索，因此建议将每个块保持足够小（大约在 256 和 8K 之间），并使用非常快速的压缩/解压缩算法。这样，解压缩将足够快，成为算法中微不足道的一部分。例如，像 LZ4 这样的东西提供了大约 1GB/s 的解压缩速度。

关于搜索：这完全取决于您要搜索的内容，但如果是关于找到精确的 N-gram，那么我们很幸运，因为它们已经按字典顺序排序。

在这个阶段，将每个块的第一个 N-gram 存储到一个表中就足够了。当搜索一个特定的 N-gram 时，只需要找出它在哪个块中。块的第一个 N-gram 必须是 <=。下一个块的 N gram 必然 >。如上所示，解压缩块应该是算法中无关紧要的部分。

即使有 2K 行的块，你也可能有很多“header N-gram”要存储，所以一个微不足道的气泡搜索可能会很长。建议使用树或枢轴搜索。

加载块后，仍然需要对其进行搜索以找到合适的 N-gram。可以使用与以前相同的策略（将 N-gram 加载到表中，然后在其中进行枢轴搜索）。

于 2011-10-10T15:15:12.997 回答
0

与其为每对或 2+ 个分组一遍又一遍地存储 3600 亿个 1 克 - 将单词存储一次 - 然后使用更小的整数来表示单词似乎是一个更好的选择。

（我在下面总结了我的估计。）

很难确定整数在这里是更好的选择。您需要更好地估计您需要多少磁盘空间、您拥有多少磁盘空间以及您可以负担多少磁盘空间。

统计数据告诉我们，英语单词的平均长度是 5.1 个字符。在您的应用中，这与 5.1 字节相同。两个字的平均长度约为10.2字节；两个整数的长度为 8 个字节。

文件编号 71（随机选择）中大约有 6600 万个 2 克。在每个条目 10.2 字节的情况下，您正在查看该文件的大约 673 兆字节。（假设您只存储单词，而不是计数。）对于 100 个 2 克文件，您应该需要 52 到 67 个演出（忽略索引）。为我们深刻的无知增加 50%。100 个演出将涵盖 2 克。

如果你用单词存储计数，这个文件是 1.6 gigs，其中 100 个应该是 160 gigs 左右。所以我们有 100 到 160 个演出的范围来存储 2 克。

我将估算索引所需的空间留给您。

整数每个字节省 2.2 个字节。但是存储两个整数意味着您总是需要进行两次连接才能取回真实数据。（为 5 克存储五个整数意味着您需要五个连接来获取真实数据。）存储单词本身不需要连接来获取真实数据。

如果您还存储计数，则可以通过将外键存储到 ngram 而不是使用单个单词来节省空间。所以你可以存储

ngram_id  ngram_text
--
143564    five pounds

在一张桌子上，并且

ngram_id    year    match_count  page_count  volume_count 
--
143564      1999    4            3           3
143564      2000    2            2           1
143564      2001    1            1           1
143564      2002    1            1           1
143564      2003    2            2           2
143564      2004    1            1           1
143564      2005    6            6           5
143564      2006    30           21          17
143564      2007    39           37          26
143564      2008    44           41          28

在另一个。

对于特定的 2 克，文本占用 11 个字节，整数占用 4 个字节。10 行中的每一行节省 7 个字节，70 个字节。需要一次连接才能获取真实数据。对于这种方法，我估计所有 2 克大约需要 130 个演出，不包括提供外键的索引和表。

基于 6600 万行的 100 个文件，我对存储 2 克所需空间的估计摘要。不包括索引空间和一般存储开销（取决于 dbms，这些开销可能很大。）

                           row_len  gigabytes  joins
----------------------------------------------------
words        with counts     163.2      1,077      0
two integers with counts     128.0        845    2-5

words        without counts   10.2         67      0
two integers without counts    8           53    2-5

one integer  with counts      20          132      1
one integer  without counts    4           26 (for completeness, but not really useful)

如今，多 TB 驱动器阵列并不昂贵。大家会靠这个赚钱吗？

于 2011-10-10T18:37:01.117 回答