Ricerca stringa binaria - larghezza minima del cestino?

Question

Mi sembra che stia costruendo la ricerca binaria in Python, ma la questione ha più a che fare con la struttura di ricerca binaria in generale.

Supponiamo di avere circa un migliaio di candidati idonei che sto cercando utilizzando la ricerca binaria, facendo l'approccio classico di bisecare il set di dati ordinato e ripetere questo processo al fine di restringere il set idoneo per iterare sopra. I candidati sono solo stringhe di nomi, (prima ultimo formato, ad esempio, "Peter Jackson") inizialmente a ordinare il set in ordine alfabetico e quindi procedere con bisezione usando qualcosa di simile:

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 

Questo codice adattato da qui: https://stackoverflow.com/a/212413/215608

Ecco la cosa, la procedura precedente presuppone una singola corrispondenza esatta o nessun risultato. Che cosa succede se la query è stata solo per un "Peter", ma ci sono diversi peters con cognomi diversi? Al fine di restituire tutti i Peters, si dovrebbe garantire che i "bidoni" bisecati non siano mai stati così piccoli da escludere i risultati ammissibili. Il processo di bisection dovrebbe cessare e cedere a qualcosa come una regex/normale vecchia stringa per far tornare tutti i Peters.

io non sono così tanto che chiede come fare questo come ciò che questo tipo di ricerca è chiamato ... che cosa è una ricerca binaria con un criterio delimitati per "dimensioni bin" chiamato? Qualcosa che condiziona in modo condizionale il set di dati, e una volta che i criteri sono soddisfatti, ricade su qualche altra forma di abbinamento di stringhe per garantire che possa effettivamente essere un carattere jolly finale sulla query (quindi una ricerca per un "Peter" otterrà " Peter Jacksons "e" Peter Edwards ")

Spero di essere stato chiaro cosa intendo. Mi rendo conto che nel tipico scenario DB i nomi potrebbero essere separati, questo è solo inteso come una prova di concetto.

Answer 1

io non ho incontrato questo tipo di ricerca a due stadi prima, quindi non so se ha un nome noto Posso, tuttavia, proporre un metodo per come può essere realizzato.

Lasciami dire che hai eseguito la prima tappa e non hai trovato alcuna corrispondenza.

È possibile eseguire la seconda fase con una coppia di ricerche binarie e un comparatore speciale. Le ricerche binarie utilizzano lo stesso principio di bisect_left and bisect_right. Non sarai in grado di utilizzare direttamente queste funzioni poiché avrai bisogno di un comparatore speciale, ma puoi utilizzarle come base per la tua implementazione.

Ora al comparatore. Quando si confronta l'elemento di lista x con la chiave di ricerca k, il comparatore utilizza solo x[:len(k)] e ignora il resto di x. Pertanto, quando si cerca "Peter", tutti i Peters nell'elenco sarebbero paragonabili alla chiave. Di conseguenza, bisect_left() a bisect_right() fornirebbe l'intervallo contenente tutti i Peters nell'elenco.

Tutto ciò può essere eseguito utilizzando i confronti O(log n).

Answer 2

Nella ricerca binaria, si ottiene una corrispondenza esatta O un'area in cui si trova la corrispondenza.
Quindi nel tuo caso è necessario ottenere i limiti superiore e inferiore (hilo come li chiami) per l'area che includerebbe lo Peter e restituire tutte le stringhe intermedie.

Ma se si mira a fare qualcosa di simile mostrare prossime parole di una parola che si dovrebbe guardare in Tentativi invece di BST