Suchen Sie das n-te Vorkommen von Teilzeichenfolgen in einer Zeichenfolge

117

Dies scheint ziemlich trivial zu sein, aber ich bin neu bei Python und möchte es auf die pythonischste Art und Weise tun.

Ich möchte den Index finden, der dem n-ten Vorkommen eines Teilstrings innerhalb eines Strings entspricht.

Es muss etwas geben, das dem entspricht, was ich tun möchte, nämlich

mystring.find("substring", 2nd)

Wie können Sie dies in Python erreichen?

Prestomation
quelle
7
Finden Sie das n-te Vorkommen der Zeichenfolge? Ich nehme an, es bedeutet den Index des n-ten Auftretens?
Mark Byers
2
Ja, der Index des n-ten Vorkommens
Prestomation
9
Was soll passieren, wenn sich Übereinstimmungen überschneiden? Sollte find_nth ('aaaa', 'aa', 2) 1 oder 2 zurückgeben?
Mark Byers
Ja! Es muss etwas geben, um das n-te Vorkommen eines Teilstrings in einer Zeichenfolge zu finden und den String beim n-ten Auftreten eines Teilstrings zu teilen.
Reman

Antworten:

69

Marks iterativer Ansatz wäre der übliche Weg, denke ich.

Hier ist eine Alternative mit String-Aufteilung, die häufig nützlich sein kann, um verwandte Prozesse zu finden:

def findnth(haystack, needle, n):
    parts= haystack.split(needle, n+1)
    if len(parts)<=n+1:
        return -1
    return len(haystack)-len(parts[-1])-len(needle)

Und hier ist ein kurzer (und etwas schmutziger, da Sie eine Spreu auswählen müssen, die nicht zur Nadel passt) Einzeiler:

'foo bar bar bar'.replace('bar', 'XXX', 1).find('bar')
Bobince
quelle
7
Der erste Vorschlag wird für große Saiten sehr ineffizient sein, wenn das Match, an dem Sie interessiert sind, kurz vor dem Beginn steht. Es sieht immer die ganze Saite an. Es ist klug, aber ich würde es niemandem empfehlen, der neu in Python ist und nur einen guten Weg lernen möchte, es zu tun.
Mark Byers
3
Danke, ich mag deinen Einzeiler. Ich denke nicht, dass es das am schnellsten lesbare Ding der Welt ist, aber es ist nicht viel schlimmer als die meisten anderen unten
Prestomation
1
+1 für den Einzeiler, das sollte mir jetzt helfen. Ich hatte darüber nachgedacht, das Äquivalent von zu tun .rfind('XXX'), aber das würde auseinanderfallen, wenn es 'XXX'später in der Eingabe erscheint.
Nikhil Chelliah
Diese Funktion nimmt n = 0, 1, 2, 3, ... an. Es wäre schön, wenn Sie n = 1, 2, 3, 4, ... annehmen würden.
Happy
75

Hier ist eine pythonischere Version der einfachen iterativen Lösung:

def find_nth(haystack, needle, n):
    start = haystack.find(needle)
    while start >= 0 and n > 1:
        start = haystack.find(needle, start+len(needle))
        n -= 1
    return start

Beispiel:

>>> find_nth("foofoofoofoo", "foofoo", 2)
6

Wenn Sie die n - te finden wollen überlappende Vorkommen needle, können Sie erhöhen , indem 1stattlen(needle) , wie folgt aus :

def find_nth_overlapping(haystack, needle, n):
    start = haystack.find(needle)
    while start >= 0 and n > 1:
        start = haystack.find(needle, start+1)
        n -= 1
    return start

Beispiel:

>>> find_nth_overlapping("foofoofoofoo", "foofoo", 2)
3

Dies ist einfacher zu lesen als Marks Version und erfordert weder den zusätzlichen Speicher der Teilungsversion noch das Importieren eines Moduls für reguläre Ausdrücke. Im Gegensatz zu den verschiedenen Ansätzen werden auch einige Regeln im Zen of Pythonre eingehalten:

  1. Einfach ist besser als komplex.
  2. Wohnung ist besser als verschachtelt.
  3. Lesbarkeit zählt.
