Python高效的方法來檢查是否非常大的字符串包含子字符串

Python不是我最好的語言，所以我並不擅長尋找對我的一些問題最有效的解決方案。我有一個非常大的字符串（來自30 MB文件），我需要檢查該文件是否包含較小的子字符串（該字符串只有幾十個字符）。我現在這樣做的方式是：Python高效的方法來檢查是否非常大的字符串包含子字符串

if small_string in large_string: 
    # logic here

但是這似乎是非常低效的，因爲它會檢查文件中每個可能的字符序列。我知道在換行符上只有一個完全匹配，所以將列表中的文件讀入並遍歷該列表以匹配會更好嗎？

編輯：爲了澄清一些混亂的「匹配上只有一個換行」，這裏有一個例子：

small_string = "This is a line" 
big_string = "This is a line\nThis is another line\nThis is yet another"

如果我沒有錯，在關鍵字將檢查所有的序列，而不僅僅是每一行。

來源

2011-08-24 Jon Martin

你是什麼意思，「在換行符上完全匹配」？ –

你想要有效利用空間（記憶）或找到比賽的速度效率嗎？不同的模式匹配算法在這方面具有不同的特徵。 –

@Jon：您提供的示例將停止在第一行搜索。 –

您可以使用這些算法之一：

Rabin–Karp string search algorithm
Knuth–Morris–Pratt algorithm（又名KMP）看到一個實現here

雖然我相信KMP更有效，這是實現起來比較複雜。第一個鏈接包含一些僞代碼，這些代碼應該很容易實現nt在python中。

，你可以看看這裏的替代品：http://en.wikipedia.org/wiki/String_searching_algorithm

來源

2011-08-24 12:02:11

Python已經使用[一個相當快的C級實現「boyer-moore和horspool之間的混合」]（https://hg.python.org/cpython/file/5444c2e22ff8/Objects/stringlib/fastsearch.h），所以在Python級別實現不同的字符串搜索算法可能會慢幾個數量級。 – user2357112

我不知道如何使它在比較更優化的，是誠實的。但是你可以使用較少的內存，並與我失去的時間更少/ O如果你逐行讀取文件中的行：

has_small_string = False 
for line in large_file: 
    if small_string in line: 
     has_small_string = True 
     break 
if has_small_string: 
    # ... Your stuff here ...

這絕不是革命性的改進，甚至可以少有用的，如果你真的需要大字符串中的內存，但它可以是有幫助的，所以我在這裏張貼:)

來源

2011-08-24 12:07:30 brandizzi

如果你只是要檢查如果子存在，

for line in open("file"): 
    if substring in line: 
     print "exists" 
     sys.exit() # or break to do some other stuff

來源

2011-08-24 12:09:18 ghostdog74

濡緩太慢？我只對一個170 MB字符串的末尾做了一個a in b測試以獲取唯一字符串。它在我的手指離開Enter鍵之前完成。

import subprocess 
from subprocess import STDOUT 
import os 

... 
with open(os.devnull, 'w') as devnull: 
    if subprocess.call('grep %s "%s"' % (smallstring, file), shell=True, stdout=devnull, stderr=STDOUT) == 0: 
     pass #do stuff

將無法在Windows工作：

來源

2011-08-24 12:09:45

你是怎麼搜索的？你能展示一些簡單的代碼嗎？ – Mawg

從2011年起？不是一個線索。 –

-1

我會被別人依靠快速實現。

編輯：我擔心taht grep返回0它發現了什麼或沒有。但我現在沒有任何外殼可供我使用，所以我無法測試它。

來源

2011-08-24 12:12:01 rplnt

這是不必要的，調用一個外部程序。 – ghostdog74

它真的很慢嗎？你說的是30MB的字符串;讓我們嘗試更大的字符串：

In [12]: string="agu82934u"*50*1024*1024+"string to be found" 

In [13]: len(string) 
Out[13]: 471859218 

In [14]: %timeit "string to be found" in string 
1 loops, best of 3: 335 ms per loop 

In [15]: %timeit "string not to be found" in string 
1 loops, best of 3: 200 ms per loop

我不會說，335毫秒是很多時間尋找450MB字符串中的子字符串。

來源

2011-08-24 12:35:49

您是否暗示只有一條完整的生產線纔會匹配？（您編輯：上一個換行符匹配唯一的例子似乎）

然後我想象

for line in open('file').readlines(): 
    if line==small_string: 
    return True 
return False

IE，使用==比「在」快 - 也許。我不會感到驚訝的是，如果底層實現in捕獲的情況下，搜索行和搜索字符串長度相同，只是嘗試一個==本身。

會更好。

來源

2011-08-24 13:46:47

small_string = "This is a line" 
big_string = "This is a line This is another line\nThis is yet another" 

test= big_string.split("This is a line" ,1) 

if len(test)==2: 

    print "it`s there" 

elif len(test)!=2: 

    print "it`s not"

來源

2015-11-05 12:49:43

Python高效的方法來檢查是否非常大的字符串包含子字符串

回答

相關問題