přejít na obsah přejít na navigaci

Linux E X P R E S, GNU grep – jak funguje uvnitř (LinuxDays 2017)

GNU grep – jak funguje uvnitř (LinuxDays 2017)

GNU

Program grep je velmi silný a často používaný nástroj na sekvenční zpracování textu. Ondřej Guth nám na konferenci LinuxDays 2017 umožnil nahlédnout pod jeho kapotu. 


Co je GNU grep

GNU grep je GNU verze tradičního unixového nástroje grep. Název programu vznikl z příkazu g/re/p (globally search a regular expression and print) v editoru ed. Uvedený popis příkazu přesně říká, co grep dělá – prohledává soubor podle regulárního výrazu a vypisuje nálezy.

Možná tomu nebudete věřit, ale grep existuje už od listopadu 1974, tedy necelých 43 let!

GNU grep je součástí projektu GNU. Kromě schopností původního programu grep obsahuje i funkce, které se objevily v různých novějších variantách programu (např. egrep, pcregrep nebo fgrep). Ty se zapínají pomocí parametrů, běžně je lze ale používat i přes jejich původní názvy – spuštění grepu s potřebnými parametry zajistí skripty.

Asi nejčastějším způsobem použití programu grep je filtrace řádků nějakého výpisu (logu, seznamu souborů v adresáři apod.), kdy si lze vytáhnout jen zajímavé řádky a ostatní zahodit. Na terminálech, které to umožňují (tedy například všech moderních terminálových emulátorech) pak může grep výskyty v řádcích ještě obarvit.

Pohled pod kapotu

Práce s grepem je poměrně jednoduchá. Je potřeba umět aspoň základy regulárních výrazů, v případě hledání statických řetězců dokonce ani to. Podrobnosti o použití jsou uvedeny v manuálu. Co se tam ale člověk nedozví, jsou informace o „vnitřnostech“ programu. A také to, proč je tak rychlý. Právě této oblasti věnoval na konferenci LinuxDays 2017 svoji přednášku Ondřej Guth.

A začal v podstatě právě tou rychlostí: „Vzal jsem si soubor o velikosti asi 2 GB, seskládaný ze syslogu apod. A pustil jsem na něj grep kernel – na RAMdisku a s vypnutým swapem, samozřejmě – a to slovo kernel to tam hledalo asi tak dvě setiny sekundy. (…) Pro srovnání, když jsem na totéž pustil awk, trvalo mu to přes sedm sekund.“

Ondřej Guth ukazuje na příkladu, jak funguje zpracování textu (zdroj: video z přednášky) Ondřej Guth ukazuje na příkladu, jak funguje zpracování textu (zdroj: video z přednášky)

A jak grep pracuje? Nejdřív provede tokenizaci výrazu (rozdělení na jednotlivé součásti, tokeny) a přeloží ho do podoby strukturního stromu. „Toto je věc, kterou umí standardní céčková knihovna (GNU C Library čili glibc; pozn. aut.) a dělá to i pro ostatní programy, které pracují s regulárními výrazy.“ Potom prochází vstupní data prohledávací funkcí; v případě nálezu vyhledá hranice řádku a ten vypíše (a příslušnou část případně obarví).

Prohledávacích funkcí je v grepu několik a použije se konkrétní podle toho, jaké ‚fíčury‘ chcete v tom regulárním výrazu,“ upřesňuje Ondřej Guth. „Jestli je to obyčejné slovo, nebo jestli jsou tam ‚wildcardy‘, nebo jestli je to několik regulárních výrazů a vy chcete ‚or‘ (logický součet; pozn. aut). Grep nefunguje tak, že má univerzální kód pro všechno. Má ten přístup, že použije algoritmus, který je nejlepší pro daný případ.“

Zajímavé je, že ačkoliv grep standardně pracuje po řádcích, ve skutečnosti bere soubor jako souvislý stream a teprve pro konkrétní nálezy řeší začátek a konec řádku.

Hledání souvislých řetězců

Nejčastěji se pomocí grepu hledají právě souvislé řetězce – jako byl ten „kernel“ u testu rychlosti. V grepu se pro ně používá prohledávač kwset matcher, který v sobě obsahuje dva zajímavé algoritmy. Pro jeden vzorek se používá Boyerův-Mooreův algoritmus (BM), pro více vzorků pak algoritmus Ahoův–Corasickové (AC).

