查找文件之間常用短語與百萬行

我有兩個文件具有以下行數：查找文件之間常用短語與百萬行

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')

有沒有更快的方法來做到這一點？

謝謝

來源

2012-12-21 crazyaboutliv

python是否有一個trie實現？ – James

它似乎有一個http://packages.python.org/PyTrie/ – crazyaboutliv

如果你在一個像unix系統，並且如果每個文件只包含一個短語，那麼你可以試試這個。將每個短語放入它自己的行中，然後按|排序uniq -c。另見http://www.stanford.edu/class/cs124/kwc-unix-for-poets.pdf – Himanshu

你絕對需要一個像這樣的東西。看起來你會花大部分時間在比賽中尋找比賽。

另外，每當我發現自己試圖讓python走得更快，我切換到pypy。（http://pypy.org/）設置非常簡單（只需下載二進制文件，將其放入路徑並將＃！/ usr/bin/env python更改爲＃！/ usr/bin/env pypy），並在5-10x這樣的任務。

有關使用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-22 00:50:00 vkontori

這聽起來像一個樹問題。也許這個想法可以幫助你。

使用樹可以幫助找到常用詞。我認爲基於創建樹的想法可以有兩種解決方案。

樹一旦實現，將需要存儲一個文件的每個單詞（只有一個文件）。然後，開始閱讀第二個文件並搜索樹中該文件的每個單詞。

這個解決方案當然有一些問題。在記憶這些數量的單詞（或行）時存儲樹可能需要大量的RAM。

假設您設法使用固定數量的RAM來存儲數據，所以只計算數據本身（行的字符）。在最壞的情況下，您需要255^N個字節，其中N是最長行的長度（假設您使用的是每個N擴展的字組合）。因此，存儲長度爲10的單詞的所有可能組合，您將需要1.16252367019e + 24字節的RAM。這很多。記住，這個解決方案（據我所知）是「快速」的，但是需要更多的內存。

因此，其他解決方案非常慢，正在讀取文件A的一行，然後將它與文件B的每一行進行比較。它幾乎不需要任何RAM，但需要太多時間，或許您會無法真正等待它。

因此，也許另一個解決方案是分解問題。

你說你有一個行的列表，我們不知道他們是按字母順序排序或沒有。所以，也許你可以開始閱讀文件A，並創建新的文件。例如，每個新文件都將存儲'A'起始行，其他以'B'開頭的行等等。然後，對文件B執行相同的操作，並且結果具有兩個啓動了'A'的文件行，一個用於原始A文件，另一個用於原始B文件。然後，將它們與一棵樹進行比較。

在最好的情況下，行會被平分，讓你在內存中使用樹。在最糟糕的情況下，您將只完成一個文件，與起始A文件相同，因爲可能所有行都以'A'開始。

所以，也許你可以實現一種方法來分割更多的文件，如果它們仍然太大，首先，通過第一個字符的行。然後，'A'的起始行將它們分爲'AA'，'AB'，'AC'等等，當然，刪除以前的分割文件，直到你得到足夠小的文件以使用更好的方法來搜索相同的文件行（可能在內存中使用樹）。

該解決方案也可能需要很長時間，但可能不會長時間低ram選項，也不需要太多的ram工作。

這些是我現在可以想到的解決方案。也許他們工作，也許不行。

來源

2012-12-22 00:55:59

查找文件之間常用短語與百萬行

回答

相關問題