haskell - 如何快速搜索 `Text` 中的子字符串？

Question

我正在尝试找到在 Text 字符串中搜索子字符串的最快方法。以下是所需的输出:

findSubstringIndices :: Text -> Text -> [Int]
findSubstringIndices "asdfasdf" "as" == [0, 4]  -- 0-indexed
findSubstringIndices "asdasdasdasd" "asdasd" == [0, 3, 6]  -- matches can overlap

在我的应用程序中，子字符串是固定的 6 个字母单词，但要搜索的字符串非常长(假设超过 30 亿个字母)。我当前的方法是使用 KMP 包:

import Data.Text.Lazy as T
import Data.Algorithms.KMP as KMP
findSubstringIndices a b = KMP.match (KMP.build $ T.unpack b) $ T.unpack a

但这似乎是对 Text 紧凑性的巨大浪费。有没有什么(最好是简洁的)方法可以在不解压的情况下做到这一点？

我知道 Text 中有一个名为 breakOnAll 的函数，但是它不符合我允许重叠匹配的要求。

<小时/>

编辑:根据@ReidBarton的建议，我实现了一个不需要unpack的版本，这确实更快。但我不确定这是否是最快的。

findSubstringIndicesC t a b = let (l, r) = T.breakOn b a in case r of
    "" -> []
    _  -> T.length l : findSubstringIndicesC (t + T.length l + 1) (T.tail r) b

findSubstringIndices = findSubstringIndicesC 0

Answer 1

Data.ByteString.Search 的介绍性文字表示 Boyer-Moore 通常是最快的，链接到在某些特殊情况下更好的基于 DFA 的算法，并给出近似的性能比。您不应该使用 Text 来表示 DNA 序列。 Text 适用于自然语言，可能是多语言文本。 DNA 序列看起来完全不同。