Analýza a vizualizace frekvence znaků

Co je analýza četnosti znaků?

Analýza četnosti znaků je proces počítání, kolikrát se každý znak objeví v části textu. Zahrnuje písmena, číslice, mezery, interpunkční znaménka i všechny další symboly v textu. Výsledkem je jednoduchá tabulka nebo graf: jeden znak, jeden počet.

Tento nástroj vezme libovolný vložený nebo napsaný text a automaticky spočítá každý znak. U každého jedinečného znaku uvede jeho počet a vykreslí sloupcový graf, takže nejčastější znaky je vidět na první pohled.

Tato technika je stará. Arabský učenec Al-Kindí ji popsal kolem roku 850 n. l. jako způsob, jak prolomit jednoduché šifry. Dnes se používá také při kompresi dat, kontrole pravopisu a kódování a při základním rozpoznávání jazyka.

Jak vypočítat četnost znaků

Ruční výpočet četnosti znaků se skládá ze tří kroků:

1. Procházet text po jednotlivých znacích včetně mezer a interpunkčních znamének.
2. Průběžně zaznamenávat počet každého odlišného znaku. Nový znak začíná na hodnotě 1; opakovaný znak přidá ke svému dosavadnímu počtu 1.
3. Vypsat každý znak s jeho konečným počtem.

Tento nástroj dělá totéž automaticky pomocí datové struktury zvané hašovací mapa (vyhledávací tabulka, která ukládá hodnotu pod klíčem). U každého znaku v textu kontroluje, zda už je tento znak v mapě uveden. Pokud ano, přidá k uloženému počtu 1. Pokud ne, vytvoří novou položku s počtem 1. Tato metoda se každého znaku dotkne právě jednou, takže čas potřebný ke zpracování roste přímo úměrně délce textu, nikoli rychleji.

Po spočítání nástroj vypíše výsledky abecedně podle znaku. V současnosti nenabízí možnost seřadit je podle počtu.

Četnost znaků v procentech

Samotné počty se obtížně porovnávají mezi texty různé délky. Proto se četnost často vyjadřuje jako procento z celkového počtu znaků:

$f(c) = \frac{n_c}{N} \times 100\%$

Zde $n_c$ označuje, kolikrát se objeví znak $c$, a $N$ je celkový počet znaků v textu. Tento nástroj uvádí skutečné počty a celkový počet znaků, nikoli sloupec s procenty, ale procento pro libovolný znak lze vypočítat vydělením jeho počtu celkovým počtem a vynásobením hodnotou 100.

Praktický příklad

Vezměme slovo „mississippi“, které má 11 znaků a neobsahuje mezery ani interpunkční znaménka.

Počítáním jednotlivých písmen získáme:

Tabulka je seřazena abecedně (i, m, p, s), stejně jako tento nástroj řadí své výsledky. Součet počtů je 11, tedy celková délka slova. Sloupec s procenty vznikne vydělením každého počtu hodnotou 11 a vynásobením hodnotou 100, například 4 ÷ 11 × 100 ≈ 36,4 %.

Jak tento nástroj používat

Zadejte nebo vložte text do vstupního pole. Nástroj jej analyzuje okamžitě, bez nutnosti stisknout tlačítko. Jak se text mění, seznam znaků a sloupcový graf se aktualizují.

Sekce s výsledky zobrazuje:

• Sloupcový graf s jedním sloupcem pro každý znak. Vyšší sloupce znamenají, že se znak objevuje častěji.
• Celkový počet znaků v textu včetně mezer a interpunkčních znamének.
• Seznam jednotlivých znaků a jejich přesných počtů.

Tlačítko „Kopírovat“ naformátuje výsledky jako prostý text, přičemž na každém řádku bude jeden znak a jeho počet; výsledky jsou připravené k vložení do tabulky nebo dokumentu. Mezery jsou v tomto výstupu označeny jako „mezera“, aby nebyly zaměněny za prázdné řádky.

V běžném anglickém textu je pět nejčastějších písmen E, T, A, O a I. Text, v němž se vzácná písmena jako Q nebo Z objevují neobvykle často, může být zakódovaný, zašifrovaný nebo napsaný v jiném jazyce.

Využití analýzy četnosti znaků

Luštění substitučních šifer

Substituční šifra nahrazuje každé písmeno zprávy jiným písmenem nebo symbolem, a to v celém textu stejně. Protože je náhrada důsledná, zůstává v zašifrovaném textu zachován vzorec četnosti původního jazyka. V angličtině tvoří písmeno E asi 12 % všech písmen. Pokud se některý symbol v šifrovaném textu objevuje přibližně s touto četností, je silným kandidátem na zástupce písmene E. Byla to hlavní metoda prolamování substitučních šifer po celá staletí, než ji moderní šifrování učinilo zastaralou pro cokoli kromě hádanek a historických dokumentů.

