2012-01-27 7 views
6

Czytam coś o wyszukiwaniu (zakres) ciąg (ów) w posortowanej tablicy ciągów.Nie można zrozumieć metody wyszukiwania ciągów zgodnie z opisem. Co to jest WSFFFF?

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ę?

+0

'\ uFFFF' jest maksymalną wartością dla znaku Unicode, nie jest używane jako drukowana czcionka –

+0

'\ uFFFF' jest sekwencją specjalną dla punktu kodowego U + FFFF, która jest gwarantowana przez [stanard] (http: //unicode.org/charts/PDF/UFFF0.pdf), aby nie być postacią. Czy jest jakiś specjalny użytek, ponieważ jest on zdefiniowany gdzie indziej w tym, co czytasz? –

+1

@Sam Dehaan: * "\ uFFFF jest maksymalną wartością dla znaku Unicode" * ... Od Unicode 3.1 jest znacznie więcej niż 65 536 punktów kodowych, a pojedynczy Java * char * nie wystarcza do reprezentacji nowych współrzędnych kodowych. Na przykład znak Unicode "MUSICAL SYMBOL G CLEF" ma kod 0xC0101D11E kodowania Unicode (więcej niż 0xFFFF) i potrzebuje dwóch znaków Java * char * do reprezentacji: "\ uD8334 \ uDD1E". Ten SNAFU pochodzi z faktu, że Java (i jego typ pierwotny * char) został zdefiniowany przed wydaniem Unicode 3.1. Podsumowując: nie, \ uFFFF to zdecydowanie ** NOT ** maksymalna wartość dla codepoint kodu Unicode. – TacticalCoder

Odpowiedz

3

\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

+0

Więc ten symbol '\ uFFFF' pomaga przekazać znak w hexie w' ciągu'? – Cratylus

+0

który jest zależny od języka, ale "oznacza" znak Unicaode znany jako "FFFF". SOFT jak ASCII 0xFF ... –

+0

Spójrz na moje ostatnie zdanie, aby podnieść ostatnie zdanie fragmentu. –

9

\ 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.

+0

Myślę, że twój przykład nie jest poprawny. Masz 'abc' {2}, aby być prawym dzieckiem root'a, a także masz' abc' {3}, aby zostawić wnuka 'aab' {root} – Cratylus

+0

W lewym wyszukiwaniu binarnym to '2 * i + 1' i prawe dziecko' 2 * i + 2'. To właśnie mam na myśli. Poprawiłem mój komentarz – Cratylus

+0

@ user384706 Myślę, że źle zrozumiałeś mój przykład: nie ma tam korzenia - w rzeczy samej, nie ma hierarchia dowolnego rodzaju. To po prostu tablica ciągów, posortowana alfabetycznie w porządku rosnącym. – dasblinkenlight

1

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.