相似子串快速搜索

Question

我需要在一个巨大的字符串中寻找类似于给定模式的子字符串。源字符串可能长达100Mb。模式相对较短（10-100个字符）。问题是，我不仅需要找到精确匹配的子字符串，还需要找到与模式有几个字符不同的相似子字符串（最大允许错误计数作为参数提供）。

有没有什么办法可以加快算法速度？

- Vitas

---

你是在寻找一个针对单个查询进行优化的算法吗？还是一种索引策略，可以基于100MB源文本创建数据结构，以使所有类似的查询都得到优化呢？ - rwong

我在 Stack Overflow 上找到了一个类似的问题，其中提供了几种 Python 解决方案。 - Anderson Green

要在两个不同的字符串中找到相似的子串，我会使用序列比对算法。 - Anderson Green

Answer 1

1)与字符串搜索相关的算法有很多种。其中一种著名的算法是Knuth-Morris-Pratt算法。

2)您可能还想在使用的任何语言中检查正则表达式（“Regex”）。它们肯定会帮助您找到与原始子字符串“相似”的子字符串。

例如[Java]

String pat = "Home";
String source = "IgotanewHwme";

for(int i = 0; i < pat.length(); i++){
    //split around i .. not including char i itself .. instead, replace it with [a-zA-Z] and match using this new pattern.
    String new_pat = "("+pat.substring(0, i)+")"+ "[a-zA-Z]" + "("+pat.substring(i+1, pat.length())+")";
    System.out.println(new_pat);
    System.out.println(source.matches("[a-zA-Z]*"+new_pat+"[a-zA-Z]*"));
}

我认为很容易让它接受任意数量的错误计数。

- Ahmed Salama

---

Knuth-Morris-Pratt算法不是一种近似字符串搜索算法，但比特帕算法是。 - Anderson Green

Answer 2

听起来您想要使用模糊/近似字符串匹配。请查看维基百科页面，看看是否可以找到适合您需求的算法。

- Asgeir

Answer 3

你可以查看Levenshtein距离, Needleman-Wunsch算法和Damerau-Levenshtein距离

它们提供了评估两个字符串之间差异的度量标准（即添加、删除、替换等的数量）。它们经常用于测量DNA之间的变异。

你可以很容易地在各种编程语言中找到实现。

- ThibThib