Jedním ze základních principů, které se pozitivně projevují na rychlosti grepu, je protisměrné vyhledávání. To je efektivnější než vyhledávání sousměrné (tedy „od začátku“), a to tím více, čím delší je zadaný regulární výraz.

V rámci BM algoritmu se využívá „bad character shift“, tedy posun pro neshodný znak. „Při zpracování výrazu se vypočítá tabulka – v grepu je to pole. Pro každý znak se zjistí jeho posuv.“ Tento posuv se pak používá při neshodě znaků. Složitější je řešení „delta2“, kombinující více strategií, ale výsledkem je opět pole.

Zpracování vstupu programem grep (zdroj: video z přednášky) Zpracování vstupu programem grep (zdroj: video z přednášky)

Ondřej Guth ukázal fungování na konkrétních hledaných vzorcích a konkrétních prohledávaných textech. Pro značnou obsáhlost nemá smysl je podrobněji rozebírat, vše si můžete prohlédnout a poslechnout ve videozáznamu z přednášky.

Shrnutí

Přednáška ukázala, že i tak zdánlivě jednoduchý nástroj, jakým je GNU grep, může ukrývat zajímavé, poměrně složité, velmi propracované a velmi efektivní algoritmy. Mimochodem zrovna grep je ukázkou unixové filosofie, kdy má každý nástroj dělat jednu věc a tu dělat co nejlépe.



Nahoru

Příspěvky

GNU grep – jak funguje uvnitř (LinuxDays 2017)
Tomas 29. 10. 2017, 09:25:04
Odpovědět  Odkaz 
Super článok ...
GNU grep – jak funguje uvnitř (LinuxDays 2017)
fela 31. 10. 2017, 06:44:58
Odpovědět  Odkaz 
Super článok a super program. Neviem, ako by sme bez grep-u fungovali... Tu sa ukazuje dôležitosť FSF a GNU. Toto je hodné donácie!

Odpovědět

Nejsou podporovány žádné značky, komentáře jsou jen čistě textové. Více o diskuzích a pravidlech najdete v nápovědě.
Diskuzi můžete sledovat pomocí RSS kanálu rss



 
 

Top články z OpenOffice.cz

Lukáš Jelínek

Lukáš Jelínek

Dlouholetý člen autorského týmu LinuxEXPRESu a OpenOffice.cz. Vystudoval FEL ČVUT v oboru Výpočetní technika. Žije v Kutné Hoře, podniká v oblasti IT a zároveň pracuje v týmu projektu Turris. Ve volném čase rád fotografuje, natáčí a stříhá video, občas se věnuje powerkitingu a na prahu čtyřicítky začal hrát tenis.


  • Distribuce: Debian, Kubuntu, Linux Mint
  • Grafické prostředí: KDE

| proč linux | blog



Public Relations

GFI Unlimited Secure Email: bezpečná elektronická pošta pro malé a střední firmy

GFIJsou dvě oblasti, které letos budou pro obchodní kontinuitu malých a středních firem (SMB) kriticky důležité: bezpečnost firemních sítí a elektronické pošty. Podle odhadů společnosti GFI Software více než 50 % loňských útoků směřovalo právě na SMB firmy.

Pokračování ...


GFI

Public Relations

Security Operations Center (SOC) - Vaše kyberbezpečnost za paušál

DatasysNemáte zaměstnance s velmi specializovanými dovednostmi v oblasti sítí a bezpečnosti? Dále digitalizujete a adaptujete nové technologie? Do kyberbezpečnosti investujete, ale nároky narůstají? V době stále sofistikovanějších kybernetických útoků přirozeně vzrůstají nároky na udržování IT bezpečnosti.

Pokračování ...


Redakční blog

Pavel Fric

Pavel Fric, 10. April

Zapojte se do tvorby distribuce Mageia

Podílejte se na vytváření balíčků pro Mageiu, dělejte, co je potřeba, staňte se baličem


Pavel Fric

Pavel Fric, 13. March

Lollypop

Lollypop je hudební přehrávač navržený, jak ukazuje jeho podoba, aby výborně zapadl do pracovního...


Pavel Fric

Pavel Fric, 26. February

QElectroTech

Kreslení elektrotechnických i jiných výkresů


Všechny blogy »

DT Summit MP