稀疏矢量，它们是什么？

Question

我在内部使用Mahout API进行朴素贝叶斯分类器。其中一个功能是SparseVectorsFromSequenceFiles，虽然我尝试了旧的Google搜索，但我仍然没有说明稀疏向量是什么。 最接近我的解释是这个site这并没有帮助我理解tbh。

Answer 1

概念上，向量表示数组的泛化，即允许使用索引对其元素进行任意访问的数据结构。 Java的内置阵列Vector<T>和ArrayList<T>是实现“规则”（密集）向量概念的数据结构示例。

密集向量通过使用简单的公式baseAddress + index * elementSize将向量索引转换为内存地址来提供对其元素的恒定时间访问。这意味着内存中的大小与向量需要支持的最大索引成比例。

虽然这是可以接受的情况下，您希望放入一个向量中的元素数量和最高可能的索引相对接近。但是，如果您希望使用大范围的索引来索引相对较少的元素（例如，分布在具有100,000个索引的向量中的1,000个元素），则分配100,000个空间是很浪费的。您可以通过实现暴露向量接口的数据结构来节省内存，但会使用较少的内存用于内部表示。

链接中的示例显示了一种可能的实现。其他实现也是可能的，这取决于数据中索引的分布。如果索引是随机分布的，则可以使用HashMap<Integer,T>作为稀疏向量的后备存储。如果索引聚集在一起，则可以通过“页面”拆分索引空间，并将真实数组仅分配给需要的页面。这种实现与物理内存分配给虚拟内存空间的方式类似。