算法：如何从一个大字符串中搜索一个子串，可以有一定的模糊度。

[James369]

给定:
一个大字符串（不超过 100 万个字符）和一个查询子串（不超过 20 个字符）。
现在需要在这个大串中找到这些个子串，但可以设定匹配的模糊度：
比如：
当设定精确度为 100%时，则精确匹配这个子串。
当设定精确度为 80%时，可以只匹配子串的 80%内容。

好不好做？

[djyde]

还有一个前提条件需要确认：80%是指连续的 80%吗

[imn1]

排列还是组合？就是有没有顺序要求？
例如给出 abcde——
1. bacde 算 100%还是 80%？
2. eacdx 满足 80%么
3. aacde 呢？就是出现的次数只算一次匹配还是多次匹配？
……

你这个精确度的定义不同，影响很大
算法楼下继续，非我所长，轮子我只会用，不会造，🐶

[ipwx]

如果只是针对一个查询串：带边界条件的 edit-distance 算法？复杂度大概是 O(MN) 感觉。。。（ M=100 万，N=20 ）

如果针对很多很多查询串：把大字符串预先拆成重叠的 k-字符（比如 3 ），然后针对这些 k-字符建立倒排索引。然后用查询串的 k-字符去取出相关的索引，根据索引的先后位置和匹配次数你可以快速筛选出可能匹配的位置。最后针对这些位置做一次 edit-distance 最终确认。

[ipwx]

筛选这一步太麻烦了，楼下贤者可以补充。

[ipwx]

最后补充一句：因为倒排索引是根据位置排序的，多个倒排索引 + 不能超过 20 个字符误差范围这个条件能快速进行多路倒排索引的合并。合并过程可以用二分。。。总之是挺复杂的一个程序，但可以很快。

[ipwx]

…… 合并的过程不仅要用二分，可能还要用优先队列。优先队列是为了 O(1) 确定哪个倒排索引的下一个元素是最前面的，二分是为了跳过某个倒排索引因为太靠前了和别的倒排索引根本不可能相交的位置。

[James369]

@djyde 非连续，这种模糊确切说是一种意义上的相近。

[TimePPT]

你这模糊程度定义完全不科学。
「一定意义上的相近」如果是指语义相似度，就跟子串长度和字符没啥关系了。

[ericgui]

你这属于自然语言处理了，NLP is hard

[James369]

@ericgui 能不能用“正则表达式”来实现类似的效果呢，加上一些概率论的知识，分词，然后用同义词判断？

[LeeReamond]

感觉跟搜索引擎算法比较类似了，毕竟搜索引擎也可以抽象成标题是连续储存的字符串，通过搜索进行模糊定位，的一种业务。只不过当然现代搜索引擎处理的内容远比百万更长罢了。一个简单的 nlp 实现思路是，首先你需要对自己的字集进行 w2v，过程中可以有若干优化省略不表，在向量化以后每个向量就代表一个自然含义，且如果你的训练集合适，那么其自然含义有群聚性，比如 LZ 主题中的狗，小狗，小花狗，一条狗等等这些词会具有相近的向量位置。那么自然而然地近似一句话（可以解释为多个词向量的和），如果其自然语义接近，向量和落点肯定也是近似的，而后再进行准确+高效的位匹配就是储存层方面的工作。

只是简述一下思路，当然这只是理想情况下，你实际做过就知道难度。

[dbsquirrel]

jieba?

[4kingRAS]

这不就是搜索引擎吗，你用百度也没打正则表达式吧。不过我觉得倒也用不到 nlp，同 3 楼，编辑距离问题，https://zhuanlan.zhihu.com/p/80682302 总之就是得到一个相似性得分，按得分排序。

[7075]

用词向量试试

[ipwx]

那你的需求就是搜索引擎。。。直接找经典的信息检索教材就行。

[yolee599]

讲道理能做出来这个算法可以开公司卖算法了吧

[rrfeng]

一般都是分词索引，分词查询的。

[longkas239]

现有工具的话，今天刚了解到 Elasticsearch 。设定同义词：一条狗=一只狗。 检索的时候用 match_phase 类型, 通过 slop 参数控制模糊程度。 可以试一下

[James369]

@yolee599 #16 确切说也不能算是算法，我觉得应该有现成的轮子解决这个问题。 毕竟这是个比较普遍的需求。LS 有几位 V 友给了些思路，我觉得可以进一步研究看看。

[hzder]

ES