Nie można zrozumieć metody wyszukiwania ciągów zgodnie z opisem. Co to jest WSFFFF?

Question

Czytam coś o wyszukiwaniu (zakres) ciąg (ów) w posortowanej tablicy ciągów.

Mówi:

Jeśli chcesz znaleźć wszystkie ciągi zaczynające się na "h", można uruchomić binarny poszukiwania strings "h" i "h \ uFFFF". Daje to wszystkie indeksy pasma dla wszystkich klawiszy zaczynających się na "h". Zauważ, że wyszukiwanie binarne może zwrócić indeks, w którym łańcuch byłby nawet jeśli , nie jest on faktycznie w tablicy.

Nic nie rozumiem z tego paragrafu.

Co to jest h\uFFFF, w jaki sposób pomaga/jest używane w wyszukiwaniu binarnym i czy ostatni cel oznacza również, że nawet to wyszukiwanie jest błędne?

Każda pomoc w zrozumieniu tego, co tu jest powiedziane, proszę?

Answer 1

\uFFFF to największa możliwa postać w Javie. Ponieważ ciągi są posortowane, wyszukiwanie h znajdzie początek zakresu, podczas gdy h\uFFFF znajdzie koniec (przyjmując tutaj ciągi Unicode), ponieważ żadna druga postać nie może być większa niż \uFFFF. Nawet jeśli nie może dokładnie odpowiadać ciągowi znaków, wyszukiwanie zwróci indeks miejsca docelowego , który byłby, nawet jeśli tak naprawdę tam nie jest.

zmiana: \uFFFF jest największa sortable Unicode znaków w 16 bitowym bloku, jeśli pracujesz z 32-bitowych bloków używać U+10FFFF (cokolwiek to jest w Javie). Osobiście nigdy nie pracowałem 32-bitowymi blokami Unicode w Javie. Zobacz rozdział 16.7 z the 5.2.0 spec.

U + FFFF i U + 10FFFF. Te dwa nieznakowane punkty kodowe mają atrybut związany z największymi jednostkami kodu dla poszczególnych form kodowania Unicode. W UTF-16, U + FFFF jest powiązany z największą 16-bitową wartością jednostki kodu, FFFF. U + 10FFFF to powiązane z największą legalną 32-bitową wartością kodu UTF-32, 10FFFF. Ten atrybut powoduje, że te dwa niekażyste punkty kodu są przydatne do wewnętrznych celów jako wskaźniki. Na przykład, mogą one być służy do wskazania końca listy, do reprezentowania wartości w indeksie gwarantowanej być wyższa niż jakiejkolwiek uzasadnionej wartości znaków, i tak dalej

Answer 2

\ uFFFF jest " znak ", który jest ostatni w 16-bitowym" alfabecie ", tj. po każdej poprawnej literze, znaku lub specjalnym symbolu.

Podczas wyszukiwania binarnego ciągu w posortowanej tablicy znajduje się miejsce, w którym można wstawić ten ciąg. Kiedy masz wiele identycznych ciągów, otrzymujesz lokalizację przed pierwszą. Kiedy dodajesz "ostatnią literę alfabetu" za łańcuchem, punkt wstawienia będzie po ostatnim z identycznych ciągów, dając ci zakres identycznych ciągów w posortowanej tablicy.

Wyobraź sobie: przypuśćmy, że nie możesz używać w swoich słowach litery Z. Teraz masz posortowaną tablicę ciągów:

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

Jeśli szukasz abc, wyszukiwania binarnego informuje o pierwsze miejsce, gdzie można je wstawić, która jest 2. Jeśli szukać abcZ, thoug, wyszukiwania binarnego będzie return 4, ponieważ abcZ jest alfabetycznie zaraz po abc. Dzięki temu wiesz, że zakres od 2 do 4 włącznie jest zajęty przez ciąg . Jeśli oba wyszukiwania zwrócą tę samą liczbę, wiesz, że ciąg nie jest obecny w tablicy.

W cytowanym akapicie \uFFFF odgrywa rolę "zabronionej litery Z" z mojego przykładu.

Answer 3

Sekwencja \uFFFF w języku Java oznacza znak z punktem kodowania U + FFFF w standardzie Unicode. Jednakże kodowy nie koduje postać wcale:

U + FFFF stosuje się do oznaczenia wartości numerycznej, która nie gwarantuje się postać, do zastosowań, takich jak wartości końcowej na końcu indeksu .

Zobacz te nazwy: Unicode Technical Report #16, this Unicode character chart i this character definition.

Answer 4

Jak inne odpowiedzi podano, szukając h znajdzie początek zakresie ciągi zaczynające się h, natomiast h\uFFFF znajdzie koniec (Exclusive) zakresu ciągów zaczynając h w zestawie danych.

Ostatnie zdanie oznacza, że ​​wyszukanie h\uFFFF pokaże Ci gdzie wstawiłeś taki ciąg, jeśli nie ma go w twoich danych, dlatego daje ci wyłączny koniec twojego zasięgu.