Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
14
2.Przeglądmetodwyszukiwaniainformacji
WsystemiewyszukiwaniaopartymnametodzieGhoshaopisyobiek-
tówmogąbyćpamiętanewielokrotnie(np.jeżeliopisobiektujestdłuższy
niżprzyjętyopisklasy).
Przyjętymodelmatematycznybardzoograniczamożliwościrealizacji,
stądteżistniejągłównierealizacjeeksperymentalnesystemówwyszuki-
waniaopartychnametodzieGhosha.
2.6.MetodaChowa
MetodaChowa[12]poleganapodzialewszystkichobiektówbazyda-
nychnazadanązgóryliczbęrrozłącznychgrup.Każdagrupazawierać
będzieokreślonąliczbęklas.Zakładasię,żekażdyobiektjestopisany
iloczynemdeskryptorów.Przyjmujesięopisklasstałejdługościk,tzn.
opisklasyjestiloczynemkdeskryptorów.Jeżeliwszystkichdeskryptorów
wsystemiejestn,toliczbaklaswynosićbędzie(n
k).Przypołączeniuklas
wrgrupwkażdejgrupieznajdowaćsiębędziec=[
(
n
k)
r]klas,gdziezapis
[x]oznaczacechęgórnązx.
Wszystkiedeskryptorysystemunumerujemyod1don.Kolejnekla-
syodpowiadająlinioworosnącejnumeracjideskryptorówwopisieklas.
Wpierwszejgrupieznajdziesięcpierwszychklas,wdrugiejkolejnecklas
itd.
Dlawyszukiwaniawbaziedanychwystarczypamiętaćnumerygrup,
numeryklaswgrupachizbioryobiektówodpowiadającekażdejklasie.
Dosystemuzadajemypytaniewpostaciiloczynukdeskryptorów.
Numerklasybędącejodpowiedziąnatakzadanepytanieznajdujemy
zwzoru[12,17]:
N=(
n
k)−
k11
Σ
j=1
(
k−j+1
n−ij
−1)(
n−ij−1
k−1
)−
Σ
j=1
k
(n−ij)+1
gdzie:j-numerdeskryptorawpytaniuij-numerdeskryptorawsyste-
mie.AdresgrupyGi,wktórejznajdujesięN-taklasa,obliczamyjako
i=[N
c].
Jeżelicniejestliczbącałkowitą,toprzyjmujesię,żepierwszergrup
zawieraćbędzie[c]−1klas,aostatniagruparesztę.Wtedyprzywy-
szukiwaniuodpowiedzinumergrupyGiokreślająnastępującewarunki:
dlaN<(r−1)([c]−1)nrgrupyi=[N
fc11]]
dlaN>(r−1)([c]−1)nrgrupyi=r.
WmetodzieChowa,mającutworzoneklasyigrupy,uzyskujemybar-
dzoszybkoodpowiedźnapytanierównedługościopisuklasy.Dlapytań
krótkich(omniejszejliczbiedeskryptorów)odpowiedźznajdujesięjako
