如何高效地存储大量的n-gram？

Question

我正在从十六进制形式的二进制项中提取4元组，这意味着每个项最多可以有65535个不同的四元组。

我想将每个项与其四元组及其频率相关联，但我对如何存储所有内容感到困惑 - 这是我的第一次数据挖掘经验，我对最佳实践和常用工具毫无头绪。

我最初想到的是在关系型数据库中构建一个大表，其模式类似于（ITEM-NAME，GRAM1，GRAM2 ... GRAM65535），并在其中存储频率，但我发现由于列数太多，这种方法非常不切实际。

我知道一定有更好的解决方案，但我不知道该去哪里寻找。

有什么建议吗？

- gbr

---

生成的“矩阵”是稀疏的吗？也就是说，对于给定的项目，你能否期望平均至少有一半的GRAMn...GRAM65535值为0？ - p.marino

Answer 1

在我看来，存储ngram的最佳方式是前缀树。它被用于非常高效的库lingpipe。

树的例子：

 1. gr1
   1. gr2 (item1)
   2. gr3 (item2,item3,item4)
 2. gr3 (item1, tem2)
 3. gr2
  1. g3 (item5,item6)
  2. g4 (item1)

另一个选项是以倒排索引的格式存储： ngramm -> 项目

gr1 (item1, item2)
gr2 (item1, item3)
gr3 (item2, item3)
gr4 (item1, item2)

注意：第二个选项不会存储订单信息，这对于ngram非常重要...

- yura