Todd Gamblin
quelle
Kann das in einer Zeichenfolge gemacht werden? Wie find_nth (df.mystring.str, ('x'), 2), um die Position der 2. Instanz von 'x' zu finden?
Arthur D. Howland
36

Dies findet das zweite Vorkommen von Teilzeichenfolgen in Zeichenfolgen.

def find_2nd(string, substring):
   return string.find(substring, string.find(substring) + 1)

Bearbeiten: Ich habe nicht viel über die Leistung nachgedacht, aber eine schnelle Rekursion kann helfen, das n-te Vorkommen zu finden:

def find_nth(string, substring, n):
   if (n == 1):
       return string.find(substring)
   else:
       return string.find(substring, find_nth(string, substring, n - 1) + 1)
Sriram Murali
quelle
Kann dies allgemein erweitert werden, um das n-te Element zu finden?
ifly6
Dies ist meiner Meinung nach die beste Antwort. Ich habe eine kleine Ergänzung für den Sonderfall gemacht, bei dem n = 0
Jan Wilmans
Ich wollte den Beitrag der Kürze halber nicht bearbeiten. Ich stimme Ihnen jedoch zu, dass n = 0 als Sonderfall behandelt werden sollte.
Sriram Murali
Dies sollte angepasst werden, um den Fall zu behandeln, in dem weniger als nder Teilstring vorkommt. (In diesem Fall durchläuft der Rückgabewert regelmäßig alle Vorkommenspositionen.)
Coldfix
28

Da Regex nicht immer die beste Lösung ist, würde ich hier wahrscheinlich eine verwenden:

>>> import re
>>> s = "ababdfegtduab"
>>> [m.start() for m in re.finditer(r"ab",s)]
[0, 2, 11]
>>> [m.start() for m in re.finditer(r"ab",s)][2] #index 2 is third occurrence 
11
Mark Peters
quelle
4
Hier besteht natürlich das Risiko, dass die zu suchende Zeichenfolge Sonderzeichen enthält, die dazu führen, dass der reguläre Ausdruck etwas tut, was Sie nicht wollten. Die Verwendung von re.escape sollte dies lösen.
Mark Byers
1
Das ist klug, aber ist es wirklich Pythonic? Scheint übertrieben, nur das n-te Vorkommen eines Teilstrings zu finden, und es ist nicht gerade einfach zu lesen. Auch, wie Sie sagen, müssen Sie alle re dafür importieren
Todd Gamblin
Wenn Sie eckige Klammern verwenden, weisen Sie Python an, die gesamte Liste zu erstellen. Runde Klammern würden nur durch die ersten Elemente iterieren, was effektiver ist:(m.start() for m in re.finditer(r"ab",s))[2]
Emu
1
@emu Nein, was du gepostet hast, funktioniert nicht. Sie können keinen Index eines Generators nehmen.
Mark Amery
@ MarkAmery sorry! Ich bin ziemlich überrascht, warum ich diesen Code gepostet habe. Dennoch ist eine ähnliche und hässliche Lösung mit der itertools.isliceFunktion möglich:next(islice(re.finditer(r"ab",s), 2, 2+1)).start()
Emu
17

Ich biete einige Benchmarking-Ergebnisse an, in denen die wichtigsten bisher vorgestellten Ansätze verglichen werden, nämlich @ bobince's findnth()(basierend auf str.split()) mit @ tgamblin's oder @Mark Byers find_nth()(basierend auf str.find()). Ich werde auch mit einer C-Erweiterung ( _find_nth.so) vergleichen, um zu sehen, wie schnell wir gehen können. Hier ist find_nth.py:

def findnth(haystack, needle, n):
    parts= haystack.split(needle, n+1)
    if len(parts)<=n+1:
        return -1
    return len(haystack)-len(parts[-1])-len(needle)

def find_nth(s, x, n=0, overlap=False):
    l = 1 if overlap else len(x)
    i = -l
    for c in xrange(n + 1):
        i = s.find(x, i + l)
        if i < 0:
            break
    return i

