Impossibile per me comprendere un metodo di ricerca stringa come descritto. Cos'è uFFFF?

Question

Sto leggendo qualcosa sulla ricerca di una (gamma di) stringa (s) in una matrice ordinata di stringhe.

Dice:

Se si desidera trovare tutte le stringhe che iniziano con "h", è possibile eseguire una ricerca binaria per le stringhe "h" e "h \ uFFFF". Questo fornisce tutti gli indici della banda per tutti i tasti che iniziano con "h". Si noti che una ricerca binaria può restituire l'indice in cui la stringa sarebbe anche se non è effettivamente nella matrice.

Non capisco nulla da questo paragrafo.

Che cos'è h\uFFFF in che modo aiuta/viene utilizzato nella ricerca binaria e l'ultimo sentenzioso significa anche che anche questa ricerca è difettosa?

Qualsiasi aiuto per capire cosa viene detto qui per favore?

Answer 1

\uFFFF è il più grande carattere possibile in Java. Poiché le stringhe sono ordinate, la ricerca di h troverà l'inizio dell'intervallo mentre h\uFFFF troverà la fine (assumendo qui stringhe unicode) poiché nessun secondo carattere può essere maggiore di \uFFFF. Anche se non può corrispondere esattamente alla stringa, la ricerca restituirà l'indice di dove il target sarebbe anche se non è realmente lì.

aggiornamento: \uFFFF è il più grande di caratteri Unicode ordinabile possibile nel blocco a 16 bit, se si sta lavorando con i blocchi a 32 bit utilizzare U+10FFFF (qualunque cosa sia in Java). Personalmente non ho mai lavorato a blocchi unicode a 32 bit in Java. Vedere la sezione 16.7 di the 5.2.0 spec.

U + FFFF e U + 10FFFF. Questi due punti di codice non caratteri hanno l'attributo di essere associati ai valori di unità di codice più grandi per i moduli di codifica Unicode specifici di . In UTF-16, U + FFFF è associato a con il valore di unità di codice a 16 bit più grande, FFFF. U + 10FFFF è associato al più grande valore di unità di codice UTF-32 a 32 bit legale, 10FFFF. Questo attributo rende questi due punti di codice non simpatico utili per scopi interni come sentinelle. Ad esempio, potrebbero essere utilizzato per indicare la fine di un elenco, per rappresentare un valore in un indice garantita superiore a qualsiasi valore di carattere valido, e così via

Answer 2

\ uFFFF è il " carattere "che ordina per ultimo nell'alfabeto a 16 bit, vale a dire dopo ogni lettera, carattere o simbolo speciale valido.

Quando si effettua una ricerca binaria per una stringa in un array ordinato, si trova un punto in cui è possibile inserire quella stringa. Quando hai più stringhe identiche, ottieni una posizione prima della prima. Quando aggiungi "l'ultima lettera dell'alfabeto" dopo la tua stringa, il punto di inserimento sarà dopo l'ultima delle stringhe identiche, quindi ti darà un intervallo di stringhe identiche in una matrice ordinata.

Immagina questo: supponi che non ti sia permesso usare la lettera Z con le tue parole. Ora avete un array ordinato di stringhe:

0 1 2 3 4 5 6 
aab abb abc abc abd bcx bdy 

Se si cerca abc, ricerca binaria si dice il primo luogo dove è possibile inserire esso, che è 2. Se si cerca abcZ, thoug, ricerca binaria avrebbe return 4, perché abcZ arriva in ordine alfabetico subito dopo abc. Questo ti consente di sapere che l'intervallo tra 2, compreso e 4, esclusivo, è occupato dalla stringa abc. Se entrambe le ricerche restituiscono lo stesso numero, si sa che la stringa non è presente nell'array.

Nel paragrafo che hai citato, \uFFFF svolge il ruolo della "lettera Z proibita" dal mio esempio.

Answer 3

La sequenza \uFFFF in Java denota il carattere con codice Unicode U + FFFF. Tuttavia, il codepoint non codifica un carattere affatto:

U + FFFF viene utilizzato per rappresentare un valore numerico che è garantito non essere un personaggio, per usi come il valore finale al termine di un indice .

vedere questi riferimenti: Unicode Technical Report #16, this Unicode character chart e this character definition.

Answer 4

Come altre risposte hanno specificato, alla ricerca di h troverà l'inizio della serie di stringhe che iniziano con h, mentre h\uFFFF troverà alla fine (esclusiva) della gamma di stringhe che iniziano con h nel set di dati.

L'ultima frase significa che la ricerca di h\uFFFF ti mostrerà dove inserire una stringa di questo tipo, se non esiste nei tuoi dati, motivo per cui ti dà la fine esclusiva del tuo intervallo.