logo标签列表

如何高效地在一组字符串中找到特定长度的相同子串？

stringalgorithm
6

我有一个集合 S，通常包含10-50个长字符串。为了说明问题，假设每个字符串的长度在1000到10000个字符之间。

我想找到特定长度 k 的字符串（通常在5到20的范围内），它们是S中每个字符串的子字符串。这显然可以使用朴素方法完成 - 枚举S[0]中的每个k长度子字符串，并检查它们是否存在于S的每个其他元素中。

是否有更有效的方法来解决这个问题？据我所知，这与最长公共子序列问题有一些相似之处，但我对LCS的理解有限，不确定如何将其调整为我们将期望公共子字符串长度限制为k的情况，或者是否可以应用子序列技术来查找子字符串。

2
请说明 - 您需要子字符串（连续片段）还是子序列？ - MBo
子串。谢谢你指出来，我没有意识到这两者之间的区别。 - Samantha
字符串中的字符范围是什么？ - RaffleBuffle
ASCII在这里足够了。 - Samantha
4个回答
3
这里有一个相当简单的算法，应该比较快。

  1. 使用滚动哈希算法，如Rabin-Karp字符串搜索算法中所述，构建一个哈希表H0，其中包含S0的所有|S0|-k+1长度为k的子字符串。由于每个哈希都可以从前一个哈希中在O(1)时间内计算出来，因此大约需要O(|S0|)的时间，但如果存在冲突或重复子字符串，则需要更长的时间。使用更好的哈希可以帮助您解决冲突问题，但如果S0中有很多长度为k的重复子字符串，则可能会使用O(k|S0|)。

  2. 现在在S1上使用相同的滚动哈希。这一次，在H0中查找每个子字符串，并且如果找到它，则从H0中删除它并将其插入新表H1中。除非存在某些病态情况（例如S0和S1都是同一个字符的长重复），否则这应该大约需要O(|S1|)的时间。(如果S0和S0是相同的字符串，或者有很多重叠的部分，则也会不太优化。)

  3. 为每个Si重复步骤2，每次创建一个新的哈希表。（在每次步骤2的迭代结束时，可以删除上一步的哈希表。）

在最后，最后一个哈希表将包含所有共同的k长度的子字符串。
总运行时间应该约为O(Σ|Si|)，但在最坏情况下可能为O(kΣ|Si|)。即使如此，根据所描述的问题规模，它应该在可接受的时间内运行。
你能详细说明为什么在最坏的情况下时间复杂度会是O(kΣ|Si|)吗？k从哪里来？ - Eli Zatlawy
1
从需要比较长度为O(k)的两个字符串以验证匹配是否正确的需求中解脱出来。最坏情况发生在有大量哈希碰撞且没有匹配的情况下。 - rici
1

我会尝试使用HashSet的简单方法：

  1. 为S中的每个长字符串构建一个HashSet，其中包含所有k-字符串。
  2. 按元素数量对集合进行排序。
  3. 扫描第一个集合。在其他集合中查找该术语。

第一步解决了每个长字符串中的重复项。 第二步确保最少的比较次数。

let getHashSet k (lstr:string) =
    let strs = System.Collections.Generic.HashSet<string>()
    for i in 0..lstr.Length - k do
        strs.Add lstr.[i..i + k - 1] |> ignore
    strs

let getCommons k lstrs =
    let strss = lstrs |> Seq.map (getHashSet k) |> Seq.sortBy (fun strs -> strs.Count)
    match strss |> Seq.tryHead with
    | None   -> [||]
    | Some h ->
    let rest = Seq.tail strss |> Seq.toArray
    [|  for s in h do
            if rest |> Array.forall (fun strs -> strs.Contains s) then yield s
    |]

测试：

let random = System.Random System.DateTime.Now.Millisecond
let generateString n =
    [|  for i in 1..n do
            yield random.Next 20 |> (+) 65 |> System.Convert.ToByte
    |] |> System.Text.Encoding.ASCII.GetString


