У меня возникли небольшие проблемы с некоторым кодом. Пожалуйста, имейте в виду, что я ужасный программист, поэтому мое решение, вероятно, не очень красноречиво (и, вероятно, причина, по которой у меня заканчивается память - у меня 4 гигабайта, и скрипт медленно ее заполняет).
Вот в чем проблема. У меня около 3500 файлов в каталоге. Каждый файл состоит из одной строки, в которой может быть относительно мало или много символов без пробелов (самый маленький файл имеет размер 200 байт, а самый большой — 1,3 мегабайта). То, что я пытаюсь сделать, это найти общую подстроку между этими двумя файлами за раз заданной длины (в приведенном ниже коде это 13 символов). Я делаю два за раз, потому что я не ищу общую подстроку среди всех них, а скорее комбинации двух, пока все файлы не будут сравнены. То есть любая общая подстрока заданной длины между файлами, а не подстрока, общая для всех них.
Я использую модуль дерева суффиксов, обертывающий реализацию C (здесь). Сначала я делаю список всех файлов в каталоге, затем ищу комбинации из двух, чтобы все комбинации были покрыты, я передаю два файла за раз в дерево суффиксов, а затем ищу последовательности, которые являются общими подстроками.
Тем не менее, я действительно не знаю, почему у него медленно заканчивается память. Я надеюсь, что мы можем внести поправку в код, чтобы он каким-то образом очищал память от неиспользуемых вещей? Очевидно, что 3500 файлов будут долго обрабатываться, но я надеюсь, что можно обойтись без инкрементального заполнения 4 гигабайт памяти. Любая помощь будет принята с благодарностью! Вот код, который у меня есть до сих пор:
from suffix_tree import GeneralisedSuffixTree
from itertools import combinations
import glob, hashlib, os
alist = open('tmp.adjlist', 'w')
def read_f(f):
f = open(f, "r")
s = str(f.readlines())
f.close()
return s
def read_gs(a,b):
s1 = read_f(a)
s2 = read_f(b)
print str(a) + ":" + str(hashlib.md5(s1).hexdigest()) + " --- " + str(b) + ":" + str(hashlib.md5(s2).hexdigest())
return [s1,s2]
def build_tree(s):
hlist = []
stree = GeneralisedSuffixTree(s)
for shared in stree.sharedSubstrings(13):
for seq,start,stop in shared:
hlist.append(hashlib.md5(stree.sequences[seq]).hexdigest())
hlist = list(set(hlist))
for h in hlist:
alist.write(str(h) + " ")
alist.write('\n')
glist = []
for g in glob.glob("*.g"):
glist.append(g)
for a,b in list(combinations(glist, 2)):
s = read_gs(a,b)
build_tree(s)
alist.close()
os.system("uniq tmp.adjlist network.adjlist && rm tmp.adjlist")
ОБНОВЛЕНИЕ №1
Вот обновленный код. Я добавил предложения Пирса. Однако после того, как jogojapan обнаружил утечку памяти в коде C, и учитывая, что это выходит за рамки моего опыта, я в конечном итоге выбрал гораздо более медленный подход. Если кто-то хорошо разбирается в этой области, мне было бы очень любопытно посмотреть, как изменить код C, чтобы исправить утечку памяти или функцию освобождения, поскольку я думаю, что привязка дерева суффиксов C для Python очень ценна. Вероятно, потребуется несколько дней, чтобы запустить данные через этот скрипт без дерева суффиксов, поэтому я определенно готов посмотреть, есть ли у кого-нибудь творческое исправление!
from itertools import combinations
import glob, hashlib, os
def read_f(f):
with open(f, "r") as openf:
s = str(openf.readlines())
return s
def read_gs(a,b):
s1 = read_f(a)
s2 = read_f(b)
print str(a) + ":" + str(hashlib.md5(s1).hexdigest()) + " --- " + str(b) + ":" + str(hashlib.md5(s2).hexdigest())
return [s1,s2]
def lcs(S1, S2):
M = [[0]*(1+len(S2)) for i in xrange(1+len(S1))]
longest, x_longest = 0, 0
for x in xrange(1,1+len(S1)):
for y in xrange(1,1+len(S2)):
if S1[x-1] == S2[y-1]:
M[x][y] = M[x-1][y-1] + 1
if M[x][y]>longest:
longest = M[x][y]
x_longest = x
else:
M[x][y] = 0
return S1[x_longest-longest: x_longest]
glist = glob.glob("*.g")
for a,b in combinations(glist, 2):
s = read_gs(a,b)
p = lcs(s[0],s[1])
if p != "" and len(p) >= 13:
with open("tmp.adjlist", "a") as openf:
openf.write(hashlib.md5(s[1]).hexdigest() + " " + hashlib.md5(s[0]).hexdigest() + "\n")
os.system("uniq tmp.adjlist network.adjlist && rm tmp.adjlist")
