Cheap way to search a large text file for a string

Question

I need to search a pretty large text file for a particular string. Its a build log with about 5000 lines of text. Whats the best way to go about doing that? Using regex shouldn't cause any problems should it? I'll go ahead and read blocks of lines, and use the simple find.

Answer 1

If it is "pretty large" file, then access the lines sequentially and don't read the whole file into memory:

with open('largeFile', 'r') as inF:
    for line in inF:
        if 'myString' in line:
            # do_something

Answer 2

You could do a simple find:

f = open('file.txt', 'r')
lines = f.read()
answer = lines.find('string')

A simple find will be quite a bit quicker than regex if you can get away with it.

Answer 3

The following function works for textfiles and binary files (returns only position in byte-count though), it does have the benefit to find strings even if they would overlap a line or buffer and would not be found when searching line- or buffer-wise.

def fnd(fname, s, start=0):
    with open(fname, 'rb') as f:
        fsize = os.path.getsize(fname)
        bsize = 4096
        buffer = None
        if start > 0:
            f.seek(start)
        overlap = len(s) - 1
        while True:
            if (f.tell() >= overlap and f.tell() < fsize):
                f.seek(f.tell() - overlap)
            buffer = f.read(bsize)
            if buffer:
                pos = buffer.find(s)
                if pos >= 0:
                    return f.tell() - (len(buffer) - pos)
            else:
                return -1

The idea behind this is:

• seek to a start position in file
• read from file to buffer (the search strings has to be smaller than the buffer size) but if not at the beginning, drop back the - 1 bytes, to catch the string if started at the end of the last read buffer and continued on the next one.
• return position or -1 if not found

I used something like this to find signatures of files inside larger ISO9660 files, which was quite fast and did not use much memory, you can also use a larger buffer to speed things up.

Answer 4

This is a multiprocessing example of file text searching. TODO: How to stop the processes once the text has been found and reliably report line number?

import multiprocessing, os, time
NUMBER_OF_PROCESSES = multiprocessing.cpu_count()

def FindText( host, file_name, text):
    file_size = os.stat(file_name ).st_size 
    m1 = open(file_name, "r")

    #work out file size to divide up to farm out line counting
        
    chunk = (file_size / NUMBER_OF_PROCESSES ) + 1
    lines = 0
    line_found_at = -1

    seekStart = chunk * (host)
    seekEnd = chunk * (host+1)
    if seekEnd > file_size:
        seekEnd = file_size

    if host > 0:
        m1.seek( seekStart )
        m1.readline()
            
    line = m1.readline()
    
    while len(line) > 0:
        lines += 1
        if text in line:
            #found the line
            line_found_at = lines
            break
        if m1.tell() > seekEnd or len(line) == 0:
            break
        line = m1.readline()
    m1.close()
    return host,lines,line_found_at
        
# Function run by worker processes
def worker(input, output):
    for host,file_name,text in iter(input.get, 'STOP'):
        output.put(FindText( host,file_name,text ))

def main(file_name,text):
    t_start = time.time()
    # Create queues
    task_queue = multiprocessing.Queue()
    done_queue = multiprocessing.Queue()
    #submit file to open and text to find
    print 'Starting', NUMBER_OF_PROCESSES, 'searching workers'
    for h in range( NUMBER_OF_PROCESSES ):
        t = (h,file_name,text)
        task_queue.put(t)

    #Start worker processes
    for _i in range(NUMBER_OF_PROCESSES):
        multiprocessing.Process(target=worker, args=(task_queue, done_queue)).start()

    # Get and print results
    
    results = {}
    for _i in range(NUMBER_OF_PROCESSES):
        host,lines,line_found = done_queue.get()
        results[host] = (lines,line_found)

    # Tell child processes to stop
    for _i in range(NUMBER_OF_PROCESSES):
        task_queue.put('STOP')
