稀疏查找表的用处
稀疏查找表(Sparse Look-Up Table, SparseLUT)适用于如下场景:
在一个实际场景中,面临这样一个问题:如何根据一个特征序列,索引到一个值。
例如,
- 特征序列为“是水果,体积很大,绿色,有条纹,甜,水分多”,根据这些特征应索引到值“西瓜”,
- 特征序列为“是水果,体积不大,红色,没有条纹,甜或酸,水分适中”,根据这些特征应索引到值“苹果”,
- 特征序列为“是水果,体积不大,橙色,没有条纹,甜或酸,水分适中”,根据这些特征应索引到特征“橘子”。
如果我们将“是/不是水果”用“
-
$[0,0,0,0,0,0]\rightarrow$ 西瓜, -
$[0,1,1,1,[0,1],1]\rightarrow$ 苹果, -
$[0,1,2,1,[0,1],1]\rightarrow$ 橘子。
那么,当给出特征序列“
稀疏查找表正是用于实现类似上述特征匹配过程的一个工具。形式上说,所面临的问题可抽象为,给定形如
(式1)
的一系列特征序列及其对应的值时,构建一个有向无环图,该图占用尽可能少的存储空间存储数据,并确保在给定形如
的特征序列时,计算机通过在该有向无环图上搜索,能在常数时间访问到对应的值。式1中,每一行的右箭头左边的对象被称为“特征序列”,右边的对象被称为“值”;每个特征序列由一系列整数的列表构成,其中的每个列表被称为“特征列表”,特征列表中的每个整数被称为“特征”;特征序列和值的数量为
当一个特征列表中的特征的数量仅为
稀疏查找表的优势
在说明稀疏查找表的优势前,我们首先介绍一种图的简化表示方式。若一组结点与另一组结点之间两两连接,那么,我们可以将每组结点称为一个“结点集”,在图表示中,用一个箭头连接两个结点集对应的结点。例如,结点集
其简化表示为
上面的例子中,若输入为
-
$[0,0,0,0,0,0]\rightarrow$ 西瓜, -
$[0,1,1,1,[0,1],1]\rightarrow$ 苹果, -
$[0,1,2,1,[0,1],1]\rightarrow$ 橘子。
其对应稀疏查找表的图表示为
这个例子中,稀疏查找表呈现出了树的结构。然而,稀疏查找表并不一定是树,而通常是有向无环图。例如,若输入为
-
$[[0,1,2],0,1,[0,1,2]]\rightarrow A$ , -
$[[0,1,2],0,[0,1,2],[0,1,2]]\rightarrow B$ , -
$[[0,1,2],1,[0,1,2],[0,1,2]] \rightarrow C$ , -
$[0,2,[0,1,2],[0,1,2]] \rightarrow D$ 。
则其对应稀疏查找表的图表示为
可以看出,黄色标记的结点集有多个父节点,这使得该图不是树。
稀疏查找表正是通过尽可能地“复用”结点来节约存储空间的。
为了实现与稀疏查找表相同的功能(即“查找”的功能),最常见的技术方案是使用高维数组来存储一张“查找表”,并将所有可能的特征对应的值存储在数组中,通过数组下标访问的方式来索引值。例如,对于上述水果的例子,须在内存中存储一个形状为
例如,假设我们需要用一个长度为20的列表作为特征序列,用于索引到特定的值,而特征序列中的每个数的取值范围是0至9之间的整数,每个待访问的值的类型是char型(占用1字节内存),则这张查找表将需要
一种改进的存储方式是利用稀疏表(Sparse Table)来存储。稀疏表是利用数据在某一维度上的稀疏性来压缩数组的存储空间。例如,对于图5a所示的稠密存储的表,由于数据在0、3、6、8列是稠密的,而在其他列都为0,因此可将那些全为0的列抛弃,而只保留含有1的列,并将列标存储下来,得到如图5b所示的稀疏存储的表。
另一种更为通用的稀疏存储方式是利用类似于前缀树(Trie)来存储。前缀树是一种树状的数据结构,它原本用于字符串匹配。上述场景中,给定多个特征序列,前缀树将那些“前缀”相同的部分合并为一个结点,由此来压缩存储空间,并实现值的常数时间的访问。上述水果的场景对应的前缀树如图6所示(尽管这不是严格的前缀树)。
然而,传统的稀疏表的存储方式,以及前缀树,并不能完全适用于某些场景。例如,如果一个特征是“
使用方法
通过以下命令即可安装稀疏查找表的Python包:
pip install sparse_lut
下面介绍使用稀疏查找表的方法。
首先,通过如下代码初始化稀疏查找表
from sparse_lut import SparseLUT
# initialization
lut = SparseLUT((3, 3, 3, 3, 3))
其次,通过add
方法,向稀疏查找表中加入多条特征序列,例如
# adding feature-lists
lut.add([[0,1,2], [0,1,2], [0,1,2], [0,1,2], [0,1,2]], "A")
lut.add([[1,2], [0], [0,1,2], [0,1,2], [0,1,2]], "B")
lut.add([[1,2], [1], [0,1,2], [0,1,2], [0,1,2]], "C")
第三,构建稀疏查找表。如果要进一步进行可视化,则需要传入参数 False
,否则,程序构建好后会将相关的中间变量清空,以至于无法进行进一步的可视化。
# building the sparse-lut
lut.build(False) # set True is visualization is not required
第四,如果需要可视化,则通过draw
方法进行。 上述例子的可视化结果如图8所示。
图8
第五,通过下标访问。例如
# accessing the value
result = lut[0,1,0,0,0]
print(result)
程序会打印“OrderedSet(['A'])”,即成功访问到了对应的值。