在Python中对大型文本文件进行字符串搜索 - 分析各种方法

Question

这个问题已经被问了很多次。在阅读了答案后，我进行了一些快速分析来尝试之前提到的各种方法...

• 我有一个包含6百万行字符串（DMOZ项目的分类路径）的600 MB文件。
• 每行上的条目都是唯一的。
• 我想要一次加载该文件，并在数据中保持搜索以查找匹配项。

我尝试的三种方法如下，列出了加载文件所花费的时间、搜索负匹配所花费的时间和任务管理器中的内存使用情况：

---

1) set :
    (i)  data   = set(f.read().splitlines())
    (ii) result = search_str in data   

加载时间约为10秒，搜索时间约为0.0秒，内存使用量约为1.2GB

2) list :
    (i)  data   = f.read().splitlines()
    (ii) result = search_str in data

加载时间约为6秒，搜索时间约为0.36秒，内存使用量约为1.2GB

3) mmap :
    (i)  data   = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)
    (ii) result = data.find(search_str)

加载时间约为0秒，搜索时间约为5.4秒，内存使用情况无法确定

4) Hash lookup (using code from @alienhard below):   

加载时间 ~ 65秒，搜索时间 ~ 0.0秒，内存使用 ~ 250MB

5) File search (using code from @EOL below):   
   with open('input.txt') as f:
       print search_str in f #search_str ends with the ('\n' or '\r\n') as in the file

加载时间约为0秒，搜索时间约为3.2秒，内存使用情况未知

6) sqlite (with primary index on url): 

加载时间 ~ 0秒，搜索时间 ~ 0.0秒，内存使用 ~ NA

---

对于我的用例而言，只要我有足够的内存可用，选择使用 set 看起来是最好的选项。我希望对以下问题提出一些评论：

1. 更好的替代方案，例如 sqlite?
2. 使用 mmap 改进搜索时间的方法。我有一个64位设置。 [编辑] 例如布隆过滤器
3. 当文件大小增长到几个GB时，是否有任何方法可以继续使用 'set'，例如将其分批处理..

[编辑1] P.S. 我需要频繁搜索、添加/删除值，并且不能仅使用哈希表，因为我需要稍后检索修改后的值。

欢迎提出任何评论或建议！

[编辑2] 使用答案中建议的方法更新结果 [编辑3] 使用sqlite的结果更新

解决方案: 基于所有的分析和反馈，我认为我会选择使用 sqlite。第二种选择是方法4。 sqlite的一个缺点是数据库大小超过了具有url的原始csv文件的两倍。这是由于url上的主索引造成的。

- user

---

你需要在文件中查找许多字符串，还是只有一个字符串，一次或其他什么东西？ - Eric O. Lebigot

@senderle 不行。 @EOL：我需要重复搜索字符串，并添加新的。我会更新原始帖子。 - user

为什么选项1和2具有相同的内存使用率？我尝试了一个大约有110k行的2.7mb数据文件。列表的大小与数据文件大致相同，而集合对象的大小约为4.1mb。 - Chris.Q

Answer 1

如果需要进行多次连续搜索，则变体1非常适用。由于set在内部是哈希表，因此它在搜索方面表现出色。但是，构建需要时间，并且仅在数据适合RAM时才能正常工作。

变体3适用于非常大的文件，因为您有足够的地址空间将它们映射并且操作系统缓存了足够的数据。您需要进行完整的扫描；一旦数据不再适合RAM，它可能变得相当缓慢。

如果需要进行多个搜索且无法将数据存储到RAM中，则SQLite绝对是一个好主意。将字符串加载到表中，构建索引，然后SQLite会为您构建一个很好的b树。即使数据不适合RAM，该树也可以适应RAM（这有点像@alienhard提出的方式），即使不能，所需的I/O量也显着降低。当然，您需要创建基于磁盘的SQLite数据库。我怀疑基于内存的SQLite不会显著击败Variant 1。

- 9000

---

我的担忧是文件可能会超出RAM大小，而mmap不够快。我得看看sqlite。感谢您的见解。只要查找时间少于1/10秒，并且可以管理2-5GB的文件，我就很满意。 - user

Answer 2

使用外部化字符串的自定义哈希表搜索

为了获得快速的访问时间 和 更低的内存消耗，可以按照以下步骤进行：

• 对于每一行，计算一个字符串哈希并将其添加到哈希表中，例如，index[hash] = position（不要存储字符串）。如果发生冲突，则在一个列表中存储该键的所有文件位置。
• 要查找一个字符串，计算它的哈希并在表中查找它。如果找到了键，从文件中读取位于position的字符串以验证您确实有一个匹配项。如果有多个位置，请检查每个位置，直到找到一个匹配或没有找到。

编辑1：替换行号为位置（正如评论者所指出的那样，显然需要实际位置而不是行号）

编辑2：提供一个使用自定义哈希表的实现代码，证明这种方法比其他提到的方法更具有内存效率：

from collections import namedtuple 
Node = namedtuple('Node', ['pos', 'next'])

def build_table(f, size):
    table = [ None ] * size
    while True:
        pos = f.tell()
        line = f.readline()
        if not line: break
        i = hash(line) % size
        if table[i] is None:
            table[i] = pos
        else:
            table[i] = Node(pos, table[i])
    return table

def search(string, table, f):
    i = hash(string) % len(table)
    entry = table[i]
    while entry is not None:
        pos = entry.pos if isinstance(entry, Node) else entry
        f.seek(pos)
        if f.readline() == string:
            return True
        entry = entry.next if isinstance(entry, Node) else None
    return False