Komprese dat

Kompresní formát DEFLATE, který používá nástroj gzip, kombinuje metodu LZ77 s Huffmanovým kódováním. Huffmanův kód se vytváří z četností symbolů. Znaky, které se vyskytují často, dostanou krátké binární kódy a vzácné znaky delší. Protože běžné znaky zabírají na jeden výskyt méně místa, celý soubor se zmenší, aniž by se ztratila jakákoli informace.

Odhalování problémů s kódováním

Text, v němž se zobrazují podivné, neočekávané znaky (například „é“ místo očekávaného „é“), často poukazuje na nesoulad mezi kódováním znaků, v němž byl soubor uložen, a kódováním použitým při jeho načtení. Graf četnosti s neobvyklým nárůstem podivných symbolů místo běžných písmen může pomoci problém s kódováním potvrdit.

Identifikace jazyka

Různé jazyky mají různé typické rozdělení znaků. Angličtina upřednostňuje E, T a A. Němčina navíc používá písmena jako ä, ö a ü, která se v angličtině nevyskytují vůbec. Porovnání četností znaků v textu se známými jazykovými profily dává rychlý, přibližný způsob, jak odhadnout jeho jazyk.

Styl psaní a autorství

Protože autoři mívají ustálené návyky v používání interpunkce a písmen, mohou vzorce na úrovni znaků sloužit jako jeden z dílčích důkazů při určování autorství. Samotná četnost znaků jen zřídka prokáže, kdo něco napsal; nejlépe funguje v kombinaci s volbou slov, délkou vět a dalšími stylistickými znaky.

Další metody analýzy textu

Četnost znaků není jediným způsobem analýzy textu.

• Četnost slov počítá celá slova místo znaků. Má blíže k významu textu a běžně se používá při výzkumu klíčových slov a analýze témat.
• Analýza n-gramů zkoumá krátké posloupnosti znaků nebo slov, například dvojice či trojice. Prediktivní klávesnice a automatické doplňování tuto metodu používají k odhadu dalšího písmene nebo slova.
• Analýza sentimentu posuzuje, zda text působí pozitivně, negativně nebo neutrálně, a používá k tomu metody výrazně přesahující prosté počítání.
• Analýza čitelnosti, například pomocí skóre Flesch–Kincaid, odhaduje obtížnost čtení textu na základě délky vět a slov.

Často kladené otázky

Co vám analýza četnosti znaků prozradí?

Ukazuje, jak často se jednotlivé znaky v textu objevují. Výsledky mohou odhalit vzorce užitečné v kryptografii, při kompresi, odhalování chyb v kódování nebo odhadování jazyka textu.

Jak tento nástroj řadí výsledky?

Řadí znaky abecedně. Možnost řazení podle počtu neexistuje; nejčastější a nejméně časté znaky je nutné najít procházením počtů nebo ze sloupcového grafu.

Zobrazuje nástroj procenta?

Ne. Uvádí skutečný počet každého znaku a celkový počet znaků. Procento lze vypočítat vydělením počtu daného znaku celkovým počtem a vynásobením hodnotou 100.

Dokáže analýza četnosti znaků prolomit moderní šifrování?

Ne. Funguje pouze proti jednoduchým substitučním šifrám, v nichž jeden znak vždy zastupuje stejný náhradní znak. Moderní šifrování, například AES, vytváří výstup bez takového konzistentního vzorce, takže četnosti neodhalí nic o původní zprávě.

Počítá nástroj mezery a interpunkční znaménka?

Ano. Počítá se každý znak na vstupu včetně mezer, tabulátorů, zalomení řádků a interpunkčních znamének. Mezery bývají v běžném textu často vůbec nejčastějším znakem.

Kolik textu je potřeba pro spolehlivé vzorce?

Pevné minimum neexistuje. Velmi krátký text může čistě náhodou vykazovat četnosti, které se od očekávaného vzorce hodně liší. Delší vzorky se obvykle shodují se známými jazykovými vzorci lépe.

Reference

1. Naskręcki, B., Univerzita Adama Mickiewicze. Elements of Cryptanalysis, Chapter 3: Frequency Analysis. Frequency analysis – Al-Kindího pojednání o analýze četnosti, napsané kolem roku 850 n. l.
2. Cornell University, katedra matematiky. English Letter Frequency. Tabulka četnosti písmen v angličtině – E s podílem 12,02 %, dále T, A, O a I, ve vzorku o 40 000 slovech.
3. IETF. RFC 1951: DEFLATE Compressed Data Format Specification version 1.3. RFC 1951 – DEFLATE kombinuje LZ77 a Huffmanovo kódování; Huffmanovy kódy se vytvářejí z četností symbolů.