离散化步骤
【离散化简介】
★ 离散化是一种数据处理的技巧,本质上可以看成是一种“哈希”,其保证数据在哈希以后仍然保持原来的“全/偏序”关系。用来离散化的可以是大整数、浮点数、字符串等等。
★ 通俗地讲,离散化可以在保持“元素之间相对关系”的前提下,实现数据压缩。
【离散化步骤】
简单而言,常用的离散化算法步骤为“提取、排序、去重、映射”。
【离散化示例】
例如,一块宣传栏,横向长度的刻度标记为1~10,贴4张不同颜色的与宣传栏等宽的海报,且后者覆盖前者,问最后能看见几种颜色的海报。其中,4张不同颜色的海报对应于宣传栏上的刻度分别为 [1, 3]、[2, 5]、[3, 8]、[3, 10]。离散化步骤如下:
(1)提取:提取4张海报的8个端点 1 3 2 5 3 8 3 10
(2)排序:从小到大排序4张海报的8个端点,得:1 2 3 3 3 5 8 10
(3)去重:对 1 2 3 3 3 5 8 10 去重,得 1 2 3 5 8 10
(4)映射:将原来的8个端点,映射到去重后的6个端点上
则,原来的4个区间 [1, 3]、[2, 5]、[3, 8]、[3, 10] 将映射为 [1, 3]、[2, 4]、[3, 5]、[3, 6]
。显然,宣传栏的长度从10压缩到6。
【参考文献】
https://oi-wiki.org/misc/discrete/
https://blog.csdn.net/m0_67717626/article/details/136156476