從非常大的文件中刪除罕見單詞

Question

給定一個非常大的文本文件，我想刪除文件中只出現一次的所有單詞。有沒有簡單有效的方法來做到這一點？

最好的問候，

Answer 1

很難知道沒有具體的代碼來引用，但一個良好的開端可能是Natural Language Toolkit for Python。

Answer 2

你必須通過文件做2遍：

在通1：

• 建立一個使用單詞作爲鍵和它們的出現爲值的字典（即你讀每次總之，加1到它在字典中值）
• 然後預處理列表中刪除所有鍵與大於1的值，這是現在你的「黑名單」

在通2：

• 再次通讀文件，並刪除任何在黑名單中匹配的詞。

運行時間：

• 線性時間閱讀兩道文件。
• 它需要O（1）在通1.
• 每個單詞添加到詞典/遞增其值這需要O（n）的預過程的字典入黑名單。
• 它需要O（1）爲黑名單查找在通2.

O（n）的複雜性

Answer 3

2穿過該文件是絕對必要的。但是，如果罕見的詞語非常罕見，那麼您可以在第二遍中跳過標記大部分文件。首先逐字地傳遞文件並構建一個字典，其中包含一次遇到的單詞的找到位置或兩次遇到單詞的佔位符值。

MULTI_WORD = -1 
word_locations = {} 

for pos, word in tokenize(input_file): 
    if word not in word_locations: 
     word_locations[word] = pos 
    else: 
     word_locations[word] = MULTI_WORD 

然後你就可以過濾掉，你需要做編輯的位置，做一個普通的副本上休息：

edit_points = [(pos, len(word)) for word, pos in word_locations.iteritems() 
           if pos != MULTI_WORD] 

start_pos = 0 
for end_pos, edit_length in edit_points: 
    input_file.seek(start_pos) 
    output_file.write(input_file.read(end_pos - start_pos)) 
    start_pos = end_pos + edit_length 
input_file.seek(start_pos) 
output_file.write(input_file.read()) 

您可能需要一對夫婦更優化的，像塊明智副本程序來節省內存開銷和沒有編輯點的特殊情況。