稀疏向量，它们是什么？

Question

我正在使用内的Mahout作为一个朴素的贝叶斯分类器。其中一个函数是SparseVectorsFromSequenceFiles，虽然我尝试过旧的Google搜索，但我仍然不明白稀疏向量是什么。我所得到的最接近的解释是这个站点，它没有帮助我理解tbh。

Answer 1

从概念上讲，向量表示数组的泛化，即允许使用索引任意访问其元素的数据结构。Java的内置数组、Vector<T>和ArrayList<T>是实现“规则”(密集)向量概念的数据结构的例子。

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

虽然这是可以接受的情况下，当您希望放在向量中的元素数量和最高可能的索引是相对接近的。但是，如果希望使用范围较广的索引来索引相对较少的元素(例如，分配100000个空间的1000个元素分散在一个向量上，100万个索引)，那么分配100000个空间是浪费的。您可以通过实现一个数据结构来节省内存而牺牲CPU周期，该数据结构公开了一个向量的接口，但在其内部表示中使用了较小的内存量。

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