在大字符串中查找子字符串

#read in csv file in form ("case, num, val \n case1, 1, baz\n...") 
# convert to form FOO = "casenumval..." roughly 6 million characters 
for someString in List: #60,000 substrings 
    if substr not in FOO: 
     #do stuff 
    else: 
     #do other stuff

所以我的問題是，有太多的子字符串來檢查這個龐大的字符串。我已經嘗試逐行閱讀文件，並檢查子線對線，但這仍然崩潰的程序。有沒有什麼技術可以有效地檢查大量的子字符串是否對應一個非常大的字符串？在大字符串中查找子字符串

FOR CONTEXT：我正在執行數據檢查，懷疑數據保存到csv文件以供審查/更改。然後將該已審閱/更改的文件與原始文件進行比較。沒有改變的數據已被驗證爲良好，必須保存到新的「exceptionFile」中。已被更改並通過的數據被忽略。並且已經被更改並且被檢查並且仍然懷疑的數據被再次發送以供審查。

來源

2017-06-30 alexjones

如果'otherString'實際上是一個字符串，循環會遍歷_individual characters_，不子。 – ForceBru

你讀過這個問題嗎？ https://stackoverflow.com/questions/1765579/fast-algorithm-for-searching-for-substrings-in-a-string – Idos

這將有助於，如果你告訴我們什麼「做東西」和「做其他事情」需要知道。例如，它是否重要_哪些子字符串被找到，或者你只是在尋找它們？ – zwol

你應該做的第一件事就是將您的60000個字符串列表來搜索到一個大的正則表達式：

for m in searcher.finditer(FOO): 
    print(m.group(0)) # prints the substring that matched

：

import re 
searcher = re.compile("|".join(re.escape(s) for s in List)

現在你可以一次全部搜索它們

如果你只關心的是知道哪些被發現，

print(set(m.group(0) for m in searcher.finditer(FOO))

這仍然在做比絕對最低限度更多的工作，但它應該比以前做的更有效率多。另外，如果您知道您的輸入是CSV文件，並且您也知道沒有任何字符串搜索包含換行符，則可以逐行操作，這可能會或可能不是更快不是取決於條件，你在做什麼，但肯定會用較少的內存什麼：

with open("foo.csv") as FOO: for line in FOO: for m in searcher.finditer(line): # do something with the substring that matched

來源

2017-06-30 19:19:13 zwol

謝謝您的回答，我會立即對此進行測試。 – alexjones

在大字符串中查找子字符串

回答

相關問題