Natürlich ist die Leistung am wichtigsten, wenn die Zeichenfolge groß ist. Nehmen wir also an, wir möchten die 1000001. erste Zeile ('\ n') in einer 1,3-GB-Datei namens 'bigfile' finden. Um Speicherplatz zu sparen, möchten wir an einer mmap.mmapObjektdarstellung der Datei arbeiten:

In [1]: import _find_nth, find_nth, mmap

In [2]: f = open('bigfile', 'r')

In [3]: mm = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)

Es gibt bereits das erste Problem mit findnth(), da mmap.mmapObjekte nicht unterstützen split(). Wir müssen also tatsächlich die gesamte Datei in den Speicher kopieren:

In [4]: %time s = mm[:]
CPU times: user 813 ms, sys: 3.25 s, total: 4.06 s
Wall time: 17.7 s

Autsch! Zum Glück spasst immer noch in die 4 GB Speicher meines Macbook Air. Lassen Sie uns also einen Benchmark erstellen findnth():

In [5]: %timeit find_nth.findnth(s, '\n', 1000000)
1 loops, best of 3: 29.9 s per loop

Offensichtlich eine schreckliche Leistung. Mal sehen, wie der darauf basierende Ansatz str.find()funktioniert:

In [6]: %timeit find_nth.find_nth(s, '\n', 1000000)
1 loops, best of 3: 774 ms per loop

Viel besser! findnth()Das Problem ist natürlich, dass es gezwungen ist, die Zeichenfolge während zu kopieren. Dies split()ist bereits das zweite Mal, dass wir die 1,3 GB Daten danach kopieren s = mm[:]. Hier kommt der zweite Vorteil von find_nth(): Wir können es mmdirekt verwenden, so dass keine Kopien der Datei erforderlich sind:

In [7]: %timeit find_nth.find_nth(mm, '\n', 1000000)
1 loops, best of 3: 1.21 s per loop

Es scheint eine kleine Leistungseinbuße Betriebs auf sein mmgegenüber s, aber dies zeigt , dass find_nth()uns eine Antwort in 1,2 s im Vergleich zu bekommen findnth‚s insgesamt 47 s.

Ich fand keine Fälle, in denen der str.find()basierte Ansatz signifikant schlechter war als derstr.split() basierte Ansatz, daher würde ich an dieser Stelle argumentieren, dass die Antwort von @ tgamblin oder @ Mark Byers anstelle der von @ bobince akzeptiert werden sollte.

In meinen Tests war die find_nth()obige Version die schnellste reine Python-Lösung, die ich finden konnte (sehr ähnlich der Version von @Mark Byers). Mal sehen, wie viel besser wir mit einem C-Erweiterungsmodul arbeiten können. Hier ist _find_nthmodule.c:

#include <Python.h>
#include <string.h>

off_t _find_nth(const char *buf, size_t l, char c, int n) {
    off_t i;
    for (i = 0; i < l; ++i) {
        if (buf[i] == c && n-- == 0) {
            return i;
        }
    }
    return -1;
}

off_t _find_nth2(const char *buf, size_t l, char c, int n) {
    const char *b = buf - 1;
    do {
        b = memchr(b + 1, c, l);
        if (!b) return -1;
    } while (n--);
    return b - buf;
}

/* mmap_object is private in mmapmodule.c - replicate beginning here */
typedef struct {
    PyObject_HEAD
    char *data;
    size_t size;
} mmap_object;

typedef struct {
    const char *s;
    size_t l;
    char c;
    int n;
} params;

int parse_args(PyObject *args, params *P) {
    PyObject *obj;
    const char *x;

    if (!PyArg_ParseTuple(args, "Osi", &obj, &x, &P->n)) {
        return 1;
    }
    PyTypeObject *type = Py_TYPE(obj);

    if (type == &PyString_Type) {
        P->s = PyString_AS_STRING(obj);
        P->l = PyString_GET_SIZE(obj);
    } else if (!strcmp(type->tp_name, "mmap.mmap")) {
        mmap_object *m_obj = (mmap_object*) obj;
        P->s = m_obj->data;
        P->l = m_obj->size;
    } else {
        PyErr_SetString(PyExc_TypeError, "Cannot obtain char * from argument 0");
        return 1;
    }
    P->c = x[0];
    return 0;
}

