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

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），其中包含所有标准化的搜索关键字，并将其映射到找到这些关键字的位置。然后您可以快速检索偏移量和长度，并在实际文件中查找该位置，进行适当的基于==的比较。在

Answer 2

根据您搜索整句话的评论：

建立前缀索引。

对文件进行排序。接下来，处理一次文件。计算将搜索减少到1000个句子所需的前缀长度。也就是说，在一个给定句子的大约1000个句子中，你需要多少个前缀字符。在

例如：“The”可能是英语中常见的起始词。但是“快速”可能已经足够接近了，因为“q”是低频，对于任何像“快速棕色狐狸”这样的东西。。。等等。”

这样做的一种方法是将所有的前缀（例如，40）放入一个集合.计数器. 找到每个长度的最大计数，然后选择您的长度，使max<；=1000。可能还有其他方法。；—）

现在，再次处理该文件。构建一个单独的索引文件，由前缀长度（在文件头中）、前缀和偏移量组成。所有以前缀K开头的句子都以偏移量V开头。因为文件已排序，索引也将被排序。在

您的程序可以将索引读入内存，打开文件，并开始处理搜索。对于每次搜索，切掉前缀，在索引中查找，查找文件偏移量，然后扫描匹配项。在