wake-up-neo.net

zeichenfolgenanzahl mit überlappenden Vorkommen

Was ist der beste Weg, um die Anzahl der Vorkommen einer bestimmten Zeichenfolge zu zählen, einschließlich der Überlappung in Python? ist es der naheliegendste Weg:

def function(string, str_to_search_for):
      count = 0
      for x in xrange(len(string) - len(str_to_search_for) + 1):
           if string[x:x+len(str_to_search_for)] == str_to_search_for:
                count += 1
      return count


function('1011101111','11')
returns 5

?

oder gibt es einen besseren Weg in Python?

45
calccrypto

Nun, diese könnte schneller sein, da sie den Vergleich in C durchführt:

def occurrences(string, sub):
    count = start = 0
    while True:
        start = string.find(sub, start) + 1
        if start > 0:
            count+=1
        else:
            return count
64
Jochen Ritzel
>>> import re
>>> text = '1011101111'
>>> len(re.findall('(?=11)', text))
5

Wenn Sie nicht die gesamte Liste der Übereinstimmungen in den Speicher laden möchten, wäre dies niemals ein Problem! Sie könnten dies tun, wenn Sie wirklich wollten:

>>> sum(1 for _ in re.finditer('(?=11)', text))
5

Als Funktion (re.escape stellt sicher, dass die Teilzeichenfolge den regulären Ausdruck nicht beeinträchtigt):

>>> def occurrences(text, sub):
        return len(re.findall('(?={0})'.format(re.escape(sub)), text))

>>> occurrences(text, '11')
5
36
jamylak

Sie können auch das neue Python-Regex-Modul verwenden, das überlappende Übereinstimmungen unterstützt.

import regex as re

def count_overlapping(text, search_for):
    return len(re.findall(search_for, text, overlapped=True))

count_overlapping('1011101111','11')  # 5
9
David C

str.count von Python zählt nicht überlappende Teilzeichenfolgen:

In [3]: "ababa".count("aba")
Out[3]: 1

Hier sind ein paar Möglichkeiten, überlappende Sequenzen zu zählen. Ich bin mir sicher, dass es noch mehr gibt :)

Vorausschauende reguläre Ausdrücke

Wie finde ich überlappende Übereinstimmungen mit einem Regex?

In [10]: re.findall("a(?=ba)", "ababa")
Out[10]: ['a', 'a']

Generieren Sie alle Teilzeichenfolgen

In [11]: data = "ababa"
In [17]: sum(1 for i in range(len(data)) if data.startswith("aba", i))
Out[17]: 2
8
Dima Tisnek
s = "bobobob"
sub = "bob"
ln = len(sub)
print(sum(sub == s[i:i+ln] for i in xrange(len(s)-(ln-1))))
3

So finden Sie ein Muster in einer anderen Zeichenfolge mit Überlappung

Diese Funktion (eine andere Lösung!) Erhält ein Muster und einen Text. Gibt eine Liste mit allen untergeordneten Zeichenfolgen und deren Positionen zurück.

def occurrences(pattern, text):
    """
    input: search a pattern (regular expression) in a text
    returns: a list of substrings and their positions 
    """
    p = re.compile('(?=({0}))'.format(pattern))
    matches = re.finditer(p, text)
    return [(match.group(1), match.start()) for match in matches]

print (occurrences('ana', 'banana'))
print (occurrences('.ana', 'Banana-fana fo-fana'))

[('ana', 1), ('ana', 3)] 
[('Bana', 0), ('Nana', 2), ('Fana', 7), ('Fana', 15)]

3
def count_substring(string, sub_string):
    count = 0
    for pos in range(len(string)):
        if string[pos:].startswith(sub_string):
            count += 1
    return count

Dies könnte der einfachste Weg sein.

2
Arun Tom

Meine Antwort auf die Bob-Frage zum Kurs:

s = 'azcbobobegghaklbob'
total = 0
for i in range(len(s)-2):
    if s[i:i+3] == 'bob':
        total += 1
print 'number of times bob occurs is: ', total
2
Luke D

Ein ziemlich pythonischer Weg wäre, Listenverständnis hier zu verwenden, obwohl es wahrscheinlich nicht der effizienteste wäre.

sequence = 'abaaadcaaaa'
substr = 'aa'

counts = sum([
    sequence.startswith(sub, i) for i in range(len(sequence))
])
print(counts)  # 5

Die Liste wäre [False, False, True, False, False, False, True, True, False, False], da alle Indizes durch die Zeichenfolge geprüft werden, und weil int(True) == 1, sum die Gesamtzahl der Übereinstimmungen angibt.

1
ParkerD
def count_substring(string, sub_string):
    counter = 0
    for i in range(len(string)):
        if string[i:].startswith(sub_string):
        counter = counter + 1
    return counter