static PyObject* py_find_nth(PyObject *self, PyObject *args) {
    params P;
    if (!parse_args(args, &P)) {
        return Py_BuildValue("i", _find_nth(P.s, P.l, P.c, P.n));
    } else {
        return NULL;    
    }
}

static PyObject* py_find_nth2(PyObject *self, PyObject *args) {
    params P;
    if (!parse_args(args, &P)) {
        return Py_BuildValue("i", _find_nth2(P.s, P.l, P.c, P.n));
    } else {
        return NULL;    
    }
}

static PyMethodDef methods[] = {
    {"find_nth", py_find_nth, METH_VARARGS, ""},
    {"find_nth2", py_find_nth2, METH_VARARGS, ""},
    {0}
};

PyMODINIT_FUNC init_find_nth(void) {
    Py_InitModule("_find_nth", methods);
}

Hier ist die setup.pyDatei:

from distutils.core import setup, Extension
module = Extension('_find_nth', sources=['_find_nthmodule.c'])
setup(ext_modules=[module])

Installieren Sie wie gewohnt mit python setup.py install. Der C-Code spielt hier eine Rolle, da er sich darauf beschränkt, einzelne Zeichen zu finden. Mal sehen, wie schnell dies geht:

In [8]: %timeit _find_nth.find_nth(mm, '\n', 1000000)
1 loops, best of 3: 218 ms per loop

In [9]: %timeit _find_nth.find_nth(s, '\n', 1000000)
1 loops, best of 3: 216 ms per loop

In [10]: %timeit _find_nth.find_nth2(mm, '\n', 1000000)
1 loops, best of 3: 307 ms per loop

In [11]: %timeit _find_nth.find_nth2(s, '\n', 1000000)
1 loops, best of 3: 304 ms per loop

Klar noch ein bisschen schneller. Interessanterweise gibt es auf C-Ebene keinen Unterschied zwischen In-Memory- und Mmapped-Fällen. Es ist auch interessant zu sehen, dass das _find_nth2(), was auf string.hder memchr()Bibliotheksfunktion basiert , gegen die unkomplizierte Implementierung in verliert _find_nth(): Die zusätzlichen "Optimierungen" in memchr()sind anscheinend nach hinten los ...

Zusammenfassend ist die Implementierung in findnth()(basierend auf str.split()) wirklich eine schlechte Idee, da (a) sie aufgrund des erforderlichen Kopierens für größere Zeichenfolgen eine schreckliche Leistung erbringt und (b) überhaupt nicht für mmap.mmapObjekte funktioniert . Die Implementierung in find_nth()(basierend auf str.find()) sollte unter allen Umständen bevorzugt werden (und daher die akzeptierte Antwort auf diese Frage sein).

Es gibt noch viel Raum für Verbesserungen, da die C-Erweiterung fast um den Faktor 4 schneller lief als der reine Python-Code, was darauf hinweist, dass möglicherweise eine dedizierte Python-Bibliotheksfunktion vorliegt.

Stefan
quelle
8

Einfachster Weg?

text = "This is a test from a test ok" 

firstTest = text.find('test')

print text.find('test', firstTest + 1)
Forbzie
quelle
Ich kann mir vorstellen, dass dies im Vergleich zu anderen Lösungen auch ziemlich performant ist.
Rotareti
7

Ich würde wahrscheinlich so etwas mit der Suchfunktion machen, die einen Indexparameter akzeptiert:

def find_nth(s, x, n):
    i = -1
    for _ in range(n):
        i = s.find(x, i + len(x))
        if i == -1:
            break
    return i

print find_nth('bananabanana', 'an', 3)

Es ist nicht besonders pythonisch, aber es ist einfach. Sie können dies stattdessen mit Rekursion tun:

def find_nth(s, x, n, i = 0):
    i = s.find(x, i)
    if n == 1 or i == -1:
        return i 
    else:
        return find_nth(s, x, n - 1, i + len(x))

print find_nth('bananabanana', 'an', 3)

