计算(很大)文本中的(大量)字符串

|| 我在Stackoverflow上看到了“高效地在文件中搜索字符串”问题的几种变体,但与我的情况不太相似。 我有一个文本文件,其中包含相对大量(> 300K)的字符串。这些字符串中的绝大多数是多个单词(例如\“ Plessy v。Ferguson \”,\“ John Smith \”等)。 从那里,我需要搜索大量文本文件(一组合计> 10GB的法律文档),并计算这些字符串的实例。 由于搜索字符串的数量,具有多个单词的字符串以及搜索目标的大小,许多“标准”解决方案似乎掉到了一边。 有些事情可以简化问题- 我不需要复杂的标记化/词干提取等功能(例如,我关心的唯一实例是“ Plessy诉Ferguson”,无需担心“ Plessy”,“ Plessy等”)。 al。\“等) 会有一些重复项(例如,多个名为“ John Smith”的人),但是,对于此数据集,这在统计上不是很重要的问题,因此...如果将多个John Smith合并为一个单次统计,现在还可以。 我只需要计算这些特定实例;我不需要返回搜索结果 1个文件中的10个实例与10个文件中的每个实例中的1个实例相同 对解决此问题的快速/肮脏方法有什么建议吗? 我已经调查了NLTK,Lucene和其他公司,但是对于我要解决的问题,它们似乎过大了。我应该吸收它并将所有内容导入数据库吗? bruteforce grep 30万次? ;) 我首选的开发工具是Python。 要搜索的文档主要是这样的合法文档-http://www.lawnix.com/cases/plessy-ferguson.html 预期结果汇总了这些文档中引用案例的频率- “ Plessey诉Ferguson:15”     
已邀请:
        解决此问题的一种简单方法是用查询(仅是前缀树,内部有单个字符的节点列表)构建特里树,并且当您搜索10gb文件时,当文本匹配时,将递归地遍历树。 这样,您可以在搜索大文件中的每个字符位置时尽早地修剪大量选项,同时仍可以搜索整个解决方案空间。 时间性能将非常好(与许多其他更复杂的解决方案一样好),并且您只需要足够的空间来存储树(比整个字符串数组少很多),并且只需一个小的缓冲区即可文件。绝对比gdb压缩300k次要好得多...     
        您必须处理几个约束,这使这成为一个复杂的问题。 硬盘IO 记忆空间 处理时间 我建议编写一个多线程/多进程python应用程序。要进行子处理的库很轻松。将每个进程读入一个文件,并按照Blindy的建议读取解析树。完成后,它将结果返回给父级,父级将结果写入文件中。 这将消耗尽可能多的资源,同时允许扩展。如果将其粘贴在beowulf群集上,它将为您透明地跨cpus共享进程。 唯一的症结是硬盘驱动器IO。将其分成不同硬盘上的块,然后在每个进程完成时启动一个新文件并加载文件。如果您使用的是Linux,则所有文件都可以共存于同一文件系统名称空间中,而您的程序将不知道它们之间的区别。     
        丑陋的暴力解决方案无法正常工作。 在文档中花费一grep的时间并推断出300k greps所花费的时间(如果您有很多可用的机器,则可以尝试并行化),这是否可行?我的猜测是30万次搜索将不可行。例如,对大约50 Mb的文件进行一次搜索大约需要5 s,所以对于10 Gb,您可能希望约1000 s,然后重复进行30万次,则意味着在一台计算机上完成大约10年。您可以并行化以进行一些改进(受限于一台计算机上的磁盘io),但仍然会受到很大限制。我假设您希望任务在数小时而不是数月内完成,因此这不太可能解决。 因此,您将需要以某种方式对文档建立索引。 Lucene(例如通过pythonsolr)或Xapian应该适合您的目的。为文档建立索引,然后搜索被索引的文档。     

bab

您应该使用组模式匹配算法,该算法使用动态算法来重用评估。即Aho–Corasick。实作 http://code.google.com/p/graph-expression/wiki/RegexpOptimization http://alias-i.com/lingpipe/docs/api/com/aliasi/dict/ExactDictionaryChunker.html     
        我不知道这个想法是否非常愚蠢,请让我知道... 将要搜索的文件划分为合理大小的数字10/100/1000 ...,对于每个“块”,使用可用于SW的索引SW。在这里,我正在考虑全局使用ctags gnu或使用
ptx
实用程序,或使用本文中介绍的技术。 使用此技术,您“仅\”需要在索引文件中搜索目标字符串。     

要回复问题请先登录注册