公开(公告)号：CN114117145B

公开(公告)日：2024-08-02

申请号：CN202010876431.X

申请日：2020-08-27

Applicant: 东北大学秦皇岛分校

Inventor： 于长永 ,  赵楚

IPC: G06F16/903 ,  G16B30/10 ,  G16B50/30

Abstract: 本发明提供一种基于位运算和SIMD并行操作的字符串过滤方法，属于字符串匹配和比对领域。该字符串过滤方法在编辑距离矩阵中寻找计算规律，将编辑距离矩阵与偏移汉明掩码原理相结合，从理论上减少位操作的调用次数；计算过程中使用的树形计算结构可以有效的避免重复计算和降低空间复杂度；使用SSE指令集中的位操作函数进行操作，从底层加速位运算的速度，提高算法的实际运行速度。本发明有效解决现有技术中存在的问题，在进行字符串相似性查询前，过滤掉错误阈值不满足条件的字符串，避免消耗不必要的计算资源。本发明相比于现有技术，计算的字符串对可以具有不同的长度，具有更准确的过滤效果，更小的计算复杂度，并且不会错误过滤正确的字符串对。

公开(公告)号：CN114117145A

公开(公告)日：2022-03-01

申请号：CN202010876431.X

申请日：2020-08-27

Applicant: 东北大学秦皇岛分校

Inventor： 于长永 ,  赵楚

IPC: G06F16/903 ,  G16B30/10 ,  G16B50/30

Abstract: 本发明提供一种基于位运算和SIMD并行操作的字符串过滤算法，属于字符串匹配和比对领域。该字符串过滤算法在编辑距离矩阵中寻找计算规律，将编辑距离矩阵与偏移汉明掩码原理相结合，从理论上减少位操作的调用次数；计算过程中使用的树形计算结构可以有效的避免重复计算和降低空间复杂度；使用SSE指令集中的位操作函数进行操作，从底层加速位运算的速度，提高算法的实际运行速度。本发明有效解决现有技术中存在的问题，在进行字符串相似性查询前，过滤掉错误阈值不满足条件的字符串，避免消耗不必要的计算资源。本发明相比于现有技术，计算的字符串对可以具有不同的长度，具有更准确的过滤效果，更小的计算复杂度，并且不会错误过滤正确的字符串对。