Es ist ein funktionaler Weg, um es zu lösen, aber ich weiß nicht, ob es dadurch pythonischer wird.

Mark Byers
quelle
1
for _ in xrange(n):kann anstelle vonwhile n: ... n-=1
jfs
@JF Sebastian: Ja, ich denke das ist ein bisschen mehr Pythonic. Ich werde aktualisieren.
Mark Byers
Übrigens: xrange wird in Python 3 nicht mehr benötigt: diveintopython3.org/…
Mark Byers
1
return find_nth(s, x, n - 1, i + 1)sollte sein return find_nth(s, x, n - 1, i + len(x)). Keine große Sache, spart aber Rechenzeit.
Dan Loewenherz
@dlo: Eigentlich kann das in einigen Fällen zu unterschiedlichen Ergebnissen führen: find_nth ('aaaa', 'aa', 2). Meins gibt 1, deins gibt 2. Ich denke, deins ist tatsächlich das, was das Poster will. Ich werde meinen Code aktualisieren. Danke für den Kommentar.
Mark Byers
3

Dadurch erhalten Sie eine Reihe von Startindizes für Übereinstimmungen mit yourstring:

import re
indices = [s.start() for s in re.finditer(':', yourstring)]

Dann wäre Ihr n-ter Eintrag:

n = 2
nth_entry = indices[n-1]

Natürlich muss man mit den Indexgrenzen vorsichtig sein. Sie können die Anzahl der Instanzen yourstringwie folgt ermitteln:

num_instances = len(indices)
modle13
quelle
2

Hier ist ein anderer Ansatz mit re.finditer.
Der Unterschied besteht darin, dass dies nur so weit wie nötig in den Heuhaufen schaut

from re import finditer
from itertools import dropwhile
needle='an'
haystack='bananabanana'
n=2
next(dropwhile(lambda x: x[0]<n, enumerate(re.finditer(needle,haystack))))[1].start() 
John La Rooy
quelle
2

Hier ist eine weitere re+ itertoolsVersion, die bei der Suche nach a stroder a funktionieren sollte RegexpObject. Ich werde frei zugeben, dass dies wahrscheinlich überarbeitet ist, aber aus irgendeinem Grund hat es mich unterhalten.

import itertools
import re

def find_nth(haystack, needle, n = 1):
    """
    Find the starting index of the nth occurrence of ``needle`` in \
    ``haystack``.

    If ``needle`` is a ``str``, this will perform an exact substring
    match; if it is a ``RegexpObject``, this will perform a regex
    search.

    If ``needle`` doesn't appear in ``haystack``, return ``-1``. If
    ``needle`` doesn't appear in ``haystack`` ``n`` times,
    return ``-1``.

    Arguments
    ---------
    * ``needle`` the substring (or a ``RegexpObject``) to find
    * ``haystack`` is a ``str``
    * an ``int`` indicating which occurrence to find; defaults to ``1``

    >>> find_nth("foo", "o", 1)
    1
    >>> find_nth("foo", "o", 2)
    2
    >>> find_nth("foo", "o", 3)
    -1
    >>> find_nth("foo", "b")
    -1
    >>> import re
    >>> either_o = re.compile("[oO]")
    >>> find_nth("foo", either_o, 1)
    1
    >>> find_nth("FOO", either_o, 1)
    1
    """
    if (hasattr(needle, 'finditer')):
        matches = needle.finditer(haystack)
    else:
        matches = re.finditer(re.escape(needle), haystack)
    start_here = itertools.dropwhile(lambda x: x[0] < n, enumerate(matches, 1))
    try:
        return next(start_here)[1].start()
    except StopIteration:
        return -1
Hank Gay
quelle
2

Aufbauend auf der Antwort von modle13 , jedoch ohne die Modulabhängigkeitre .

def iter_find(haystack, needle):
    return [i for i in range(0, len(haystack)) if haystack[i:].startswith(needle)]

Ich wünschte, dies wäre eine eingebaute String-Methode.

