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

[James369]

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

好不好做？

[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]

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