如何在`Text`中以非常快的速度搜索子字符串？

我試圖找到儘可能最快的方式來搜索字符串Text中的子字符串。下面是所需的輸出：如何在`Text`中以非常快的速度搜索子字符串？

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

在我的應用程序，則子是一個固定的6字母的單詞，而是要搜索的字符串是很長的（比方說超過3十億個字母）。我目前的做法是使用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緊湊的浪費。有沒有（最好簡潔）的方式來做到這一點沒有unpack ing？

我知道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

來源

2015-10-05 trVoldemort

你預計會有很多比賽嗎？一個簡單的方法是使用'breakOn'，然後從結果的第二部分丟棄一個字符並重復。 –

@ReidBarton：這是一個想法。我有點擔心文檔說「如果你需要重複地用一個子串打斷一個字符串（例如，你想打破每個子串的實例），請改用breakOnAll，因爲它具有較低的啓動開銷。」這是否意味着重複使用此功能不可取？ – trVoldemort

嗯，是的，我認爲每個搜索都有一些額外的啓動開銷。這就是爲什麼我問你是否期望找到大量的匹配，或者只是少數，在這種情況下額外的開銷不太可能成爲問題。無論如何，第三方軟件包中可能會有更好的解決方案。 –

的介紹性文字Data.ByteString.Search表明，博耶 - 穆爾通常是最快的，鏈接到一個基於DFA的算法，在某些特殊情況下更好，並給出了近似的性能比。您不應該使用Text來表示DNA序列。 Text適用於自然語言，可能是多語言文本。 DNA序列看起來完全不同。

來源

2015-10-06 19:37:31 dfeuer

謝謝。我想我選擇'Text'的原因之一是因爲它具有'toUpper'這個方便的函數，它需要應用於輸入序列，並且我沒有在'ByteString'中找到等價物。有什麼簡單的方法可以在'ByteString'中做同樣的事情嗎？ – trVoldemort

呃......我可以使用'Data.ByteString.Lazy.Char8' - >'map Char。toUpper' – trVoldemort

@trVoldemort，你可以，但你可能會更好通過手動模式匹配來進行大小寫轉換。你只需要將四個字母轉換成什麼？五，如果你想要相同的功能來支持RNA？完整的Unicode大小寫轉換看起來像是矯枉過正，但是您可能會發現它足夠快。 – dfeuer

如何在`Text`中以非常快的速度搜索子字符串？

回答

相關問題