给定一个文本串T和模式串P,字符串匹配就是从一个T中找到所有和P相同的子串。字符串匹配的应用涉及到生物信息学、文本编辑、模式识别、自然语言处理和搜索引擎等领域。随着互联网技术的发展,数据来源的差异性导致了不确定数据的产生。本文重点研究生物信息学领域的不确定字符串匹配问题,研究内容如下。首先,通过对现有方法进行深入分析,发现了现有方法存在索引构建时间长,索引规模大的问题。其次,针对生物信息学领域中字符种类较少的特点,提出了空间代价为字符种类乘字符串长度的索引USAL。在USAL上提出了积极字符和消极字符的概念,基于积极字符并结合贪心思想和范围最值查询RMQ提出了一种高效的字符串匹配算法GUSM。USAL在每个位置记录了每种字符的出现概率,字符串匹配时,根据给定的查询概率阈值用RMQ以O(1)时间返回当前划分区间中概率最大的积极字符位置,然后对该位置进行概率阈值的验证,最后返回正确的结果。为了提高积极字符位置的过滤效果,提出了基于最小概率字符和随机选择字符的过滤策略。再次,为了进一步增强字符串匹配阶段的过滤效果,结合Bitmap思想提出了一种小规模位图索引BI。BI可以对USAL上的位置概率进行位映射,基于BI提出了一种高效字符串匹配算法BUSM,字符串匹配时,将子串匹配操作转化为BI上的位操作,然后验证候选结果集合,最后返回正确的结果。为了提高BUSM在概率阈值验证阶段的效率,提出了多维位图索引MBI,通过减少候选结果集合的规模,从而提高了算法执行效率。最后,对于多个不同特征的真实数据集和人工合成数据集进行实验,验证了本文提出算法的高效性。