Imposible para mí entender un método de búsqueda de cadenas como se describe. ¿Qué es uFFFF?

Question

Estoy leyendo algo sobre la búsqueda de una (variedad de) serie (s) en una matriz ordenada de cadenas.

Dice:

Si usted quiere encontrar todas las cadenas que comienzan con "h", puede ejecutar una búsqueda binaria para la cuerdas "h" y "h \ uFFFF". Esto da todos los índices de la banda para todas las teclas que comienzan con "h". Tenga en cuenta que una búsqueda binaria puede devolver el índice donde estaría la cadena incluso si no está realmente en la matriz.

No entiendo nada de este párrafo.

¿Qué es h\uFFFF cómo ayuda/se usa en la búsqueda binaria y la última frase también significa que incluso esta búsqueda es defectuosa?

¿Alguna ayuda para entender lo que se dice aquí, por favor?

Answer 1

\uFFFF es el carácter más grande posible en Java. Dado que las cadenas están ordenadas, la búsqueda de h encontrará el inicio del rango, mientras que h\uFFFF encontrará el final (suponiendo que las cadenas de unicode estén aquí) ya que ningún segundo carácter puede ser mayor que \uFFFF. Incluso si no puede coincidir exactamente con la cadena, la búsqueda devolverá el índice de donde el objetivo sería, incluso si no está realmente allí.

actualización: \uFFFF es el más grande de caracteres Unicode puede ordenar posible en el bloque de 16 bits, si se está trabajando con bloques de 32 bits utilizar U+10FFFF (sea lo que sea en Java). Personalmente, nunca trabajé en bloques Unicode de 32 bits en Java. Consulte la sección 16.7 de the 5.2.0 spec.

U + FFFF y U + 10FFFF. Estos dos puntos de código no característicos tienen el atributo de estar asociado con los valores de unidad de código más grandes para formas de codificación Unicode particulares. En UTF-16, U + FFFF está asociado con el valor de unidad de código de 16 bits más grande, FFFF. U + 10FFFF es asociado con el valor de unidad de código UTF-32 legal más grande de 32 bits, 10FFFF. Este atributo hace que estos dos puntos de código no característicos sean útiles para propósitos internos como centinelas. Por ejemplo, puede ser que sean utiliza para indicar el final de una lista, para representar un valor en un índice garantiza que sea más alto que cualquier valor de carácter válido, y así sucesivamente

Answer 2

\ uFFFF es el " carácter "que ordena en último lugar en el" alfabeto "de 16 bits, es decir, después de cualquier letra, carácter o símbolo especial válido.

Cuando realiza una búsqueda binaria de una cadena en una matriz ordenada, encuentra un lugar donde esa cadena podría insertarse. Cuando tiene múltiples cadenas idénticas, obtiene una ubicación antes que la primera. Cuando agregue "la última letra del alfabeto" después de su cadena, el punto de inserción será posterior a la última de las cadenas idénticas, lo que le proporcionará un rango de cadenas idénticas en una matriz ordenada.

Imagínese esto: suponga que no está permitido utilizar la letra Z en sus palabras. Ahora usted tiene una matriz ordenada de cadenas:

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

Si busca abc, búsqueda binaria le dice que el primer lugar donde se puede insertar, que es 2. Si busca abcZ, thoug, búsqueda binaria haría return 4, porque abcZ viene alfabéticamente después de abc. Esto le permite saber que el rango entre 2, inclusive y 4, exclusivo, está ocupado por la cadena abc. Si ambas búsquedas devuelven el mismo número, sabrá que la cadena no está presente en la matriz.

En el párrafo que citó, \uFFFF juega el papel de la "letra Z prohibida" de mi ejemplo.

Answer 3

La secuencia \uFFFF en Java denota el carácter con el punto de código Unicode U + FFFF. Sin embargo, el punto de código no codifica un carácter en absoluto:

U + FFFF se utiliza para representar un valor numérico que está garantizado para no ser un carácter, para usos tales como el valor final al final de un índice .

ver estas referencias: Unicode Technical Report #16, this Unicode character chart y this character definition.

Answer 4

Como otras respuestas han especificado, la búsqueda de h se encuentra el inicio de la serie de cadenas que comienzan con h, mientras h\uFFFF se encuentra el extremo (exclusivo) de la gama de cadenas a partir de h en su conjunto de datos.

La última oración significa que la búsqueda de h\uFFFF le mostrará dónde insertaría una cadena de este tipo, si no existe en sus datos, por lo que le otorga el extremo exclusivo de su rango.