Biorąc pod uwagę ciąg, który chcę liczyć, ile substrings z Len = 5 mam na nim.

Na przykład: wejście: "ABCDEFG" Wyjście: 3

I nie jestem pewien, co powinno być najłatwiejszym i szybkim sposobem na to w Pythonie. Dowolny pomysł?

Aktualizacja:

Chcę tylko policzyć różne podciągi.

Wejście: "AAAAAA" Substrings: 2 razy wyjście "AAAAA": 1

6
adolfosrs 13 sierpień 2014, 01:57

7 odpowiedzi

Najlepsza odpowiedź
>>> n = 5
>>> for s in 'ABCDEF', 'AAAAAA':
...     len({s[i:i+n] for i in range(len(s)-n+1)})
... 
2
1
3
jfs 12 sierpień 2014, 23:19

Aby uzyskać smyczki, które możesz użyć nltk w ten sposób:

>>> from nltk.util import ngrams
>>> for gram in ngrams("ABCDEFG", 5):
...     print gram
... 
('A', 'B', 'C', 'D', 'E')
('B', 'C', 'D', 'E', 'F')
('C', 'D', 'E', 'F', 'G')

Możesz zastosować Licznik, a następnie zdobądź unikalne n-gramów (i ich częstotliwość) jak więc:

>>> Counter(ngrams("AAAAAAA", 5))
Counter({('A', 'A', 'A', 'A', 'A'): 3})
2
Jason Sperske 12 sierpień 2014, 22:19

Używanie rozumienia listy (Kod Golf) :

findSubs=lambda s,v:[''.join([s[i+j] for j in range(v)]) for i,x in enumerate(s) if i<=len(s)-v]
findCount=lambda s,v:len(findSubs(s,v))

print findSubs('ABCDEFG', 5)  #returns ['ABCDE', 'BCDEF', 'CDEFG']
print findCount('ABCDEFG', 5) #returns 3

Aktualizuj

W przypadku aktualizacji można rzucić listę powyżej do zestawu, z powrotem do listy, a następnie posortuj struny.

findUnique=lambda s,v:sorted(list(set(findSubs(s,v))))
findUniqueCount=lambda s,v:len(findUnique(s,v))

print findUnique('AAAAAA', 5)      #returns ['AAAAA']
print findUniqueCount('AAAAAA', 5) #returns 1
2
Mr. Polywhirl 12 sierpień 2014, 22:27

To tylko długość minus 4:

def substrings(s):
    return len(s) - 4

Jest to prawda, ponieważ możesz stworzyć poduszkę na pierwszą, drugą, ..., piąty do ostatniego znaku jako pierwszej litery podciągu.

1
pascalhein 12 sierpień 2014, 22:02

Ogólne rozwiązanie może być:

def count(string, nletters):
  return max(0, len(string) - nletters + 1)

Który ma przypadek użytkowania zgodnie z przykładem:

print count("ABCDEFG", 5)
1
blitzen 12 sierpień 2014, 22:03
>>> how_much = lambda string, length: max(len(string) - length + 1, 0)
>>> how_much("ABCDEFG", 5)
3
1
vil 12 sierpień 2014, 22:04

Jestem prawie pewien, że Python nie jest dobrym językiem, aby to zrobić, ale jeśli długość odrębnych substringów, które chcesz znaleźć, nie jest mały jak 5, ale większy jak 1000, gdzie twój główny ciąg jest bardzo długi, a następnie liniowy roztwór czasowy Twoim problemem jest zbudowanie drzewa przyrostka, możesz przeczytać o nich online. Drzewo przyrostek do ciągów długości N może być zbudowany w czasie O (N) i przemierzanie drzewa zajmuje również czas O (N) i przemierzając wyższe poziomy drzewa, które możesz liczyć wszystkie różne podciągi o określonej długości, Również w czasie O (N), niezależnie od długości substrings, które chcesz.

1
user2566092 13 sierpień 2014, 16:52