在大文本中计数字符串
我在StackOverflow上看到过几种关于“如何高效地在文件中搜索字符串”的问题，但我的情况有点不同。
我有一个文本文件，里面包含了相对较多的字符串（超过30万条）。这些字符串大多数都是多个单词的组合（比如“Plessy v. Ferguson”，“John Smith”等）。
接下来，我需要在一大堆文本文件中搜索这些字符串（这些法律文件总共超过10GB），并统计这些字符串出现的次数。
由于搜索字符串的数量很多，而且这些字符串都是多个单词，再加上要搜索的文件很大，很多“标准”的解决方案似乎都不太适用。
不过，有一些因素让问题简单了一些：
我不需要复杂的分词、词干提取等处理（例如，我只关心“Plessy v. Ferguson”，不需要考虑“Plessy”、“Plessy et. al.”等）。
会有一些重复的情况（比如，有好几个人叫“John Smith”），不过对于这个数据集来说，这并不是一个很重要的问题，所以如果多个“John Smith”被统计成一个，那也没关系。
我只需要统计这些特定的实例；不需要返回搜索结果。
在一个文件中出现10次和在10个文件中各出现1次的统计方式是一样的。
有没有什么快速简单的方法来解决这个问题呢？
我研究过NLTK、Lucene等工具，但它们似乎对我想解决的问题来说有点过于复杂。我是不是应该忍耐一下，把所有东西导入数据库？还是直接用暴力方式搜索30万次？；）
我比较喜欢用Python作为开发工具。
需要搜索的文档主要是这样的法律文件 - http://www.lawnix.com/cases/plessy-ferguson.html
我想要的结果是统计这些案件在这些文档中被提到的次数，比如 - “Plessy v. Ferguson: 15”
5 个回答
这个简单粗暴的方法行不通。
你可以先试着用一次grep命令搜索你的文件，看看这次搜索花了多长时间，然后推算一下如果要进行30万次搜索需要多长时间。如果你有很多机器，可以考虑并行处理，这样可能会快一些。我的猜测是，30万次搜索可能不太现实。比如，我用grep在大约50MB的文件中搜索一次，花了大约5秒钟。那么如果是10GB的文件，你可能需要大约1000秒，再重复30万次的话，估计要花10年才能完成，假如只用一台电脑。虽然可以通过并行处理来提高速度（但这还是受限于一台电脑的磁盘读写速度），不过效果也会有限。我想你希望这个任务在几个小时内完成，而不是几个月，所以这个方法可能不太合适。
所以你需要想办法给文件建立索引。Lucene（比如通过pythonsolr）或者Xapian都可以满足你的需求。先给文件建立索引，然后再在索引中搜索。
你面临几个限制条件，这让问题变得复杂。
- 硬盘读写速度
- 内存空间
- 处理时间
我建议你写一个多线程或多进程的Python应用程序。使用子进程的库非常简单。每个进程读取一个文件，然后按照Blindy的建议解析树形结构。当它完成后，会把结果返回给父进程，父进程再把结果写入一个文件。
这样可以充分利用你能提供的资源，同时也方便扩展。如果你把它放在一个Beowulf集群上，它会自动在你的多个CPU之间分配进程。
唯一需要注意的是硬盘的读写速度。可以把文件分成几个部分，放在不同的硬盘上。当一个进程完成后，就启动一个新的进程来加载一个文件。如果你使用的是Linux，所有文件可以在同一个文件系统中共存，你的程序不会察觉到有什么不同。
解决这个问题的一个简单方法是建立一个字典树，也就是一个前缀树。这种树的每个节点里只放一个字符。当你在搜索一个10GB的大文件时，可以根据文本的匹配情况，递归地在这个树里查找。
这样一来，你在搜索大文件时，可以很早就排除掉很多不可能的选项，特别是在每个字符的位置上，同时又能遍历到所有可能的解决方案。
这样做的时间效率会非常好，跟很多其他复杂的解决方案一样出色。而且你只需要足够的空间来存储这棵树（比存储整个字符串数组要少得多），再加上一个小的缓冲区来处理大文件。总之，这种方法比在数据库里搜索30万次要好得多……