Znajdź n-te wystąpienie podciągu w ciągu


118

Wydaje się, że powinno to być dość trywialne, ale jestem nowy w Pythonie i chcę to zrobić jak najbardziej w Pythonie.

Chcę znaleźć indeks odpowiadający n-temu wystąpieniu podciągu w ciągu.

Musi być coś równoważnego temu, co CHCĘ zrobić, czyli

mystring.find("substring", 2nd)

Jak możesz to osiągnąć w Pythonie?


7
Znajdź n-te wystąpienie łańcucha? Zakładam, że oznacza to indeks n-tego wystąpienia?
Mark Byers

2
Tak, indeks n-tego wystąpienia
prestomowa

9
Co powinno się stać, jeśli są nakładające się mecze? Czy find_nth ('aaaa', 'aa', 2) powinno zwrócić 1 czy 2?
Mark Byers

Tak! musi być coś, co znajdzie n-te wystąpienie podciągu w ciągu znaków i podzieli go przy n-tym wystąpieniu podciągu.
Reman

Odpowiedzi:


69

Myślę, że iteracyjne podejście Marka byłoby typowym sposobem.

Oto alternatywa z dzieleniem ciągów, która często może być przydatna do znajdowania procesów powiązanych:

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)

A oto szybki (i nieco brudny, ponieważ musisz wybrać plewy, które nie pasują do igły):

'foo bar bar bar'.replace('bar', 'XXX', 1).find('bar')

7
Pierwsza sugestia będzie bardzo nieefektywna w przypadku dużych ciągów, gdy interesujący Cię mecz jest blisko początku. Zawsze patrzy na cały ciąg. Jest to sprytne, ale nie polecałbym tego komuś, kto jest nowy w Pythonie i po prostu chce się nauczyć, jak to robić.
Mark Byers

3
Dzięki, podoba mi się twoja jedna wkładka. Nie sądzę, że jest to najbardziej czytelna rzecz na świecie, ale nie jest dużo gorsza niż większość innych poniżej
prestom

1
+1 dla jednej linijki, to powinno mi teraz pomóc. Myślałem o zrobieniu odpowiednika .rfind('XXX'), ale to by się rozpadło, gdyby i tak 'XXX'pojawiło się później na wejściu.
Nikhil Chelliah,

Ta funkcja zakłada n = 0, 1, 2, 3, ... Byłoby miło, gdybyś założył, że n = 1, 2, 3, 4, ...
Happy

75

Oto bardziej Pythonic wersja prostego rozwiązania iteracyjnego:

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

Przykład:

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

Jeśli chcesz znaleźć n-te nakładające się wystąpienie needle, możesz zwiększyć o 1zamiast len(needle), na przykład:

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

Przykład:

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

Jest to łatwiejsze do odczytania niż wersja Marka i nie wymaga dodatkowej pamięci wersji dzielącej lub importowania modułu wyrażeń regularnych. W przeciwieństwie do różnych podejść, przestrzega również kilku zasad Zen Pythonare :

  1. Proste jest lepsze niż złożone.
  2. Płaskie jest lepsze niż zagnieżdżone.
  3. Liczy się czytelność.

Czy można to zrobić w ciągu? Na przykład find_nth (df.mystring.str, ('x'), 2), aby znaleźć pozycję drugiej instancji 'x'?
Arthur D. Howland

36

To znajdzie drugie wystąpienie podciągu w ciągu.

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

Edycja: Nie myślałem dużo o wydajności, ale szybka rekurencja może pomóc w znalezieniu n-tego wystąpienia:

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)

Czy można to ogólnie rozszerzyć, aby znaleźć n-ty element?
ifly6

To najlepsza odpowiedź IMHO, zrobiłem mały dodatek dla specjalnego przypadku, w którym n = 0
Jan Wilmans

Nie chciałem edytować posta ze względu na zwięzłość. Zgadzam się jednak z Tobą, że n = 0 należy traktować jako przypadek szczególny.
Sriram Murali

Powinno to być dostosowane do obsługi w przypadku, gdy jest mniej niż nwystąpień podciągu. (W tym przypadku wartość zwracana będzie cyklicznie przechodzić przez wszystkie pozycje występowania).
coldfix

29

Rozumiejąc, że regex nie zawsze jest najlepszym rozwiązaniem, prawdopodobnie użyłbym jednego tutaj:

>>> 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

4
Oczywiście istnieje ryzyko, że szukany ciąg będzie zawierał znaki specjalne, które spowodują, że wyrażenie regularne zrobi coś, czego nie chcesz. Użycie re.escape powinno rozwiązać ten problem.
Mark Byers