>>> iter_find("http://stackoverflow.com/questions/1883980/", '/')
[5, 6, 24, 34, 42]
Zv_oDD
quelle
1
>>> s="abcdefabcdefababcdef"
>>> j=0
>>> for n,i in enumerate(s):
...   if s[n:n+2] =="ab":
...     print n,i
...     j=j+1
...     if j==2: print "2nd occurence at index position: ",n
...
0 a
6 a
2nd occurence at index position:  6
12 a
14 a
Ghostdog74
quelle
1

Bereitstellung einer weiteren "kniffligen" Lösung, die splitund verwendetjoin .

In Ihrem Beispiel können wir verwenden

len("substring".join([s for s in ori.split("substring")[:2]]))
Ivor Zhou
quelle
1
# return -1 if nth substr (0-indexed) d.n.e, else return index
def find_nth(s, substr, n):
    i = 0
    while n >= 0:
        n -= 1
        i = s.find(substr, i + 1)
    return i
Jason
quelle
braucht eine Erklärung
Ctznkane525
find_nth('aaa', 'a', 0)kehrt zurück, 1während es zurückkehren sollte 0. Sie brauchen so etwas i = s.find(substr, i) + 1und kehren dann zurück i - 1.
a_guest
1

Lösung ohne Schleifen und Rekursion.

Verwenden Sie das erforderliche Muster in der Kompilierungsmethode und geben Sie das gewünschte Vorkommen in die Variable 'n' ein. Die letzte Anweisung gibt den Startindex des n-ten Vorkommens des Musters in der angegebenen Zeichenfolge aus. Hier wird das Ergebnis des Finditer, dh des Iterators, in eine Liste konvertiert und greift direkt auf den n-ten Index zu.

import re
n=2
sampleString="this is history"
pattern=re.compile("is")
matches=pattern.finditer(sampleString)
print(list(matches)[n].span()[0])
Karthik
quelle
0

Der Ersatz-Liner ist großartig, funktioniert aber nur, weil XX und Bar die gleiche Länge haben

Ein guter und allgemeiner Def wäre:

def findN(s,sub,N,replaceString="XXX"):
    return s.replace(sub,replaceString,N-1).find(sub) - (len(replaceString)-len(sub))*(N-1)
Charles Doutriaux
quelle
0

Dies ist die Antwort, die Sie wirklich wollen:

def Find(String,ToFind,Occurence = 1):
index = 0 
count = 0
while index <= len(String):
    try:
        if String[index:index + len(ToFind)] == ToFind:
            count += 1
        if count == Occurence:
               return index
               break
        index += 1
    except IndexError:
        return False
        break
return False
Yarz-Tech
quelle
0

Hier ist meine Lösung, um das nVorkommen von bin string zu finden a:

from functools import reduce


def findNth(a, b, n):
    return reduce(lambda x, y: -1 if y > x + 1 else a.find(b, x + 1), range(n), -1)

Es ist reines Python und iterativ. Für 0 oder nzu groß wird -1 zurückgegeben. Es ist einzeilig und kann direkt verwendet werden. Hier ist ein Beispiel:

>>> reduce(lambda x, y: -1 if y > x + 1 else 'bibarbobaobaotang'.find('b', x + 1), range(4), -1)
7
黄锐铭
quelle
0

Für den Sonderfall, in dem Sie nach dem n-ten Vorkommen eines Zeichens suchen (dh Teilzeichenfolge der Länge 1), erstellt die folgende Funktion eine Liste aller Vorkommenspositionen des angegebenen Zeichens:

def find_char_nth(string, char, n):
    """Find the n'th occurence of a character within a string."""
    return [i for i, c in enumerate(string) if c == char][n-1]

Wenn es weniger als nVorkommen des angegebenen Zeichens gibt, gibt es IndexError: list index out of range.

Dies wird aus der Antwort von @ Zv_oDD abgeleitet und für den Fall eines einzelnen Zeichens vereinfacht.

Coldfix
quelle
0

Def:

def get_first_N_words(mytext, mylen = 3):
    mylist = list(mytext.split())
    if len(mylist)>=mylen: return ' '.join(mylist[:mylen])

Benutzen:

get_first_N_words('  One Two Three Four ' , 3)

Ausgabe:

'One Two Three'
Chadee Fouad
quelle