0

我有一个巨大的 .txt.gz 文件，其中包含约 800kb 的单词和分数值，每行格式化为“值单词”并按单词排序。查找给定单词的值的最快方法是什么？

我可以使用以下方法读取文件：

import gzip

f = gzip.open('somefile.txt.gz', 'rb')
file_content = f.read()

最快的方法是某种二进制搜索吗？

样本数据：

0.090909 chevre#n#1

0.058824 雪佛龙#n#1

0.071429 雪佛龙#n#2

0.071429 雪佛兰#n#1

0.166667 咀嚼#n#1

4

1 回答 1

1

二进制搜索将是执行此类操作的有效方法，但是您仍然必须将数据从文本（毕竟只是一堆字节）移动到其他数据结构中，例如列表。如果你有一个生命周期很短的程序，或者没有长期内存限制，那么dict在启动时（或在适当的时候）将整个东西加载到 Python 中（可能）会更快：

# This may not work exactly right for your file format, but you get the idea.
lookup = {}
for line in f:
    if line:
        value, key = line.trim().split():
        lookup[key] = value

然后你可以使用 Python 的内置字典来访问它，它既好又快：

def get_value(word):
    return lookup.get(word)

编辑

如果您唯一的选择是读取每个单词的整个文件，并且您正在搜索许多单词，那么与您花费在打开和一遍又一遍地阅读文件。你真正想要的是一个数据库，它实际上可以快速处理这种事情。也就是说，鉴于这些参数，如果我不得不使用文件系统，我可能会做这样的事情：

import bisect

# Define searchable (word, value) tuples for every word in the file.
# I'm assuming your files are sorted, but if not, sort this list (SLOW!!)
words = [(w[1], w[0]) for w in (line.strip().split() for line in f if line)]

# Binary search for the word and return its associated value.
def get_value(word):
    idx = bisect.bisect_left(words, (word,None)) # Tuples compare element-wise
    if idx != len(words) and words[idx][0] == word:
        return words[idx][1]
    raise ValueError('word not found')

最后，我注意到您正在使用 gzip 压缩文件，如果存储空间是一个问题，这是明智的，但它会进一步减慢您的进程。我不得不再次建议一个数据库。无论如何，我不知道您是否在这里遇到了麻烦，但以防万一，阅读 gzip 压缩文件并不比阅读普通文件“更难”。看看gzip 模块。基本上，gzip 文件就像普通文件一样工作，所以你仍然可以写for line in file等等。

于 2013-05-14T23:12:39.393 回答