Wyszukiwanie binarne ciągów - minimalna szerokość kosza?

Question

Zdarza się, że buduję wyszukiwanie binarne w Pythonie, ale pytanie ma więcej wspólnego z ogólną strukturą wyszukiwania binarnego.

Załóżmy, że mam około tysiąca kwalifikujących się kandydatów, których przeszukuję, korzystając z wyszukiwania binarnego, wykonując klasyczne podejście dzielenia posortowanego zestawu danych i powtarzania tego procesu w celu zawężenia kwalifikującego się zestawu do iteracji. Kandydaci są tylko ciągi nazw, (pierwszy-ostatni formatu, np „Peter Jackson”) początkowo posortować ustawione alfabetycznie, a następnie postępuj zgodnie ze wskazówkami bisekcji użyciu coś takiego:

hi = len(names) 
lo = 0 
while lo < hi: 
    mid = (lo+hi)//2 
    midval = names[mid].lower() 
    if midval < query.lower(): 
    lo = mid+1 
    elif midval > query.lower(): 
    hi=mid 
    else: 
    return midval 
return None 

Ten kod dostosowany stąd: https://stackoverflow.com/a/212413/215608

Oto rzeczy, powyższa procedura zakłada pojedynczy dokładny mecz lub brak wyniku. Co jeśli zapytanie dotyczyło tylko "Piotra", ale jest kilka peterów o różnych nazwiskach? Aby zwrócić wszystkich Petersów, należałoby się upewnić, że podzielone na dwie części "kosze" nigdy nie były tak małe, jak tylko przy uwzględnieniu kwalifikujących się wyników. Proces bisekcji musiałby zakończyć się i przekształcić w coś podobnego do regex/regularnego starego dopasowania, aby zwrócić wszystkich Peters.

Nie jestem tak bardzo pytający, jak to osiągnąć, jako , co to jest wyszukiwanie o nazwie ... co to jest wyszukiwanie binarne z ograniczonymi kryteriami dla "rozmiaru bin" o nazwie? Coś, co warunkowo przecina zbiór danych, a po spełnieniu kryteriów, powraca do innej formy dopasowywania ciągów znaków w celu zapewnienia, że ​​w zapytaniu może być skutecznie kończąca się wieloznacznikowa (tak, aby wyszukiwane było słowo "Peter"). Peter Jacksons "i" Peter Edwards ")

Mam nadzieję, że jasne było, co mam na myśli. Zdaję sobie sprawę, że w typowym scenariuszu DB nazwy mogą być rozdzielone, co ma służyć jedynie jako dowód koncepcji.

Answer 1

ja nie natrafiłem tego typu wyszukiwania dwustopniowego przed, więc nie wiem czy ma dobrze znane imię. Mogę jednak zaproponować sposób, w jaki można go przeprowadzić.

Powiedzmy, że wykonałeś pierwszy etap i nie znalazłeś żadnego dopasowania.

Możesz wykonać drugi etap za pomocą pary wyszukiwań binarnych i specjalnego komparatora. Wyszukiwania binarne będą używać tej samej zasady co bisect_left and bisect_right. Nie będziesz w stanie korzystać z tych funkcji bezpośrednio, ponieważ potrzebujesz specjalnego komparatora, ale możesz użyć ich jako podstawy do wdrożenia.

Teraz do komparatora. Porównując element listy x z kluczem wyszukiwania k, komparator użyje tylko x[:len(k)] i zignoruje resztę x. W ten sposób, szukając "Piotra", wszyscy Peterzy z listy porównywaliby ją do klucza. W związku z tym bisect_left() do bisect_right() daje zakres zawierający wszystkie Peters na liście. Można to zrobić za pomocą porównania O(log n).

Answer 2

W wyszukiwaniu binarnym trafiłeś dokładny mecz LUB obszar, w którym mecz byłby.
Tak więc w twoim przypadku musisz uzyskać górną i dolną granicę (hilo, jak je wywołasz) dla obszaru, który zawierałby Peter i zwrócił wszystkie pośrednie ciągi.

Ale jeśli mają zrobić coś podobnego występów następnych słowach słowem należy spojrzeć na Tries zamiast BSTS