1
To sprytne, ale czy to naprawdę Pythonic? Wydaje się, że to przesada za znalezienie n-tego wystąpienia podciągu i nie jest to łatwe do odczytania. Ponadto, jak mówisz, musisz zaimportować wszystko do tego
Todd Gamblin,

Używając nawiasów kwadratowych, mówisz Pythonowi, aby utworzył całą listę. Nawiasy okrągłe będą iterować tylko przez pierwsze elementy, co jest bardziej efektywne:(m.start() for m in re.finditer(r"ab",s))[2]
emu

1
@emu Nie, to, co opublikowałeś, nie zadziała; nie możesz wziąć indeksu generatora.
Mark Amery,

@MarkAmery sorry! Jestem dość zaskoczony, dlaczego opublikowałem ten kod. Mimo to możliwe jest podobne i brzydkie rozwiązanie przy użyciu itertools.islicefunkcji:next(islice(re.finditer(r"ab",s), 2, 2+1)).start()
emu

17

Przedstawiam wyniki testów porównawczych, porównujące najbardziej znaczące podejścia zaprezentowane do tej pory, a mianowicie @ bobince's findnth()(na podstawie str.split()) vs. @ tgamblin's lub @Mark Byers ' find_nth()(na podstawie str.find()). Porównam również z rozszerzeniem C ( _find_nth.so), aby zobaczyć, jak szybko możemy jechać. Oto 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

Oczywiście wydajność ma największe znaczenie, jeśli łańcuch jest duży, więc przypuśćmy, że chcemy znaleźć 1000001. znak nowej linii („\ n”) w pliku o nazwie „bigfile” o wielkości 1,3 GB. Aby zaoszczędzić pamięć, chcielibyśmy popracować nad mmap.mmapreprezentacją obiektową pliku:

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)

Jest już pierwszy problem findnth(), ponieważ mmap.mmapobiekty nie obsługują split(). Więc właściwie musimy skopiować cały plik do pamięci:

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

Auć! Na szczęście snadal mieści się w 4 GB pamięci mojego Macbooka Air, więc zróbmy benchmark findnth():

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

Najwyraźniej okropny występ. Zobaczmy, jak działa podejście oparte na str.find():

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

Dużo lepiej! Najwyraźniej findnth()problem polega na tym, że jest on zmuszony do skopiowania ciągu w trakcie split(), co jest już drugim razem, gdy kopiowaliśmy 1,3 GB danych dookoła s = mm[:]. Tu pojawia się druga zaleta find_nth(): Możemy go używać mmbezpośrednio, tak że nie są wymagane żadne kopie pliku:

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

Wydaje się, że działanie na mmvs. jest niewielki spadek wydajności s, ale to pokazuje, że find_nth()możemy uzyskać odpowiedź w 1,2 sekundy w porównaniu do findnth47 sekund.

Nie znalazłem przypadków, w których str.find()podejście oparte było znacznie gorsze niż str.split()podejście oparte, więc w tym miejscu argumentowałbym, że odpowiedź @ tgamblin lub @Mark Byers powinna zostać zaakceptowana zamiast @ bobince.

W moich testach find_nth()powyższa wersja była najszybszym czystym rozwiązaniem Pythona, jakie mogłem wymyślić (bardzo podobnym do wersji @Mark Byers). Zobaczmy, o ile lepiej możemy zrobić z modułem rozszerzającym C. Oto _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);
}

Oto setup.pyplik:

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

Zainstaluj jak zwykle z python setup.py install. Kod C odgrywa tutaj przewagę, ponieważ ogranicza się do znajdowania pojedynczych znaków, ale zobaczmy, jak szybko to jest:

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

Najwyraźniej jeszcze trochę szybciej. Co ciekawe, na poziomie C nie ma różnicy między obudowami in-memory i mmapped. Warto również zauważyć, że _find_nth2(), który opiera się na string.h„s memchr()funkcja biblioteki, traci się przeciwko zwykłej realizacji w _find_nth(): dodatkowy«optymalizacje»w memchr()widocznie mści ...

Podsumowując, implementacja w findnth()(oparta na str.split()) jest naprawdę złym pomysłem, ponieważ (a) działa strasznie w przypadku większych ciągów z powodu wymaganego kopiowania i (b) w ogóle nie działa na mmap.mmapobiektach. Implementacja w find_nth()(oparta na str.find()) powinna być preferowana we wszystkich okolicznościach (i dlatego powinna być akceptowaną odpowiedzią na to pytanie).

Wciąż jest sporo miejsca na ulepszenia, ponieważ rozszerzenie C działało prawie 4 razy szybciej niż czysty kod Pythona, co wskazuje, że może istnieć argument za dedykowaną funkcją biblioteczną Pythona.


