наиболее часто встречающиеся подстроки с допуском

Question

Я пытаюсь найти наиболее часто используемые подстроки (определенной длины L) на строке, но допускающие определенный порог или ошибку T (в позиции подпоследовательностей), очевидно, не более L сам. Однако до сих пор я не добился успеха. Как я могу заполнить код?

stn='KLHLHLHKPLHLHLPHHKLH' 
L = 4 #(lenght of the pattern) 
T = 1 #(maximum tolerance or permitted error in any position of the query pattern) 

pattcount = {} 
for n in range(len(stn)- L+1): 
patt = stn[n:n+L] 
s_ = stn[i:i+len(patt)] 
if LevenshteinDistance(s_, patt) == T: 
pattcount[patt] = pattcount[patt] + 1 if pattcount.has_key(patt) else 1 

max = 0 
max_patt = [] 
for p,v in pattcount.iteritems(): 
if v > max: 
max_patt = [p] 
max = v 
elif v == max: 
max_patt += [p] 
print (" ".join(max_patt)) 

Поэтому, например, если наиболее часто является KLH, как может частоты чЛГ, PLH, КРП, KPH раздуть частоты KLH (для того, чтобы быть сообщено)?

Answer 1

>>> from Levenshtein import distance 
>>> from collections import defaultdict 
>>> tups = [stn[i:i+L] for i in range(0, len(stn) - (L - 1))] 
>>> print tups 
['KLHL', 'LHLH', 'HLHL', 'LHLH', 'HLHK', 'LHKP', 'HKPL', 'KPLH', 'PLHL', 'LHLH', 
'HLHL', 'LHLP', 'HLPH', 'LPHH', 'PHHK', 'HHKL', 'HKLH'] 
>>> d = defaultdict(list) 
>>> [d[x].append(y) for x in tups for y in tups 
            if x is not y and distance(x, y) <= T] 
>>> print d 
defaultdict(<type 'list'>, { 
       'KLHL': ['HLHL', 'PLHL', 'HLHL'], 
       'LHLP': ['LHLH', 'LHLH', 'LHKP', 'LHLH'], 
       'HLHK': ['HLHL', 'HLHL'], 
       'HLHL': ['KLHL', 'HLHK', 'PLHL', 'KLHL', 'HLHK', 'PLHL'], 
       'LHKP': ['LHLP'], 
       'LHLH': ['LHLP', 'LHLP', 'LHLP'], 
       'PLHL': ['KLHL', 'HLHL', 'HLHL']}) 
>>> s = sorted(d.iterkeys(), key=lambda k: len(d[k]), reverse=True) 
>>> print s 
['HLHL', 'LHLP', 'KLHL', 'LHLH', 'PLHL', 'HLHK', 'LHKP']