1

我有两个具有以下行数的文件：

file1 - 110433003
file2 - 4838810

我需要在这些之间找到常用短语。每行的形式为：

p1 ||| p2 ||| …………

file1 的 p1 可以是 file2 中的 p2。不幸的是，我编写的代码要花很长时间才能做到这一点。 

import sys
import os

if(len(sys.argv)<2):
        print 'python CommonPhrases.py enFr hrEn commonFile'
        sys.exit()
enFr = open(sys.argv[1],'r')
hrEn = open(sys.argv[2],'r')
common = open(sys.argv[3],'w')
sethrEn = set([])
setenFr= set([])
for line in hrEn:
        englishPhrase = line.split(' ||| ')[1]
        sethrEn.add(englishPhrase)

for line in enFr:
        englishPhrase = line.split(' ||| ')[0]
        if(englishPhrase in sethrEn):
                common.write(englishPhrase+'\n')

有没有更快的方法来做到这一点？

谢谢

4

2 回答 2

0

这听起来像一个树问题。也许这个想法可以帮助你。

使用树可以帮助找到常用词。我认为基于创建树的想法可以有两种解决方案。

一棵树，一旦实现，将需要存储一个文件（只有一个文件）的每个单词。然后，开始读取第二个文件并在树中搜索该文件中的每个单词。

当然，这个解决方案有一些问题。在内存中存储这么多字（或行）的树可能需要大量 MB 的 RAM。

假设您设法使用固定数量的 RAM 来存储数据，因此，只计算数据本身（行的字符）。在最坏的情况下，您将需要 255^N 个字节，其中 N 是最长行的长度（假设您使用 almos 每个单词组合的 N 扩展）。因此，存储长度为 10 的字的所有可能组合，您将需要 1.16252367019e+24 字节的 RAM。那是很多。请记住，这个解决方案（据我所知）是“快的”，但需要的 RAM 可能比你能找到的更多。

所以，其他解决方案，非常非常慢，是读取文件 A 的一行，然后将其与文件 B 的每一行进行比较。它几乎不需要 RAM，但需要太多时间，也许你无法做到真的等待它。

所以，也许另一种解决方案是划分问题。

你说你有一个行列表，我们不知道它们是否按字母顺序排序。因此，也许您可​​以开始读取文件 A，并创建新文件。例如，每个新文件都将存储“A”起始行，其他以“B”开头的行等。然后，对文件 B 执行相同操作，结果是两个以“A”开头的文件行，一个用于原始 A 文件，另一个用于原始 B 文件。然后，将它们与一棵树进行比较。

在最好的情况下，行将被平均划分，让您在内存中使用树。在最坏的情况下，您将只完成一个文件，与起始 A 文件相同，因为可能所有行都以“A”开头。

因此，也许，如果文件仍然太大，您可以实现一种方法来划分更多文件，首先，按行上的第一个字符。然后，'A'开始行，将它们划分为'AA'，'AB'，'AC'等，当然，删除之前的划分文件，直到文件足够小，可以使用更好的方法搜索相同行（也许在内存上使用树）。

此解决方案也可能需要很长时间，但可能不会像低内存选项那样长，而且不需要太多内存即可工作。

这些是我此刻能想到的解决方案。也许他们工作，也许没有。

于 2012-12-22T00:55:59.533 回答
0

你肯定需要尝试这样的事情。似乎您将花费大部分时间来寻找匹配的集合。

此外，每次我发现自己试图让 python 运行得更快时，我都会切换到 pypy。( http://pypy.org/ ) 设置起来非常简单（只需下载二进制文件，将其放入路径中，然后将 #!/usr/bin/env python 更改为 #!/usr/bin/env pypy）和为此类任务提供 5-10 倍的加速。

有关使用 PyTrie 的参考实现，请参见下文。

#!/usr/bin/env pypy

import sys
import os
sys.path.append('/usr/local/lib/python2.7/dist-packages/PyTrie-0.1-py2.7.egg/')
from pytrie import SortedStringTrie as trie

if(len(sys.argv)<2):
        print 'python CommonPhrases.py enFr hrEn commonFile'
        sys.exit()
enFr = open(sys.argv[1],'r')
hrEn = open(sys.argv[2],'r')
common = open(sys.argv[3],'w')

sethrEn = trie()

for line in hrEn:
        englishPhrase = line.strip().split(' ||| ')[1]
        sethrEn[englishPhrase] = None

for line in enFr:
        englishPhrase = line.strip().split(' ||| ')[0]
        if(englishPhrase in sethrEn):
                common.write(englishPhrase+'\n')

请注意，它需要最少的更改（4 行），并且您需要安装 PyTrie 0.1。在我的 ubuntu 系统上，“sudo easy_install PyTrie”成功了。

希望有帮助。

于 2012-12-22T00:50:00.923 回答