用python搜索大文件中字符串的更快方法

Question

我有两个文本文件需要处理。这是我的情况：

• 这两个文件非常大，一个是1.21 GB，另一个是1.1 GB。他们每个包含约3000多万行中文字符串。
• 每个文件中的每个字符串都是唯一的。
• 我不必修改这些文件，一旦它们被加载，它们就不会改变。

的一点是，这些文件中的一个已损坏。我们称之为N5。 N5应该有串的每一行看起来是这样的： 'A5 B5 C5 D5 E5 \ TF5'

相反，它是： 'a5b5 C5 D5 E5 \ TF5'

我从另一个文件试图恢复它，让我们把它N4，它看起来像这样： 'A4 B4 C4 D4 \ TF4'

我试图用N4至N5分离a5b5，这可能有三种结果做：

1. 'a4 b4 c4 d4'等于'a5 b5 c5 d5'
2. 'a4 b4 c4 d4'等于'b5 c5 d5 e5'
3. N5中没有N4匹配。

在情况1和2，我可以得到答案。但是，在3中，大约需要140秒才能在N4中完成搜索。

我现在使用列表来存储N4和N5，下面是我的代码来比较它们。

# test data 
N4 = ['a1 b1 c1 e1\t3', 'a2 b2 c2 e2\t2', 'c3 e3 f3 g3\t3'] 
N5 = ['a1b1 c1 e1 f1\t2', 'a2b c2 e2 f2\t1', 'b3c3 e3 f3 g3\t3'] 

# result stroage 
list_result = [] 
list_result_no_none = [] 

counter_none = 0 

list_len = len(N4) 

for each_item in N5: 
    counter_list_len = 0 
    list_str_2 = str(each_item).split(' ') 
    list_str_2_2 = str(list_str_2[3]).split('\t') 
    str_list_str_2_0 = str(list_str_2[0]) 
    for each_item in N4: 
     list_str_1 = str(each_item).split(' ') 
     list_str_1_2 = str(list_str_1[3]).split('\t') 

     # if n4 y == n5 
     if (str(list_str_1[0])+str(list_str_1[1]) == str(list_str_2[0]) and \ 
      (str(list_str_1[2]) == str(list_str_2[1]) and \ 
      (str(list_str_1_2[0]) == str(list_str_2[2])) and \ 
      (str(list_str_1_2[1]) >= str(list_str_2_2[1])))) : 

      list_result.append(list_str_1[0] +' '+ list_str_1[1] +' '+ list_str_1[2] +' '+ list_str_1_2[0] +' '+ list_str_2[3]) 
      list_result_no_none.append(list_str_1[0] +' '+ list_str_1[1] +' '+ list_str_1[2] +' '+ list_str_1_2[0] +' '+ list_str_2[3]) 
     break 

     # if x n4 == n5 
     elif ((str(list_str_1[0]) in (str(list_str_2[0]))) and \ 
      (str(list_str_1[1]) == str(list_str_2[1])) and \ 
      (str(list_str_1[2]) == str(list_str_2[2])) and \ 
      (str(list_str_1_2[0]) == str(list_str_2_2[0]) and \ 
      (str(list_str_1_2[1]) >= str(list_str_2_2[1])))): 

      list_result.append(str_list_str_2_0[0:(str(list_str_2[0]).find(str(list_str_1[0])))]\ 
      +' '+ str_list_str_2_0[(str(list_str_2[0]).find(str(list_str_1[0]))):len(list_str_2[0])]\ 
      +' '+ list_str_1[1] +' '+ list_str_1[2] +' '+ list_str_2[3]) 
     list_result_no_none.append(str_list_str_2_0[0:(str(list_str_2[0]).find(str(list_str_1[0])))]\ 
      +' '+ str_list_str_2_0[(str(list_str_2[0]).find(str(list_str_1[0]))):len(list_str_2[0])]\ 
      +' '+ list_str_1[1] +' '+ list_str_1[2] +' '+ list_str_2[3]) 
     break 

     # not found 
     else: 
      counter_list_len += 1 
      if counter_list_len == list_len: 
       list_result.append('none' +' '+ list_str_2[0] +' '+ list_str_2[1] +' '+ list_str_2[2] +' '+ list_str_2[3]) 
       counter_none += 1 


print(list_result) 
print(list_result_no_none) 
print("Percentage of not found: %.2f" % ((100*(counter_none/len(N5)))) + '%') 

它工作在小规模，然而，它需要在真实文件上运行的时间。

我是python的新手，在其他编程语言方面经验不多。所以如果我的问题看起来很愚蠢，我很抱歉。另外，我不是母语的人，所以对我英语不好的道歉。

Answer 1

您可以将一些列表转换为生成器，这大大减少了内存消耗。只有N4名单必须在内存中，因为它是经过很多次：

N4的

def iter_file(filename): 
    with open(filename) as inp: 
     for line in inp: 
      line = line.split(' ') 
      yield line[:-1] + line[-1].split('\t') 

def do_correction(n4, n5): 
    n4 = list(n4) 

    for words_n5 in n5: 
     for words_n4 in n4: 

      # if n4 y == n5 
      if (words_n4[0]+words_n4[1] == words_n5[0] and 
       words_n4[2] == words_n5[1] and 
       words_n4[3] == words_n5[2] and 
       words_n4[4] >= words_n5[3]): 
       yield words_n4[:-1] + words_n5[3:] 
       break 

      # if x n4 == n5 
      elif (words_n4[0] in words_n5[0] and 
       words_n4[1] == words_n5[1] and 
       words_n4[2] == words_n5[2] and 
       words_n4[3] == words_n5[3] and 
       words_n4[4] >= words_n5[4]): 
       idx = words_n5[0].find(words_n4[0]) 
       yield [words_n5[:idx], words_n5[idx:]], words_n5[1:] 
       break 
     else: # not found 
      yield ['none'] + words_n5 

with open('corrected', 'w') as output: 
    for words in do_correction(iter_file('N4'), iter_file('N5')): 
     output.write('%s\t%s' %(' '.join(words[:-1]), words[-1])) 

接下来，你可以将零为字典，这使得查找更快：我

from collections import defaultdict 

def iter_file(filename): 
    with open(filename) as inp: 
     for line in inp: 
      line = line.split(' ') 
      yield line[:-1] + line[-1].split('\t') 

def do_correction(n4, n5): 
    n4_dict = defaultdict(list) 
    for words_n4 in n4: 
     n4[words_n4[2], words_n4[3]].append(words_n4) 

    for words_n5 in n5: 
     words_n4 = next(
      (words_n4 for words_n4 in n4_dict[words_n5[1], words_n5[2]] 
       if (words_n4[0]+words_n4[1] == words_n5[0] and 
       words_n4[4] >= words_n5[3])), 
      None) 
     if words_n4: 
      yield words_n4[:-1] + words_n5[3:] 
     else: 
      words_n4 = next(
       (words_n4 for words_n4 in n4_dict[words_n5[2], words_n5[3]] 
        if (words_n4[0] in words_n5[0] and 
        words_n4[1] == words_n5[1] and 
        words_n4[4] >= words_n5[4])), 
       None) 
      if words_n4: 
       idx = words_n5[0].find(words_n4[0]) 
       yield [words_n5[:idx], words_n5[idx:]], words_n5[1:] 
      else: # not found 
       yield ['none'] + words_n5 

with open('corrected', 'w') as output: 
    for words in do_correction(iter_file('N4'), iter_file('N5')): 
     output.write('%s\t%s' %(' '.join(words[:-1]), words[-1]))