对于一个很长的字符串列表，什么是一个好的数据结构？

Question

我有一个非常大的文件（80GB），每行包含一个句子。我想在这个文件中搜索用户给定的字符串以匹配（空格、连字符、大小写被忽略）。在

现在我有文本文件，我正在使用grep，但这需要很多时间。有什么更好的解决办法？在

文本文件内容示例：

 applachian
 rocky mountains
 andes
 sierra nevada
 long mountain ranges of the world

搜索查询示例：

^{pr2}$

Answer 1

您可以通过将句子映射到散列来构建一个可共享的数据库，然后您可以在潜在的位置查找数据。在

from collections import defaultdict
from cStringIO import StringIO

DATA = """applachian
rocky mountains
andes
sierra nevada
long mountain ranges of the world"""


def normalize(sentence):
    return "".join(sentence.lower().strip())


def create_db(inf):
    db = defaultdict(list)
    offset = 0
    for line in inf:
        l = len(line)
        db[hash(normalize(line))].append((offset, l))
        offset += l
    return db


def main():
    db = create_db(StringIO(DATA))
    # save this db, and in a different script, load it to retrieve:
    for needle in ["rocky", "sierra nevada"]:
        key = hash(normalize(needle))
        for offset, length in db.get(key, []):
            print "possibly found at", offset, length


if __name__ == '__main__':
    main()

这说明了这样一个想法：您构建一个数据库（例如存储为pickle），其中包含所有标准化的搜索关键字，并将其映射到找到这些关键字的位置。然后您可以快速检索偏移量和长度，并在实际文件中查找该位置，进行适当的基于==的比较。在