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

[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

[zviacx]

在生物信息学中这个问题叫全局比对：给定短的基因链，在基因组上做有模糊的查找。

这个挺多算法的，可以看看适不适合这个输入。

[sailgu]

@zviacx blast 就是干这个的了😂，毕业后搞了 2 年生物信息，果断跳坑。

[igoist]

我抛砖引玉下吧，有兴趣的可以自己加参数去做精度的设置、优化：

(() => {
const fuzzyMatches = (fuzzy, text) => {
fuzzy = fuzzy.toLowerCase();
text = text.toLowerCase();

let tp = 0; // text position / pointer
let matches = [];

// 这边随你去优化
for (let i = 0; i < fuzzy.length; i++) {
const f = fuzzy[i];

for (; tp < text.length; tp++) {
const t = text[tp];
if (f === t) {
matches.push(tp);
tp++;
break;
}
}
}

return matches;
};

// let r = fuzzyMatches('路边有一条狗', '路边有一只狗'); // r = [ 0, 1, 2, 3 ]
// let r = fuzzyMatches('路边有一条狗', '路边有一只小狗'); // r = [ 0, 1, 2, 3 ]
// let r = fuzzyMatches('路边有一条狗', '路边有一只小花狗'); // r = [ 0, 1, 2, 3 ]
let r = fuzzyMatches('路边有一条狗', '道路旁边有一只小狗'); // r = [ 1, 3, 4, 5 ]

console.log(r);
})();

[iFlicker]

楼上说的对 这属于 NLP 范畴了

[leven87]

楼上说了很多，我来说下吧，这个不属于子字符串了。就是一个 NLP 的范畴，包括关键字提取，如你这个就是提取"路"，"旁边"，“狗”。 或者句子主干提取吧，“路边有狗“。 然后你那个要查找的文章就是语料，也可以提取关键字或者句子主干吧。 然后两者做一个这样的查找，匹配，距离计算（各种框架算法）。看能不能匹配上？

[leven87]

等待 NLP 高手解答，不过应该人家也没时间逛论坛。

[learningman]

我帮你叫了个搞 NLP 的，不知道他来不来

[minilyn]

看楼主的本意如果是「想找到一些相关联的子串」，更像是需要做一个搜索引擎的基础功能。
简化的描述一下业界常用的方案就是基于 ES，将候选集做实体识别 /打标签 /分词等，放入倒排索引中，然后将 input 字符串做同样的处理，然后就可以用 实体 /分词 /标签等信息去做 match 了，模糊度相关性等要求 可以在打分公式和过滤条件限制。 单纯的子字符串匹配是没办法很好的满足相关联的条件的，比如「路边有一条狗」和「有一个狗在路边」这种 pair 对

[rus4db]

提供一个参考概念：布隆过滤器（ Bloom Filter ）

[Arthur2e5]

不走 NLP 处理的话就是字符串近似匹配。有几个不同版本的 agrep 都可以拿来看看，直接用的话推荐试试 TRE agrep 。

[kylejustknows]

1, 字符串扩大: 比如说你要 80% 准确率, 那么你搜索 8 个字的时候, 定义对比原文字符长度为 10 个.
2, 快速过滤: 大段文字 10 个字一组, 如果这 10 个字里一个搜索字都没有或者只有一两个(小于一半), 迅速跳过.
3, 精选结果. 当遇到一组(10 个)文字中有 4 个或更多字匹配, 则这一组 和其前后两组, 从第一个匹配字开始, 尝试更细致的分组. 最坏情况是分成了 10+10+10 组长度为 10 的文字, 这 30 串文字中, 任何一组匹配了超过 8*80%= 大概 6 个搜索字, 那么这一组这 10 个字, 从第一个匹配字到最后一个匹配字之间的那段话, 就是你想要的结果.

[Xs0ul]

在不用 NLP 的情况下，如果要搜“路边有一只狗”，那“路边有一条狗”和“路边有一只猫”与它的相似程度是一样的（按 edit-distance ）， 因为都只差一个字。

但是单单 NLP 并不能自动解决复杂度的问题。Embedding 只能提供更好的相似度估计，比如“只”和“条”相似度可能是 0.9，但“狗”和“猫”是 0.6，还是需要搜索引擎领域的知识。

[James369]

@igoist #23 你的这个 fuzzyMatches 操作不错，很好用。但我想问一下，能否返回匹配串在原始大串中的具体位置呢？

[igoist]

@James369

昨天其实没仔细审题，NPL 我也没研究过，大意了，好想撤回消息啊😂

以查询短字串、匹配单个为例，前面的 fuzzyMatches 稍微改一下，调整下测试用例，可以有下面这样的结果：

[ 15, 16, 17, 18 ] 路边有一

[ 18, 19, 20 ] 边有一


按照你的需求，还得判断结果区间能否接受，之后要确定具体位置，就是楼上说的，还需要有个 fNPL 去分别处理区间左右两侧内容，这是左侧：

fNPL(index = 15, distance = n, originalText, dictionaryForLeft)

fNPL(index = 18, distance = n + 1, originalText, dictionaryForLeft)

右侧同理，你加油！/逃

[bigtang]

向量数据库就是干这个的吧？