8

Najprostszy sposób?

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

firstTest = text.find('test')

print text.find('test', firstTest + 1)

Mogę sobie wyobrazić, że jest to również całkiem wydajne w porównaniu z innymi rozwiązaniami.
Rotareti

7

Prawdopodobnie zrobiłbym coś takiego, używając funkcji find, która przyjmuje parametr indeksu:

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)

Wydaje mi się, że nie jest to specjalnie Pythonic, ale jest proste. Zamiast tego możesz to zrobić używając rekurencji:

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)

To funkcjonalny sposób na rozwiązanie tego problemu, ale nie wiem, czy to czyni go bardziej Pythonowym.


1
for _ in xrange(n):można użyć zamiastwhile n: ... n-=1
jfs

@JF Sebastian: Tak, myślę, że to trochę bardziej Pythonic. Zaktualizuję.
Mark Byers

BTW: xrange nie jest już potrzebne w Pythonie 3: diveintopython3.org/…
Mark Byers

1
return find_nth(s, x, n - 1, i + 1)powinno być return find_nth(s, x, n - 1, i + len(x)). Nie jest to wielka sprawa, ale oszczędza trochę czasu obliczeń.
Dan Loewenherz

@dlo: Właściwie to może dać różne wyniki w niektórych przypadkach: find_nth ('aaaa', 'aa', 2). Mój daje 1, twój daje 2. Domyślam się, że twój jest tym, czego chce plakat. Zaktualizuję mój kod. Dziękuję za komentarz.
Mark Byers

3

To da ci tablicę indeksów początkowych dla dopasowań do yourstring:

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

Wtedy twój n-ty wpis wyglądałby tak:

n = 2
nth_entry = indices[n-1]

Oczywiście musisz uważać na granice indeksu. Możesz uzyskać liczbę takich wystąpień yourstring:

num_instances = len(indices)

2

Oto inne podejście wykorzystujące re.finditer.
Różnica polega na tym, że zagląda to do stogu siana tylko wtedy, gdy jest to konieczne

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() 

2

Oto kolejna wersja re+, itertoolsktóra powinna działać podczas wyszukiwania a strlub a RegexpObject. Przyznam, że jest to prawdopodobnie przesadzone, ale z jakiegoś powodu bawiło mnie to.

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

2

Opierając się na odpowiedzi modle13 , ale bez rezależności od modułu.

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

Chciałbym, żeby to była wbudowana metoda ciągów.

>>> iter_find("http://stackoverflow.com/questions/1883980/", '/')
[5, 6, 24, 34, 42]

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

1

Dostarczenie innego „podstępnego” rozwiązania, które wykorzystuje spliti join.

W Twoim przykładzie możemy użyć

len("substring".join([s for s in ori.split("substring")[:2]]))

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

potrzebuje wyjaśnienia
Ctznkane525

find_nth('aaa', 'a', 0)zwraca, 1podczas gdy powinien powrócić 0. Potrzebujesz czegoś takiego, i = s.find(substr, i) + 1a potem wróć i - 1.
a_guest

1

Rozwiązanie bez używania pętli i rekurencji.

Użyj wymaganego wzorca w metodzie kompilacji i wprowadź żądane wystąpienie w zmiennej 'n', a ostatnia instrukcja wypisze indeks początkowy n-tego wystąpienia wzorca w podanym ciągu. Tutaj wynik działania finditera, czyli iteratora, jest konwertowany na listę i uzyskuje bezpośredni dostęp do n-tego indeksu.

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

1

W szczególnym przypadku, w którym szukasz n-tego wystąpienia znaku (tj. Podłańcuch o długości 1), następująca funkcja działa poprzez zbudowanie listy wszystkich pozycji wystąpień danego znaku:

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]

Jeśli będzie mniej niż nwystąpień danej postaci, to da IndexError: list index out of range.

To pochodzi od @ Zv_oDD za odpowiedź i uproszczone dla przypadku pojedynczego znaku.


To jest piękne.
Hafiz Hilman Mohammad Sofian

0

Wymiana jednej wkładki jest świetna, ale działa tylko dlatego, że XX i kierownica mają tę samą długość

Dobra i ogólna def to:

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

0

Oto odpowiedź, której naprawdę chcesz:

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

0

Oto moje rozwiązanie do znalezienia nwystąpienia bw łańcuchu 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)

Jest to czysty Python i iteracyjny. W przypadku 0 lub nzbyt dużej wartości zwraca -1. Jest jednoliniowy i można go używać bezpośrednio. Oto przykład:

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

0

Def:

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

Używać:

get_first_N_words('  One Two Three Four ' , 3)

Wynik:

'One Two Three'

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.