Vyhledávání II. - Nesekvenční vyhledávání
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Vyhledávání II. - Nesekvenční vyhledáváníVyhledávání II. - Nesekvenční vyhledávání

 

Vyhledávání II. - Nesekvenční vyhledávání

Google       Google       18. 2. 2006       13 790×

Binární vyhledávání
Uniformní binární vyhledávání
Fibonacciho vyhledávání
Jiné metody vyhledávání v seřazeném seznamu .

Reklama
Reklama

Implementujeme-li vyhledávací tabulku polem seřazeným podle velikosti klíčů položek, nabízejí se pro vyhledávání účinnější algoritmy, než je sekvenční vyhledávání. Tyto metody se poněkud podobají numerickým metodám pro hledání kořene funkce jedné proměnné, známe-li interval, v němž je právě jeden kořen. Zvlášť nápadná je podoba s metodou „půlení intervalu“. Na témže principu jsou založeny algoritmy třídy binárního vyhledávání a tzv. Fibonacciho vyhledávání, které budou blíže popsány v tomto odstavci.

1.2.1. Binární vyhledávání

Nechť pro pole implementující vyhledávací tabulku platí:

POLE[1].KLIC < POLE[2].KLIC < .... < POLE[n].KLIC

a dále nechť pro vyhledávaný klíč K platí:

K >= POLE[1].KLIC    a    K <= POLE[n].KLIC

Pak princip binárního vyhledávání lze slovně popsat takto: Vyhledávaný klíč se porovná s klíčem položky, která je umístěna v polovině prohledávaného pole. Dojde-li ke shodě, končí vyhledávání úspěšně. Je-li vyhledávany klíč menší, postupuje se porovnáváním prostředního prvku v levé polovině původního pole, je-li větší v pravé polovině původního pole. Vyhledávání končí neúspěchem v případě, že prohledávaná část pole je prázdná (tzn. že její levý index je větší než pravý).

