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