C++ - Vyhledávání v textu - Brute Force algoritmus -Linux Software

C++ - Vyhledávání v textu - Brute Force algoritmus

Tento článek je zaměřen na vyhledávání v textu. Nejprve bude zmínka o vyhledávání v textu obecně, poté si řekneme jedno z kritérií, podle kterého se vyhledávací algoritmy dají dělit a představíme si jednoduchý algoritmus Brute Force, na jehož základě je pak postaven složitější Morris-Prattův algoritmus.

8.12.2010 00:00 | Petr Sklenička | Články autora | přečteno 16013×

Vyhledávání v textu obecně

Vyhledávání v textu je činnost, při které hledáme nějaký řetězec (vzorek) v zadaném textu. Problém hledání vzorku v textu patří v oblasti počítačů k poměrně časté činnosti, neboť například textový editor, který by neuměl vyhledat danou část textu, by rozhodně nepatřil k těm kvalitnějším. Dále se s vyhledáváním v textu můžete setkat při analyzování obrazu nebo zvuku.

Algoritmů, který tento problém řeší, existuje celá řada. Všechny tyto algoritmy lze rozdělit do několika skupin. Kritérií, podle kterých můžeme utvořit dané skupiny, je také dost. Jedním takovým nejčastějším kritériem je, zda algoritmus vyžaduje nějaké předzpracování textu nebo vzorku. Celkem tedy vznikají čtyři skupiny algoritmů, které:

nevyžadují předzpracování textu ani vzorku

vyžadují předzpracování vzorku

vyžadují předzpracování textu

vyžadují předzpracování jak textu, tak vzorku

Popis algoritmu Brute Force

Jak jsem již výše psal, jedná se o velice triviální algoritmus. Není tedy težké jej pochopit a implementovat, což je sice výhoda, oproti tomu však algoritmus není příliš efektivní. Samozřejmě pokud budeme hledat v krátkém textu, rozdíl oproti lepším algoritmům bude nepatrný. Časová náročnost se ukáže až při hledání ve velmi dlouhém řetězci.

Název Brute Force lze do češtiny přeložit jako "hrubá síla", což tak trochu vystihuje celou podstatu algoritmu. Celé to funguje tak, že procházíme řetězec zleva doprava, znak po znaku. Než si algoritmus vysvětlíme podrobně, zavedeme si čtyři pojmy, které budeme používat.

x - takto budeme označovat hledaný text, neboli vzorek

t - text, ve kterém budeme hledat výskyt vzorku

delka_x - počet znaků, které obsahuje vzorek

delka_t - počet znaků, které obsahuje text, ve kterém hledáme

V tuto chvíli jsme tedy na prvním znaku, na písmenu "D". První písmeno vzorku je "C". Jelikož se sobě "D" a "C" nerovnají, můžeme se posunout na další znak v textu, což je písmeno "S". Ani písmeno "S" však není shodné s prvním písmenem vzorku, pokračujeme tedy dále. Třetím písmemem textu je "C", které se již shoduje s prvním písmenem našeho vzorku. To však ještě neznamená, že jsme vzorek našli. Náš vzorek obsahuje celkem tři písmena, jedno jsme již našli (na třetí pozici v textu), teď je nutné ověřit, jestli i druhé písmeno vzorku je shodné se čtvrtým písmenem vzorku. Druhý znak ve vzorku je "B" a čtvrtý znak v textu je také "B". Víme tedy, že jsme našli řetězec "CB". Náš vzorek je ale "CBH", proto ještě musíme ověřit, jestli jako další znak v textu je písmeno "H". Pokud ano, vzorek bude nalezen na třetí pozici (udává se místo, kde se v textu nachází první znak vzorku). Pátým znakem v textu je skutečně písmeno "H", vzorek jsme tedy úspěšně našli. Takovýmto způsobem pracuje algoritmus Brute Force. Nyní se podívejme, jak jednoduchá je jeho implementace v jazyce C++.

Nějak takto by mohl vypadat kód. Můžete si všimnout, že algoritmus je napsán tak, že najde všechny výskyty vzorku v daném textu, neskončí tedy po nalezení prvního vzorku. Dále si všimněte vnějšího cyklu. Iterační proměnná i se pohybuje v rozmezí [0, delka_t - delka_x]. Na první pohled by se mohlo zdát, že chceme-li projít celý text, je nutné se posunout i na několik posledních míst v textu. Je nutné si ale uvědomit, že pokud máme například vzorek o délce 4 a text o délce 20, poslední pozicí v textu, kde se vzorek může nacházet, je pozice 17. Dále už ne, neboť víme, že vzorek by se tam nevešel.

Myslím si, že algoritmus je poměrně jednoduchý, proto doufám, že jste jej pochopili. Daň za jednoduchost algoritmu je však jeho velká časová náročnost, proto se pro nějaké větší aplikace příliš nehodí.

Související články

Předchozí Celou kategorii (seriál) Další

C/C++ (1) - Úvod
C/C++ (2) - První program
C/C++ (3) - Proměnné a konstanty
C/C++ (4) - Funkce printf
C/C++ (5) - Funkce printf podruhé
C/C++ (6) - Operátory
C/C++ (7) - Podmínka
C/C++ (8) - Cykly
C/C++ (9) - Pole
C/C++ (10) - Standardní vstup a výstup
C/C++ (11) - Čtení a konverze čísel
C/C++ (12) - Preprocesor
C/C++ (13) - Preprocesor podruhé
C/C++ (14) - Funkce
C/C++ (15) - Proměnné
C/C++ (16) - Hlavičkové soubory
C/C++ (17) - Makefile
C/C++ (18) - Makefile podruhé
C/C++ (19) - Příkaz switch a bitové operátory
C/C++ (20) - Alokace paměti
C/C++ (21) - Práce s řetězci
C/C++ (22) - Struktury
C/C++ (23) - Seznam
C/C++ (24) - Soubory
C/C++ (25) - Funkce s proměnným počtem parametrů
C/C++ (26) - Standardní knihovna
C/C++ (27) - Standardní knihovna podruhé
C/C++ (28) - Standardní knihovna potřetí
C/C++ (29) - Standardní knihovna počtvrté
C/C++ (30) - Výčtový typ a nestandardní knihovny
C/C++ (31) - Jazyk C++, historie, charakteristika, vztah k C
C/C++ (32) - Omezení C++ oproti C
C/C++ (33) - Rozdíly mezi C a C++
C/C++ (34) - Drobná vylepšení C++
C/C++ (35) - Reference, funkce
C/C++ (36) - Prostory jmen
C/C++ (37) - Prostory jmen podruhé
C/C++ (38) - Prostory jmen potřetí
C/C++ (39) - Objektově orientované programování
C/C++ (40) - Dědičnost a virtuální metody
GCC vs. CLANG
C++ Binární vyhledávací stromy
C++ Datová struktura zásobník
C++ - Hashování
C++ šablony
Grafy a grafové algoritmy I
Grafy a grafové algoritmy II
C++ výjimky
C++ Funktory neboli funkční objekty
Grafy a grafové algoritmy III.
C++ a garbage collector

Předchozí Celou kategorii (seriál) Další

DISKUZE

Příspívat do diskuze mohou pouze registrovaní uživatelé.

ARCHIV