algorithm - 模糊 .substring 文本匹配函数

Question

我正在寻找一种模糊substring 函数的方法。这是什么意思:

• 给出了两个字符串。
• 一个通常比另一个长。让我们称之为“空头”和“多头”
• 我们想要计算“多头”中出现了多少“空头”。
• 我们要考虑距离和顺序。就像如果“短”的元素出现在“长”中，它们优选以相同的顺序出现并且彼此靠近。

示例 1:

• 简短:“杂草被摧毁”
• Long:“用细菌基因改造的裁剪可以使植物对除草剂产生抗性，而杂草则被破坏，而转基因裁剪可以抵抗破坏性昆虫，从而减少对化学杀虫剂的需求。”

这是一个完全匹配，应该有 1.0 分。

示例 2:

• 简短:“杂草会被消灭”
• 长:同上。

这是一个模糊匹配，因为文本中出现了“weed”和“destroyed”，但没有“will be”。它仍然应该获得高分(比如 0.8)。

示例 3:

如果把“Short”设置为“destroyed will be weeds”，虽然原文中“destroyed”和“weeds”都出现了，但是分值应该很低，因为顺序变了。

对此有任何建议的实现吗？

最后一点是，没有唯一的评分方法。但我正在寻找一种算法。该算法的参数可以根据需要和要求进行调整。

Answer 1

这是一种可能的方法:

1. 对于第一个单词short(0)，将第一个indexOf存入long
2. 对于每个后续单词 short(n)，存储两者:a) long 中的第一个 indexOf，和 b)(首选)第一个 short(n) 索引，它出现时间不晚于首选 indexOf short(n-1) ).
3. 相应评分