本发明涉及计算机，尤其涉及一种可动态调整大小的近似成员查询方法及系统。
背景技术：
1、给定一个集合，判断一个元素是否是该集合的成员最直接的方法就是将集合中全部元素存储在计算机中，每当一个新元素出现时，将它与集合中的元素直接比较即可。这种方法虽然快速准确，但需要很大的存储空间，不利于海量数据的存储。近似成员查询(amq:approximate membership queries)数据结构也称为过滤器，能够用紧凑的空间来表示一个集合，从而估计性地回答元素是否是集合的成员，具有较高的查询效率，但存在一定的误报率，在数据库、存储系统、流数据处理等领域中具有广泛的应用场景。最经典的过滤器有bloom过滤器，cuckoo过滤器及其变体。举例来说，bloom过滤器通过维护一个位数组，将每个到来的新元素哈希到位数组中的多个位中，并将这几个位设置为“1”，以表示该元素为集合的成员，从而能够实现快速插入和查找，但不能实现删除操作。与bloom过滤器不同的是，cuckoo过滤器使用哈希表来存储集合中元素一一对应的指纹，其中，指纹是指元素的哈希值。cuckoo过滤器支持删除操作，并且可以更有效地处理过滤器的动态更改，提高了空间效率。
2、由于数据集合的大小不可预知，我们无法在初始时设置一个合适的过滤器大小，在数据元素操作的过程中，当过滤器无法插入新的元素时，需进行相应地动态扩展，也就是根据集合中的数据重新构建一个过滤器。能够实现动态扩展的过滤器称为动态过滤器。现有的动态过滤器的扩展方式可以分为两种：过滤器级别扩展和桶级别扩展。使用过滤器级别扩展的动态过滤器在初始时只设置一个基础过滤器（如bloom过滤器，cuckoo过滤器等），随着插入元素的增加，当基础过滤器无法插入新的元素时，会通过某种方式链接一个或多个相同或者更大的过滤器，如果再次无法插入新的元素，则会继续通过相同的方式链接新的过滤器，在不断扩展的过程中，元素查询消耗的时间会逐渐增大，误报率也会随之增加。使用桶级别扩展的动态过滤器在初始时设置的基础过滤器需要由一系列桶组成，这些桶映射在一个环结构里，到来的新元素会先哈希映射到同一个环结构中，进而顺时针寻找与之最近的桶进行插入。如若最近的桶无法插入新的元素，则构建一个新的桶哈希映射到元素和当前最近的桶在环中所处位置之间的某一位置，并将新元素插入到该桶中。这种方式做到了将元素与哈希映射到的桶之间的解耦，在增加桶时不会影响已插入的元素，但将元素插入桶前需要先在环结构中查找到桶的位置，具有显著的时间成本，存在效率低下的问题。
技术实现思路
1、为此，本发明所要解决的技术问题在于克服现有技术的近似成员查询数据结构扩展操作会影响其他操作性能的问题。
2、为解决上述技术问题，第一方面，本发明提供了一种可动态调整大小的近似成员查询方法，包括：
3、获取待操作数据；所述待操作数据的操作包括插入操作、查询操作、删除操作和段级别扩展操作；
4、对近似成员查询数据结构进行初始化；
5、将所述待操作数据输入至初始化完成的近似成员查询数据结构，并对所述待操作数据进行目标操作。
6、在本发明的一个实施例中，对近似成员查询数据结构进行初始化包括：
7、构建多个段；
8、构建一个查找表；所述查找表用于完成数据元素到段的映射，以使所述数据元素可以在对应的段中完成相关操作；
9、对所述查找表进行初始化，将所述查找表平均划分为多份。
10、在本发明的一个实施例中，所述待操作数据的插入操作步骤包括：
11、获取待插入数据元素的指纹，并通过所述查找表将所述待插入数据元素映射到对应的候选段；
12、判断所述候选段是否可以插入所述待插入数据元素；若是，则在所述候选段中找到第一候选桶和第二候选桶；若否，则对所述近似成员查询数据结构进行段级别扩展；
13、判断所述第一候选桶和所述第二候选桶中是否存在一个空槽；若是，则在空槽中存储所述待插入数据元素的指纹；若否，则启动驱逐操作。
14、在本发明的一个实施例中，所述驱逐操作为：
15、将所述第一候选桶或所述第二候选桶中被驱逐的指纹重新定位到其中的另一个候选桶中，直至找到一个空槽，或驱逐的指纹数量超出预设阈值。
16、在本发明的一个实施例中，对所述近似成员查询数据结构进行段级别扩展，包括：
17、添加一个扩展段；
18、更改所述查找表到段号之间的映射关系；
19、通过遍历所述候选段中存储的指纹，完成所述候选段与所述扩展段之间数据元素的移动。
20、在本发明的一个实施例中，通过遍历所述候选段中存储的指纹，完成所述候选段与所述扩展段之间数据元素的移动，包括：
21、将所述查找表中的条目进行区分；所述查找表中有多个条目指向候选段，将多个条目平均分为第一部分和第二部分，所述第一部分的条目指向所述候选段，所述第二部分的条目指向所述扩展段；
22、遍历所述候选段中存储的指纹，判断每个指纹是否由所述第二部分的条目映射到所述候选段，并将由所述第二部分的条目映射到所述候选段中的指纹移动到所述扩展段中。
23、在本发明的一个实施例中，所述待操作数据的查询操作步骤包括：
24、获取待查询数据元素的指纹，并通过所述查找表将所述待查询数据元素映射到对应的候选段；
25、在所述候选段中查找得到两个候选桶；
26、在两个候选桶中查找是否有一个槽中存储所述待查询数据元素的指纹；若是，则报告所述待查询数据元素属于当前数据集合；若否，则报告所述待查询数据元素不属于当前数据集合。
27、在本发明的一个实施例中，所述待操作数据的删除操作步骤包括：
28、获取待删除数据元素的指纹，并通过查找表将所述待删除数据元素映射到对应的候选段；
29、在所述候选段中查找得到两个候选桶；
30、在两个候选桶中查找存储有所述待删除数据元素的指纹的槽；
31、对存储有所述待删除数据元素的指纹的槽进行清空操作。
32、第二方面，本发明提供了一种可动态调整大小的近似成员查询系统，应用于上述任一项实施例所述的可动态调整大小的近似成员查询方法，包括初始化模块、元素插入模块、元素查询模块、元素删除模块，其中：
33、所述初始化模块用于，对近似成员查询数据结构进行初始化；
34、所述元素插入模块用于，获取待插入数据元素的指纹，并通过查找表将所述待插入数据元素映射到对应的候选段；判断所述候选段是否可以插入所述待插入数据元素；若是，则在所述候选段中找到第一候选桶和第二候选桶；若否，则对所述近似成员查询数据结构进行段级别扩展；判断所述第一候选桶和所述第二候选桶中是否存在一个空槽；若是，则在空槽中存储所述待插入数据元素的指纹；若否，则启动驱逐操作；
35、所述元素查询模块用于，获取待查询数据元素的指纹，并通过查找表将所述待查询数据元素映射到对应的候选段；在所述候选段中查找得到两个候选桶；在两个候选桶中查找是否有一个槽中存储所述待查询数据元素的指纹；若是，则报告所述待查询数据元素属于当前数据集合；若否，则报告所述待查询数据元素不属于当前数据集合；
36、所述元素删除模块用于，获取待删除数据元素的指纹，并通过查找表将所述待删除数据元素映射到对应的候选段；在所述候选段中查找得到两个候选桶；在两个候选桶中查找存储有所述待删除数据元素的指纹的槽；对存储有所述待删除数据元素的指纹的槽进行清空操作。
37、在本发明的一个实施例中，还包括段级别扩展模块用于，添加一个扩展段；更改所述查找表到段号之间的映射关系；通过遍历所述候选段中存储的指纹，完成所述候选段与所述扩展段之间数据元素的移动。
38、本发明的上述技术方案相比现有技术具有以下有益效果：
39、本发明所述的一种可动态调整大小的近似成员查询方法及系统，其设计了一种可以动态调整大小的近似成员查询方法，该方法为使用段级别扩展的动态过滤器，能够动态调整大小以适应不同数量大小的集合，同时还能确保在调整时其他对数据结构进行的操作不被影响。
1.一种可动态调整大小的近似成员查询方法，其特征在于，包括：
2.根据权利要求1所述的可动态调整大小的近似成员查询方法，其特征在于，对近似成员查询数据结构进行初始化包括：
3.根据权利要求2所述的可动态调整大小的近似成员查询方法，其特征在于，所述待操作数据的插入操作步骤包括：
4.根据权利要求3所述的可动态调整大小的近似成员查询方法，其特征在于，所述驱逐操作为：
5.根据权利要求3所述的可动态调整大小的近似成员查询方法，其特征在于，对所述近似成员查询数据结构进行段级别扩展，包括：
6.根据权利要求5所述的可动态调整大小的近似成员查询方法，其特征在于，通过遍历所述候选段中存储的指纹，完成所述候选段与所述扩展段之间数据元素的移动，包括：
7.根据权利要求1所述的可动态调整大小的近似成员查询方法，其特征在于，所述待操作数据的查询操作步骤包括：
8.根据权利要求1所述的可动态调整大小的近似成员查询方法，其特征在于，所述待操作数据的删除操作步骤包括：
9.一种可动态调整大小的近似成员查询系统，应用于上述权利要求1-8任一项所述的可动态调整大小的近似成员查询方法，其特征在于，包括初始化模块、元素插入模块、元素查询模块、元素删除模块，其中：
10.根据权利要求9所述的可动态调整大小的近似成员查询系统，其特征在于，还包括段级别扩展模块用于，添加一个扩展段；更改所述查找表到段号之间的映射关系；通过遍历所述候选段中存储的指纹，完成所述候选段与所述扩展段之间数据元素的移动。