Zápis algoritmu má tvar:

	l := 1;	{ var l:1..MAX;	ukazatel levé hranice prohledávaného pole }
	r := n;	{ var r:1..MAX;	ukazatel pravé hranice prohledávaného pole }
	repeat
		i := (l+r) div 2;
		if K < POLE[i].KLIC
			then r := i–1;	{ hledaný klíč může být v levé polovině }
			else l := i+1;	{ hledaný klíč může být v pravé polovině }
	until (K = POLE[i].KLIC) or (r

Dijkstrova varianta binárního vyhldávání vychází z předpokladu, že pole může obsahovat více položek, jejichž klíče se navzájem rovnají. V případě úspěšného vyhledání se nalezne nejlevější položka ze skupiny položek se shodnými klíči, ATD tabulka sice takový předpoklad vylučuje, algoritmus však může být užitečný pro řadu aplikací.

Nechť platí:

POLE[1].KLIC <= POLE[2].KLIC <= .... <= POLE[n-1].KLIC < POLE[n].KLIC

a dále nechť pro vyhledávaný klíč K platí:

POLE[1].KLIC <= K

a

K < POLE[n].KLIC

Pak algoritmus Dijkstrovy varianty buinárního vyhledávání má tvar:

<*kod> l := 1; r := n; while r <> (l+1) do begin i := (l+r) div 2; if POLE[i].KLIC < K then l := i else r := i end; SEARCH := K = POLE[i].KLIC; { if SEARCH then prvek POLE[i] je nejlevějším prvkem skupiny položek s klíčem rovným K }

Zatímco u prvního algoritmu může úspěšné vyhledávání trvat kratší dobu než neúspěšné, Dijkstrova varianta má úspěšné i neúspěšné vyhledání stejně dlouhé.

1.2.2. Uniformní binární vyhledávání

Místo tří proměnných i, l a r lze použít pouze dvou: aktuální index i a odchylka m od aktuálního indexu i. Po každém neúspěšném porovnání ustavíme:

i := i+m		a	m := m div 2;

Při návrhu tohoto algoritmu je nutné promyslet všechny detaily, aby nedošlo k nepředvídané chybě.

Nechť je dáno pole, pro jehož položky platí:

POLE[1].KLIC < POLE[2].KLIC < .... < POLE[n].KLIC

Je-li MAX sudé, pak algoritmus potřebuje prázdnou (slepou) položku s indexem 0, jejíž klíč se nastaví na hodnotu menší, než jsou všechny vyhledávané klíče. Algoritmus uniformního binárního vyhledávání má tvar:

	POLE[0].KLIC := MINKLIC;	{ jen pro sudé MAX }
	i := (n+1] div 2;
	m := n div 2;
	while (m <> 0) and (K <> POLE[i].KLIC) do
		begin
			if K < POLE[i].KLIC
				then i := i – (m+1) div 2
				else i := i + (m+1) div 2;
			m := m div 2;
	end;
	SEARCH := K = POLE[i].KLIC;
	{ if SEARCH then prvek POLE[i] je hledaný prvek }

Hlavní přednost této metody se může využít, je-li tabulka statická. V tom případě lze pro daný počet položek vytvořit před vyhledáváním pomocné pole odchylek DELTA a jejím použitím v cyklu vyhledávání odstranit operaci dělení, čímž se algoritmus značně zrychlí. Pro DELTA platí:

DELTA[j] = round (n/2j)

Algoritmus uniformního vyhledávání využívající této výhody má tvar:


	MOCNINA := 2;		{ var MOCNINA:POSINT }
	for j := 1 to m+2 do	{ kde platí 2m-1 < n <= 2m }
		begin
			DELTA[j] := round(n/MOCNINA);
			{ var DELTA:array[1..(m+2)] of POSINT }
			MOCNINA := MOCNINA * 2;
		end;

	i := DELTA[1];
	j := 2;	
	while (K <> POLE[i[.KLIC) and (DELTA[j] <> 0) do
		begin
			if K < POLE[i[.KLIC 	then i := i + DELTA[j]
						else i := i - DELTA[j];
			j := succ(j);
		end;
	SEARCH := K = POLE[i].KLIC;
	{ if SEARCH then prvek POLE[i] je hledaným prvkem }

1.2.3. Fibonacciho vyhledávání

Existuje vzájemný vztah mezi binárním vyhledáváním v seřazeném poli a binárním stromem. Algoritmus Fibonacciho vyhledávání pracuje podobně jako binární vyhledávání. Daný interval v poli však nedělí na dvě poloviny, ale dělící bod odvozuje z Fibonacciho posloupnosti a k jeho získání stačí aditivní operace, což zvýší rychlost vyhledávání tam, kde aditivní operace jsou výrazně rychlejší než celočíselné dělení číslem 2.

V řadě metod hraje Fibonacciho posloupnost podobnou roli, jako mocninná řada dvou v obdobných metodách. K pochopení Fibonacciho vyhledávání se jen ztěží obejdeme bez Fibonacciho rozhodovacího stromu.

Fibonacciho strom řádu l má Fl+1-1 uzlů neterminálních a Fl+1 listů.
	Je-li l = 0 nebo l = 1 je strom tvořen jen listem 0.
	Je-li l>=2, pak kořenem stromu je uzel Fl
		přitom 	levý podstrom je Fibonacciho strom řádu l-1
		a 	pravý podstrom je Fibonacciho strom řádu l-2
			jehož uzly mají hodnotu zvýšenou o Fl

Pro jednoduchost budeme předpokládat, že n+1 je Fibonacciho číslo Fl+1. Pro jiné n je nutno provést potřebné počáteční úpravy. V následujícím algoritmu budeme používa funkce F(l) pro určení Fibonacciho čísla řádu.

Proměnné p a q budou mít vždy hodnoty dvou po sobě jdoucích Fibonacciho čísel.

Algoritmus Fibonacciho vyhledávání má tvar:


	i := F(l);
	p := F(l-1);
	q := F(l-2);
	TERM := false;
	while (K <> POLE[i].KLIC) and (not TERM) do
		if K < POLE[i].KLIC
		then { hledá se v levém podstromu }
			if q = 0
				then TERM := true	{ vyhledávání končí v levém listu }
				else { ustaví se nové hodnoty i,p a q pro levý podstrom }
				begin	i ;= i – q;
					p1 := q;		{ pomocná proměnná p1}
					q1 := p – q;	{ pomocná proměnná q1}
					p := p1;
					q := q1;
				end
			else { hledá se v pravém podstromu }
				if p = 1 	then TERM := true	{ vyhledávání končí v pravém listu }
					else 	{ ustaví se nové hodnoty i,p a q pro pravý podstrom }
						begin	i := i + q;
							p := p – q;
							q := q – p
						end;	{ konec if K < POLE[i].KLIC a konec while }
	SEARCH := not TERM;
	{ if SEARCH then prvek POLE[i] je hledaným prvkem }

1.2.4. Jiné metody vyhledávání v seřazeném seznamu

Má-li se vyhledávat prvek v seznamu seřazeném podle velikosti klíčů jednotlivých položek, nabízejí se principiálně i jiné metody, které známe dobře z praxe při vyhledávání žádaného hesla ve slovníku, či osoby v telefonním seznamu. V tom případě lze vyhledávání usnadnit s využitím těchto principů:

a) Některé slovníky mají na straně opačné než je hřbet výřezy označené jednotlivými písmeny abecedy (tzv. „prstové indexy“), které umožňují jedním hmatem otevřít slovník na stránce, od které jsou uvedena hesla začínající na dané písmeno. Tento princip je podobný indexsekvenčnímu přístupu k seznamu (k vhodnému místu seznamu se dostaneme pomocí „indexu“ a dále postupujeme sekvenčně) a proto mu říkáme indexsekvenční vyhledávání. Tento přístup je vhodný především pro externí vyhledávání.

b) Hledáme-li ve slovníku, který není vybaven prstovými indexy, jistě nevyhledáváme tak, že bychom „půlili“ plný rozsah slovníku abychom zjistili, zda je hledané heslo v levé nebo v pravé polovině, ale dělící bod získáváme intuitivní interpolací. Víme-li, že hledaný klíč K leží mezi klíči K1 a K2 (K1 < K2), pak dělící bod hledáme v místě blízkém hodnotě (K – K1)/ (K2 - K) a mlčky předpokládáme, že rozdělení klíčů v intervalu od K1 do K2 je rovnoměrné. Tato úvaha je základem interpolačního vyhledávání.

Řada experimentů i praktické zkušenosti však ukazují, že interpolační metoda aplikovaná na seřazené pole nesníží počet porovnání tak dostatečně, aby se kompenzoval čas, potřebný navíc pro složitější určení dělícího bodu. Metoda může být poněkud úspěšnější při aplikaci na vyhledávání na vnějších paměťových zařízeních.

Zdroj: Petr Pindur - vyhledávání

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

1 názor  —  1 nový  
Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Lukáš ChurýLukáš je šéfredaktorem Programujte, vyvíjí webové aplikace, fascinuje ho umělá inteligence a je lektorem na FI MUNI, kde učí navrhovat studenty GUI. Poslední dobou se snaží posunout Laser Game o stupeň výše a vyvíjí pro něj nové herní aplikace a elektroniku.
Web     Twitter     Facebook     LinkedIn    

Nové články

Obrázek ke článku NEWTON Media prohledá 200  milionů mediálních zpráv během sekund díky Cisco UCS

NEWTON Media prohledá 200 milionů mediálních zpráv během sekund díky Cisco UCS

Česká společnost NEWTON Media provozuje největší archiv mediálních zpráv ve střední a východní Evropě. Mezi její zákazníky patří například ministerstva, evropské instituce nebo komerční firmy z nejrůznějších oborů. NEWTON Media rozesílá svým zákazníkům každý den monitoring médií podle nastavených klíčových slov a nabízí online službu, kde lze vyhledat mediální výstupy v plném znění od roku 1996.

Reklama
Reklama
Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Reklama autora

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý