Bitap算法 Bitap算法或称为shiftorshiftandBaezaYatesGonnet算法是一种字符串近似匹配算法该算法可判断给定的文本是否包含与定义模式近似相等的子字符串其中根据萊文斯坦距離  如果子字符串和定义模式彼此在给定距离K之内则该算法认为他们近似该算法预先计算一组位掩码其中每个位掩码的每一个元素都包含一个模式然后它可以通过按位操作以完成大部分工作 可以将Bitap算法作为Unix软件开发工具agrep的基础算法之一它由Udi Manber英语Udi ManberSun Wu和Burra Gopal开发Udi Manber和Sun Wu的原始论文对算法进行了扩展以处理一般正则表达式的模糊匹配 由于算法需要的数据结构它在小于固定长度通常是字长的模式上表现最佳但是一旦针对给定的字长m进行定义则其运行时间是完全可以预测的无论文本的结构或模式如何它的运行时间均为Omn 搜索精确字符串的Bitap算法在年由BálintDömölki发明并由R K Shyamasundar在年进行了扩充随后在年由Ricardo BaezaYates英语Ricardo BaezaYates和Gaston Gonnet英语Gaston Gonnet开发该算法也延伸到了处理字符通配符和不匹配字符年Manber英语Udi Manber和Sun Wu对其进行了扩展以处理插入和删除操作完全的模糊字符串搜索此算法后来在年由 BaezaYates和Navarro英语Gonzalo Navarro改进