让我们考虑一个查询集 Q 和一个更大的超集 S。Q 的每个元素都存在于 S 中。目标是使用 S 的最小数量的（连接的）“组件”来表示 Q。
这是一个具体的例子：Q={我爱法国和葡萄酒} S={（我住在这里），（我爱你和她），（法国很美），（奶酪和葡萄酒）}
Q 的解决方案可能： - “我”来自“我住在这里” - “爱”来自“我爱你和她” - “法国”来自“法国很美” - “and”来自“我爱你和她” - “wine”来自“cheese and wine” 这导致5个“components”，即“I”、“love”、“France”、“and”、“wine”
更好的解决方案是： - “I love”来自“我爱你和她” - “France”来自“France is beautiful” - “and wine”来自“cheese and wine” 这会产生 3 个“组件”，即“I love”、“France”、“and wine”，这可能是这个例子的最佳解决方案。我们希望尽量减少“组件”的数量。
有谁知道如何调用这种算法？我在文本解析、文本挖掘等方面进行了搜索，但没有找到合适的内容。
我将此问题描述为“最小间隔覆盖”；我不确定这是规范名称，但我不是第一个使用该短语的人。
有一个有两个阶段的有效算法。在第一阶段，确定出现在源中的查询的最大子字符串。对于每个这样的子字符串，输出第二阶段的间隔。在第二阶段，通过重复选择覆盖最低未覆盖位置的最高端点的区间来找到最小基数覆盖。
在你的例子中
Q=(I love France and wine)
S={(I live here), (I love you and her), (France is beautiful), (cheese and wine)}
间隔是，从一开始，（1, 2）“我爱”，（3, 3）“法国”，（4, 5）“和葡萄酒”。哎呀，现在第二阶段是微不足道的。假设相反
Q=(a b c d)
S={(a b), (b c), (c d)}
那么间隔是 (1, 2) "a b", (2, 3) "b c", (3, 4) "c d"。未覆盖的最低值为 1；我们取 (1, 2)。未覆盖的最低值为 3；我们取 (3, 4) 超过 (2, 3) 因为 4 > 3。
编辑添加：
瓶颈很可能是第一阶段。如果这是一个问题，那么有一个算法：构建一个包含源语句的后缀树。然后，根据查询字符串遍历树。除非查询逐字出现在源代码中，否则您最终会尝试使用不存在的链接；在这种情况下，当前最大间隔结束，您需要按照后缀链接，直到您可以再次取得进展。（计算生物学家，我描述的是哪种算法？）
您所描述的听起来像集合覆盖问题，其中您有一个主集（在您的情况下为查询）和一组集合（您的组件）可供选择，目标是覆盖主集的每个元素. 这个问题已经得到很好的研究，但不幸的是它是 NP-hard 并且没有已知的多项式时间算法。此外，用于集合覆盖的最佳多项式时间逼近算法在最坏情况下只能达到真实解的 O(log n) 因子。
如果您正在处理小查询或少量组件，您可以通过列出所有子集并检查哪些子集有效来强制回答。但是，对于大型查询或大量组件，您不应该期望有效地获得准确的答案。
希望这可以帮助！