SIZE = 2**24
with open('data.txt', 'r') as f:
    table = build_table(f, SIZE)
    print search('Some test string\n', table, f)

在这个程序中，行的哈希值仅用于索引到表中（如果我们使用普通字典，哈希值也将作为键存储）。行的文件位置存储在给定索引处。冲突是通过链接解决的，即我们创建一个链接列表。但是，第一个条目永远不会包装在节点中（这种优化使代码有点复杂，但它节省了相当多的空间）。

对于一个有600万行的文件，我选择了2^24的哈希表大小。在我的测试数据中，我得到了933132个冲突。（哈希表大小为一半时，内存消耗大致相同，但导致更多的冲突。因为更多的冲突意味着搜索需要更多的文件访问，所以我宁愿使用一个较大的表。）

Hash table: 128MB (sys.getsizeof([None]*(2**24)))
Nodes:       64MB (sys.getsizeof(Node(None, None)) * 933132)
Pos ints:   138MB (6000000 * 24)
-----------------
TOTAL:      330MB (real memory usage of python process was ~350MB)

- alienhard

---

存储行号并没有任何帮助，你需要存储文件位置。 - Sven Marnach

@alienhard 不错的想法，值得一试。有没有已经做到这一点的轻量级库？ - user

我也考虑过这个，但是我检查了一下，在我的机器上，一个有6000000个项的字典，每个项有两个整数（每个项大约120 + 24 + 24字节），仍然需要近1GB的内存。实际上，由于集合只占与相同大小字典的2/3的内存，并且由于您只需要在集合中存储一个字符串（每个项大约80 + 40 + len(s)字节），根据平均字符串长度，集合解决方案实际上可能需要更少的内存。 - senderle

@buffer 我编辑了我的答案并添加了完整的实现。我非常想知道它对你的数据集有什么作用？ - alienhard

@senderle 你说得没错，使用字典会占用太多内存。但是通过自定义实现（见代码），我们可以做得更好，因为我们不需要存储哈希键，并且在最佳情况下只需将位置整数存储在表中。实际的内存消耗取决于碰撞的数量，但是使用我的测试数据，我得到了330MB，这比其他解决方案少了3.5倍的内存。 - alienhard

@alienhard，你的代码很棒，点个赞。我会把你的方法的结果加进去。 - user

Answer 3

您可以尝试以下方法：

with open('input.txt') as f:
    # search_str is matched against each line in turn; returns on the first match:
    print search_str in f

使用适当的换行符（'\n'或'\r\n'）结束具有search_str的内容。这应该使用较少的内存，因为文件是逐步读取的。由于仅读取文件的一部分，因此速度也应该相当快。

- Eric O Lebigot

---

它会比mmap更快吗？ - user

@buffer：是的，它比mmap更快。在文件中查找不存在的字符串时，使用mmap比上述解决方案慢50%以上（在我的机器上，mmap需要4秒，而in只需要2.4秒）。in解决方案还具有可忽略的内存占用。 - Eric O. Lebigot

谢谢，我已经更新了结果。我猜这个方法只适用于全行搜索。 - user

@buffer：是的，它只适用于全行搜索（就像您原始帖子中的方法（1）、（2）和（4）一样）。 - Eric O. Lebigot

Answer 4

我猜很多DMOZ上的路径开始都一样。您应该使用trie数据结构并将单个字符存储在节点上。

Trie具有O(m)的查找时间（其中m是键长），同时也可以节省大量空间，用于保存大型词典或类似树形数据。

您还可以在节点上存储路径部分以减少节点数-这称为Patricia Trie。但是，这会通过平均字符串长度比较时间使查找变慢。有关实现的更多信息，请参见SO问题Python中的Trie（前缀树）。

Python软件包索引上有几个Trie实现，但它们不太好。我已经用Ruby和Common Lisp编写了一个，特别适合这项任务-如果您请求得当，我可以将其发布为开源…… :-)

- peterhil

---

好的，但是如果您可以将数据分区，以便许多项目（例如行、子句或其他内容）开头相同，那么仍然值得考虑使用 Trie。 - peterhil

同意。在阅读维基百科文章后，我意识到我脑海中有一个模糊类似的想法，但可能超出了我现在所需的10倍规模。正在寻找快速解决方案。 - user

为了快速解决问题，您可以尝试使用Judy Arrays。有一个名为PyJudy的Python C库。 - peterhil

Answer 5

关于文本索引解决方案怎么样？

在Java世界中，我会使用Lucene，但在Python中有一个叫做Whoosh的引擎。

https://bitbucket.org/mchaput/whoosh/wiki/Home

- rlawson

---

我会看一下...但如果它类似于Lucene，正如@Creotiv所建议的那样，Sphinx可能是更好的选择。 - user

Answer 6

如果不建立索引文件，你的搜索速度会很慢，而这并不是一项简单的任务。因此最好使用已经开发好的软件。最好的方法是使用Sphinx Search Engine。

- Andrey Nikishaev

---

Sphinx是一款很棒的软件，但对于我的情况来说似乎有些过度。我正在寻找一个轻量级的解决方案。 - user

我认为没有轻量级解决方案。如果你愿意，你可以尝试自己做某种索引来加快搜索，但正如我所说，这并不简单，因此需要时间来制作出能够良好运行的东西。 - Andrey Nikishaev

但是有一个时刻，你必须使用C来编写，因为基于Python的算法无法提供良好的性能。 - Andrey Nikishaev