如何降低Python中在大文件内搜索bigram的时间复杂度？

Hey there! Let's fix that slow bigram check for your massive file. Your current code works, but it's inefficient because it scans lines one by one from scratch every time you call the function—and that adds up fast for large files. Here are several optimized approaches tailored to different scenarios:

1. Preload the File into Memory (If You Have the RAM) #

If your file fits comfortably in your system's memory, reading it once and storing the content in a variable will make subsequent checks blazingly fast. No more re-opening and re-scanning the file every time!

# Do this ONCE at the start of your program, not inside the check function
with open(r"D:\bigram.txt", 'r') as file:
    full_file_content = file.read()

def check(word1, word2):
    target_phrase = f"{word1} {word2}"
    return 1 if target_phrase in full_file_content else -1

Pro tip: Using f-strings (f"{word1} {word2}") is more efficient than string concatenation with +.

2. Optimize Line-by-Line Scanning (For Tight Memory) #

If loading the whole file isn't an option, you can still speed up your original approach by moving redundant operations outside the loop. Your original code re-built the target phrase every time it checked a line—let's fix that:

def check(word1, word2):
    target_phrase = f"{word1} {word2}"
    with open(r"D:\bigram.txt", 'r') as file:
        for line in file:
            if target_phrase in line:
                return 1
        return -1

This cuts down on unnecessary string operations, which adds up over thousands/millions of lines.

3. Use mmap for Ultra-Large Files #

For files that are way too big for RAM, the mmap module is a game-changer. It maps the file directly to your system's virtual memory, letting you search it like it's in RAM without actually loading the whole thing.

import mmap

def check(word1, word2):
    # mmap works with byte strings, so we encode our target phrase
    target_phrase = f"{word1} {word2}".encode()
    with open(r"D:\bigram.txt", 'r') as file:
        # Map the entire file for read-only access
        with mmap.mmap(file.fileno(), length=0, access=mmap.ACCESS_READ) as mapped_file:
            # find() returns -1 if the phrase isn't found
            return 1 if mapped_file.find(target_phrase) != -1 else -1

The OS handles the low-level optimization here, making this way faster than manual line-by-line scanning for huge files.

4. Preprocess Bigrams into a Set (For Frequent Checks) #

If you need to check multiple different bigrams over and over, preprocessing all bigrams into a Python set is the way to go. Sets have O(1) lookup time, so once you build the set, checks are instant.

# Preprocess ONCE at program start
bigram_collection = set()
with open(r"D:\bigram.txt", 'r') as file:
    for line in file:
        # Adjust this if lines have extra whitespace or multiple bigrams
        cleaned_bigram = line.strip()
        bigram_collection.add(cleaned_bigram)

def check(word1, word2):
    target_phrase = f"{word1} {word2}"
    return 1 if target_phrase in bigram_collection else -1

If the file is so large that even a set won't fit in RAM, you could use a lightweight database like SQLite to store the bigrams and run quick queries instead.

Quick Recommendation #

• Frequent checks: Use the set preprocessing method
• Single check, huge file: Use mmap
• Small/medium file: Preload into memory

内容的提问来源于stack exchange，提问作者N Agarwal