在（非常大的）文本中计算（大量）字符串

Question

我已经看到了Stackoverflow中“有效搜索文件中的字符串”问题的几个变体，但不像我的情况。

• 我有一个文本文件，其中包含一个相对较大的数字（> 300K）的字符串。绝大多数这些字符串是多个词（例如，“普莱西诉弗格森”，“约翰史密斯”等）。

• 从那里，我需要搜索非常大的一组文本文件（一组总共大于10GB的合法文档）并计算这些字符串的实例。

因为搜索字符串的数量，有多个单词的字符串和搜索目标的大小，很多“标准”的解决方案似乎倒在路边。

有些事情简化问题一点点 -

• 我不需要复杂的符号化/词干/等（如我所关心的唯一实例是“普莱西诉弗格森。”，不需要担心“普莱西”，“普莱西等”）

• 会有一些重复（例如，多个人名为“约翰史密斯”），但是，这不是一个非常这个数据集有统计学意义的问题，所以......如果多个John Smith被合并成一个单一的计数，那么现在就可以。

• 我只需要计算这些特定的实例;我并不需要返回搜索结果

• 在1个文件10个实例数相同，每10个文件

快速/肮脏的方式来解决这个问题有什么建议1个实例？

我已经调查了NLTK，Lucene &其他人，但他们似乎是矫枉过正的问题，我试图解决。我应该把它吸入并将所有内容导入到数据库中？ bruteforce grep它300K次？ ;）

我的首选开发工具是Python。

---

要搜索的文档主要是法律文档这样的 - http://www.lawnix.com/cases/plessy-ferguson.html

预期的成果是对的情况下是如何经常跨越这些文档中引用tallys - “普莱西v弗格森：15”

Answer 1

解决这个问题的简单方法是用你的查询构建一个trie（只是一个前缀树，里面有一个单一字符的节点列表），当你通过你的10gb文件进行搜索时，你会以文本的形式递归地遍历树火柴。

通过这种方式，您可以在选择大文件中的每个字符位置时尽早选择的选项，同时仍在搜索整个解决方案空间。

时间表现会非常好（与其他很多更复杂的解决方案一样好），并且只需要足够的空间来存储树（比整个字符串数少很多）和一个小缓冲区进入大文件。肯定比grecking一个db好多了300k ...

Answer 2

你有几个约束你必须处理，这使得这是一个复杂的问题。

1. 硬盘IO
2. 内存空间
3. 处理时间

我建议写一个多线程/多进程Python应用程序。子进程的库是无痛的。让每个进程读取一个文件，并按照Blindy建议的解析树。完成后，它会将结果返回给父项，并将其写入文件。

这将耗尽尽可能多的资源，因为您可以投入它，同时允许扩展。如果你将它粘在一个beowulf集群上，它会透明地为你共享你的cpus中的进程。

唯一的问题是硬盘IO。在不同的硬盘上将它分成块，并且在每个过程完成时，启动一个新过程并加载一个文件。如果你在linux上，所有的文件可以共存在同一个文件系统名字空间中，你的程序不会知道它们的区别。

Answer 3

丑陋的蛮力解决方案将无法正常工作。

时间一个grep通过您的文档并推断出300k greps花费的时间（并且如果您有很多可用的机器，可能尝试并行化），这是否可行？我的猜测是300k的搜索将不可行。例如，对大约50Mb的文件进行一次搜索花费了我大约5秒，因此对于10Gb，你会期望〜1000s，然后重复30万次，这意味着用一台计算机就可以在大约10年内完成搜索。你可以并行化以获得一些改进（在一台计算机上受到磁盘io的限制），但仍然会非常有限。我假设你希望在几个小时内完成任务，而不是几个月，所以这不太可能是一个解决方案。

所以你需要以某种方式索引文件。 Lucene（通过pythonsolr）或Xapian应该适合你的目的。索引文件，然后搜索索引文件。

Answer 4

我不知道这种想法是愚蠢至极还是不行，请让我知道...

鸿沟的文件搜索到合理的字号10/100/1000 ......和每个“块”使用可用于SW的索引SW。这里我正在考虑ctagsgnu global或者ptx实用程序或使用此SO post中描述的技术。

使用这种技术，您“仅”需要搜索目标字符串的索引文件。

Answer 5

您应该使用使用动态算法重新评估的组模式匹配算法。即阿霍 - 科拉斯克。实现

• http://code.google.com/p/graph-expression/wiki/RegexpOptimization
• http://alias-i.com/lingpipe/docs/api/com/aliasi/dict/ExactDictionaryChunker.html