[ for i in 1..3 do yield generateString 10000 ]
|> getCommons 4
|> fun l -> printfn "found %d\n %A" l.Length l

结果：
found 40
[|"PPTD"; "KLNN"; "FTSR"; "CNBM"; "SSHG"; "SHGO"; "LEHS"; "BBPD"; "LKQP"; "PFPH";
"AMMS"; "BEPC"; "HIPL"; "PGBJ"; "DDMJ"; "MQNO"; "SOBJ"; "GLAG"; "GBOC"; "NSDI";
"JDDL"; "OOJO"; "NETT"; "TAQN"; "DHME"; "AHDR"; "QHTS"; "TRQO"; "DHPM"; "HIMD";
"NHGH"; "EARK"; "ELNF"; "ADKE"; "DQCC"; "GKJA"; "ASME"; "KFGM"; "AMKE"; "JJLJ"|]

这是在fiddle中的链接: https://dotnetfiddle.net/ZK8DCT

1
我会将每个长字符串视为重叠短字符串的集合，例如ABCDEFGH被拆分为ABCDE、BCDEF、CDEFG、DEFGH和EFGHI。您可以将每个短字符串表示为一对索引，一个指定长字符串，另一个指定该字符串中的起始偏移量（如果这看起来太简单，请跳到结尾）。
然后，我会将每个集合按升序排序。
现在，您可以通过合并索引的排序列表来查找第一二个集合中共同的短字符串，仅保留第一个集合中也存在于第二个集合中的短字符串。检查这些幸存者是否与第三个集合相同，以此类推，最终幸存者对应于所有长字符串中都存在的短字符串。
（或者，您可以维护指向每个已排序列表的指针集，并反复查看每个指针是否指向具有相同文本的短字符串，然后前进指向最小短字符串的指针）。
时间复杂度为O(n log n)的初始排序是主导因素。在最坏情况下 - 例如，当每个字符串都是AAAAAAA..AA时 - 这会导致一个k系数，因为所有字符串比较都要检查所有字符并花费k的时间。希望有一种巧妙的方法可以绕过这个问题，使用https://en.wikipedia.org/wiki/Suffix_array可以使排序时间从O(nk log n)变为O(n)，而https://en.wikipedia.org/wiki/LCP_array应该允许您在比较来自不同后缀数组的子字符串时跳过一些字符。
重新思考后，我认为通常的后缀数组技巧可以用于将所有相关字符串连接在一起，中间用任何一个字符串中不存在的字符隔开。如果你查看结果后缀数组的LCP，你可以将其分成几个部分，在后缀之间的差异小于k个字符的点处进行分割。现在，每个特定部分中的每个偏移量都以相同的k个字符开头。现在，查看每个部分中的偏移量，并检查是否至少有一个偏移量来自每个可能的起始字符串。如果是这样，这个k字符序列出现在所有起始字符串中，否则不会。（有一些后缀数组构造方法可以适用于任意大的字母表，因此如果必要，您可以扩展您的字母表以生成任何一个字符串中不存在的字符）。
1

一些想法（N是字符串数量，M是平均长度，K是所需子字符串大小）：

方法1：

遍历所有字符串，计算k长度字符串的滚动哈希，并将这些哈希存储在映射中（存储元组{key: hash; string_num; position}）

时间复杂度O（NxM），空间复杂度O（NxM）

提取具有相等哈希值的组，逐步检查：
1）组的大小是否大于等于字符串数量
2）所有字符串是否在该组中表示
3）彻底检查真实子字符串是否相等（有时不同子字符串的哈希值可能重合）

方法2：

为每个字符串构建后缀数组

时间复杂度O（NxMlogM），空间复杂度O（NxM）

找到第一对字符串的后缀数组交集，使用类似合并的方法（后缀已排序），仅考虑长度为k的部分后缀，然后继续下一个字符串

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接