模糊快速字符串匹配和索引算法

Question

我需要尽可能快地在一个非常大的字符串中查找一组子字符串（每个约32个字符）。 我需要进行模糊搜索。

什么是最好的算法？ 我尝试了扫描整个大字符串以查找小字符串，并在每个步骤中检查Levenshtein距离，但这需要很长时间。

- AVEbrahimi

---

@NeerajJain String.contains() 不是模糊匹配方法。它只搜索精确匹配。 - AVEbrahimi

一些讨论在https://dev59.com/jHE85IYBdhLWcg3wNgrk https://dev59.com/F3RC5IYBdhLWcg3wVvnL http://stackoverflow.com/questions/16351641/algorithms-for-fast-string-approximate-matching - Thilo

你需要多快？给我们一个目标。 - bvdb

这个“模糊”的想法是你为了提高性能而提出的想法吗？还是它是一个严格的要求，意味着单词“abcde”也应该与“acbde”匹配。这些细节非常重要。 - bvdb

请给我们一些关于应用程序的背景信息。这可能是相关的。例如，100k的单词是否总是相同的，32个字符的子字符串是否来自于Web服务调用？...现在太模糊了，无法给出一个好的答案。 - bvdb

Answer 1

请查看BLAST算法（http://en.wikipedia.org/wiki/BLAST），它用于序列搜索（例如DNA搜索）。基本问题与您的问题非常相似。简而言之，您需要索引短字符串，并找到匹配丰富的区域，在该区域进行更多的计算密集型搜索。

- ElKamina

Answer 2

如果我理解你的要求正确（你想在一个大字符串中找到与给定长度为32的一组字符串相等的子序列），并且你的字母表大小合理（例如字母、数字和标点符号），那么可以按照以下步骤操作：

1. 找到每个字母的第一次出现。

2. 对于字符串中的每个位置，在该位置之后找到每个字母的下一个出现位置（可以通过从末尾扫描每个字母来以O(l * n)的时间复杂度完成，其中l是字符串的长度，n是字母表的大小）

3. 对于你的一组字符串中的每个字符串，找到该字符串的第一个字母的第一次出现，然后从该位置开始查找你的字符串中第二个字母的第一次出现等。

这样，你需要花费O(l * n)的时间进行预处理，但对于你集合中的每个小字符串，你只需要做O(m)的工作，其中m是该字符串的长度。

- Ishamael