java - 基于唯一子字符串对字符串

Question

我有两组字符串，如果可能的话，需要通过每对中的相同子字符串进行匹配(下面示例中的粗体文本；粗体/大写仅在此处进行强调，没有办法通过查看来识别关键子字符串在其自身的列表元素中)，它们在每个列表中都是唯一的。文本的其余部分 (lorem ipsum) 可能对许多元素来说是通用的，也可能是完全独特的。

列出一:

1. “Lorem ipsum dolor sat amet，CANDY BAR consectetur adipisicing 精英，”
2. "sed do eiusmod CANDY CANE tempor incididunt ut labore et dolore 麦格纳”
3. “sed do eiusmod tempor HOMER incididunt ut labore et dolore 麦格纳”
4. “Lorem ipsum dolor sat amet，consectetur adipisicing PICKUP 卡车精英，”
5. “ullamco Laboris nisi ut aliquip ex ea commodo consequat.Duis aute”

列出两个:

1. “sed do eiusmod tempor inciditunt HOMER ut labore et dolore magna”
2. “aliqua。Ut enim ad minim veniam，CANDY BAR quis nostrud exeritation”
3. “aliqua。Ut enim ad minim veniam，quis nostrud CANDY CANE练习”
4. “irure dolor in reprehenderit in voluptate velit esse cillum dolore”
5. “Lorem ipsum dolor sat amet，consectetur adipisicing 皮卡车 elit”，

从下面的示例文本中匹配的是:1-2； 2-3； 3-1； 4-5

列表一中的元素 5 和列表 2 中的元素 4 与任何内容都不匹配。

Answer 1

如果您处理的数据总量相对较小，那么已经建议的解决方案(使用 .contains() 或正则表达式)可能是最实用的。 下面是当数据量很大时的一种方法。

解决方案的关键部分是使用后缀数组。后缀数组是文本(或多个文本的串联)。

在您描述的示例中，这将涉及仅构建两个集合之一的串联文本的后缀数组。我假设我们对集 2 执行此操作，因此我们将使用唯一的分隔字符连接所有句子(我在下面选择了哈希字符 #):

 sed do eiusmod tempor incididunt HOMER ut labore et dolore magna#aliqua. Ut enim ad minim veniam, CANDY BAR quis nostrud exercitation#aliqua. Ut enim ad minim veniam, quis nostrud CANDY CANE exercitation#....

接下来，您将构造该字符串的后缀数组，以及最长公共(public)前缀数组 (LCP)。 这两种数据结构都可以使用如果文本量不是很大，则可以使用蛮力方法。或者，有一些库可以更有效地构建它们，例如 jSuffixArrays .

最后，迭代集合1的句子，并在每个句子中遍历相关标记的候选起始位置(可能只有空格或标点符号后面的单词)并搜索集合的后缀数组2 对他们来说。 当 LCP 数组可用时，搜索后缀数组可以在 O(n+m) 时间内完成(n 是集合 2 的连接字符串的长度，m 是您要查找的候选字符串的长度)正在寻找)使用 classical search algorithm by Manber and Myers ，但如果这仍然太慢，有一些改进的方法可用，例如由 Navarro and Mäkinen 2007 描述.

对于您找到的每个匹配项，后缀数组可以轻松提供有关字符串在集合 2 中出现的频率以及在多少个不同句子中出现的信息。如果需要，我可以在编辑这篇文章时详细说明如何执行后者。