Der obige Code durchläuft einfach einmal den gesamten String und prüft ständig, ob ein String mit dem bestimmten Teilstring beginnt, der gerade gezählt wird.

1
Anshul Tiwari

Hier ist mein edX MIT "find bob" * -Lösung (* find Anzahl von "bob" -Ereignissen in einem String mit dem Namen s), der in der Regel überlappende Vorkommen einer gegebenen Unterstufe zählt:

s = 'azcbobobegghakl'
count = 0

while 'bob' in s:
    count += 1 
    s = s[(s.find('bob') + 2):]

print "Number of times bob occurs is: {}".format(count)
1
dasdachs

Das kann mit Regex gelöst werden.

import re
def function(string, sub_string):
    match = re.findall('(?='+sub_string+')',string)
    return len(match)
1

Wenn die Zeichenfolgen groß sind, möchten Sie Rabin-Karp verwenden, zusammenfassend:

  • ein rollendes Fenster mit der Größe eines Teilstrings, das sich über einem String bewegt
  • ein Hash mit O(1) Overhead zum Hinzufügen und Entfernen (d. h. Verschieben um 1 Zeichen)
  • in C implementiert oder auf Pypy angewiesen
0
Dima Tisnek

Dies ist ein weiteres Beispiel für die Verwendung von str.find(), aber viele Antworten machen es komplizierter als nötig:

def occurrences(text, sub):
    c, n = 0, text.find(sub)
    while n != -1:
        c += 1
        n = text.find(sub, n+1)
    return c

In []:
occurrences('1011101111', '11')

Out[]:
5
0
AChampion

Eine einfache Möglichkeit, das Auftreten von Teilzeichenfolgen zu zählen, ist die Verwendung von count():

>>> s = 'bobob'
>>> s.count('bob')
1

Sie können replace () verwenden, um überlappende Zeichenfolgen zu finden, wenn Sie wissen, welcher Teil überlappt:

>>> s = 'bobob'
>>> s.replace('b', 'bb').count('bob')
2

Beachten Sie, dass es nicht nur statische, sondern auch andere Einschränkungen gibt:

>>> s = 'aaa'
>>> count('aa') # there must be two occurrences
1 
>>> s.replace('a', 'aa').count('aa')
3
0
danbros

Gegeben

sequence = '1011101111'
sub = "11"

Code

In diesem speziellen Fall

sum(x == Tuple(sub) for x in Zip(sequence, sequence[1:]))
# 5

Ganz allgemein dies

windows = Zip(*([sequence[i:] for i, _ in enumerate(sequence)][:len(sub)]))
sum(x == Tuple(sub) for x in windows)
# 5

oder auf Generatoren erweitern:

import itertools as it


iter_ = (sequence[i:] for i, _ in enumerate(sequence))
windows = Zip(*(it.islice(iter_, None, len(sub))))
sum(x == Tuple(sub) for x in windows)

Alternative

Sie können more_itertools.locate verwenden:

import more_itertools as mit


len(list(mit.locate(sequence, pred=lambda *args: args == Tuple(sub), window_size=len(sub))))
# 5
0
pylang

Funktion, die als Eingabe zwei Zeichenfolgen übernimmt und zählt, wie oft ein Teil in Zeichenfolgen auftritt, einschließlich Überlappungen. Um zu prüfen, ob Sub eine Unterzeichenfolge ist, habe ich den Operator in verwendet. 

def count_Occurrences(string, sub):
    count=0
    for i in range(0, len(string)-len(sub)+1):
        if sub in string[i:i+len(sub)]:
            count=count+1
    print 'Number of times sub occurs in string (including overlaps): ', count
0
Aquila3000

Für eine duplizierte question habe ich mich entschieden, sie 3 mal 3 zu zählen und die Zeichenfolge zu vergleichen, z.

counted = 0

for i in range(len(string)):

    if string[i*3:(i+1)*3] == 'xox':
       counted = counted +1

print counted
0
AndreL
def count_overlaps (string, look_for):
    start   = 0
    matches = 0

    while True:
        start = string.find (look_for, start)
        if start < 0:
            break

        start   += 1
        matches += 1

    return matches

print count_overlaps ('abrabra', 'abra')
0
doublep

Eine Alternative, die der akzeptierten Antwort sehr nahe kommt, jedoch while als if-Test verwendet, anstatt if in die Schleife einzufügen:

def countSubstr(string, sub):
    count = 0
    while sub in string:
        count += 1
        string = string[string.find(sub) + 1:]
    return count;

Dies vermeidet while True: und ist meiner Meinung nach ein wenig sauberer

0
stevoblevo