#        print "Stopping Process #%s" % i
    
    total_lines = 0
    for h in range(NUMBER_OF_PROCESSES):
        if results[h][1] > -1:
            print text, 'Found at', total_lines + results[h][1], 'in', time.time() - t_start, 'seconds'
            break
        total_lines += results[h][0]
    
if __name__ == "__main__":
    main( file_name = 'testFile.txt', text = 'IPI1520' )

Answer 5

I'm surprised no one mentioned mapping the file into memory: mmap

With this you can access the file as if it were already loaded into memory and the OS will take care of mapping it in and out as possible. Also, if you do this from 2 independent processes and they map the file "shared", they will share the underlying memory.

Once mapped, it will behave like a bytearray. You can use regular expressions, find or any of the other common methods.

Beware that this approach is a little OS specific. It will not be automatically portable.

Answer 6

If there is no way to tell where the string will be (first half, second half, etc) then there is really no optimized way to do the search other than the builtin "find" function. You could reduce the I/O time and memory consumption by not reading the file all in one shot, but at 4kb blocks (which is usually the size of an hard disk block). This will not make the search faster, unless the string is in the first part of the file, but in all case will reduce memory consumption which might be a good idea if the file is huge.

Answer 7

I like the solution of Javier. I did not try it, but it sounds cool!

For reading through a arbitary large text and wanting to know it a string exists, replace it, you can use Flashtext, which is faster than Regex with very large files.

Edit:

From the developer page:

>>> from flashtext import KeywordProcessor
>>> keyword_processor = KeywordProcessor()
>>> # keyword_processor.add_keyword(<unclean name>, <standardised name>)
>>> keyword_processor.add_keyword('Big Apple', 'New York')
>>> keyword_processor.add_keyword('Bay Area')
>>> keywords_found = keyword_processor.extract_keywords('I love Big Apple and Bay Area.')
>>> keywords_found
>>> # ['New York', 'Bay Area']

Or when extracting the offset:

>>> from flashtext import KeywordProcessor
>>> keyword_processor = KeywordProcessor()
>>> keyword_processor.add_keyword('Big Apple', 'New York')
>>> keyword_processor.add_keyword('Bay Area')
>>> keywords_found = keyword_processor.extract_keywords('I love big Apple and Bay Area.', span_info=True)
>>> keywords_found
>>> # [('New York', 7, 16), ('Bay Area', 21, 29)]

Limitation: I want to point out that this solution is NOT the optimal solution for the given question. For the given question in from eumiro's solution under the caveat given by @bfontaine in the respective comment is the definetly the best answer.

flashtext is a powerful solution, if you want to find all (!) occurrences of a string in a given text. This is something in cannot do (and is not made for to do).

Answer 8

This is entirely inspired by laurasia's answer above, but it refines the structure.

It also adds some checks:

• It will correctly return 0 when searching an empty file for the empty string. In laurasia's answer, this is an edge case that will return -1.
• It also pre-checks whether the goal string is larger than the buffer size, and raises an error if this is the case.

In practice, the goal string should be much smaller than the buffer for efficiency, and there are more efficient methods of searching if the size of the goal string is very close to the size of the buffer.

def fnd(fname, goal, start=0, bsize=4096):
    if bsize < len(goal):
        raise ValueError("The buffer size must be larger than the string being searched for.")
    with open(fname, 'rb') as f:
        if start > 0:
            f.seek(start)
        overlap = len(goal) - 1
        while True:
            buffer = f.read(bsize)
            pos = buffer.find(goal)
            if pos >= 0:
                return f.tell() - len(buffer) + pos
            if not buffer:
                return -1
            f.seek(f.tell() - overlap)

Answer 9

5000 lines isn't big (well, depends on how long the lines are...)

Anyway: assuming the string will be a word and will be seperated by whitespace...

lines=open(file_path,'r').readlines()
str_wanted="whatever_youre_looking_for"


    for i in range(len(lines)):
        l1=lines.split()
        for p in range(len(l1)):
            if l1[p]==str_wanted:
                #found
                # i is the file line, lines[i] is the full line, etc.