Analýza a vizualizácia frekvencie znakov

Čo je analýza frekvencie znakov?

Analýza frekvencie znakov je proces počítania, koľkokrát sa každý znak objaví v texte. Zahŕňa písmená, číslice, medzery, interpunkčné znamienka a všetky ostatné symboly v texte. Výsledkom je jednoduchá tabuľka alebo graf: jeden znak, jeden počet.

Tento nástroj prijme ľubovoľný text vložený alebo napísaný do vstupného poľa a automaticky spočíta každý znak. Zobrazí stĺpcový graf počtov, takže najčastejšie znaky sú na prvý pohľad výrazné. Po ukázaní na stĺpec alebo klepnutí naň sa zobrazí presný počet daného znaku.

Táto technika je stará. Arabský učenec Al-Kindí ju v 9. storočí opísal ako spôsob lúštenia jednoduchých šifier. Dnes sa používa aj pri kompresii údajov, kontrole pravopisu a kódovania a pri základnej identifikácii jazyka.

Ako vypočítať frekvenciu znakov

Manuálny výpočet frekvencie znakov pozostáva z troch krokov:

1. Prejdite text znak po znaku vrátane medzier a interpunkčných znamienok.
2. Veďte priebežný súčet pre každý odlišný znak. Nový znak začína na hodnote 1; opakovaný znak pridá k svojmu doterajšiemu súčtu hodnotu 1.
3. Uveďte každý znak s jeho konečným súčtom.

Tento nástroj robí to isté automaticky pomocou dátovej štruktúry nazývanej hašovacia mapa (vyhľadávacia tabuľka, ktorá ukladá hodnotu pod kľúč). Pri každom znaku v texte overí, či už má daný znak v mape záznam. Ak áno, k uloženému počtu pripočíta 1. Ak nie, vytvorí nový záznam s počtom 1. Táto metóda spracuje každý znak presne raz, takže čas potrebný na jej vykonanie rastie priamo úmerne s dĺžkou textu, nie rýchlejšie.

Po spočítaní nástroj zoradí výsledky abecedne podľa znakov. V súčasnosti neponúka možnosť zoradiť ich podľa počtu.

Frekvencia znakov v percentách

Samotné počty sa pri porovnávaní textov rôznej dĺžky môžu ťažko porovnávať. Preto sa frekvencia často vyjadruje ako percentuálny podiel z celkového počtu znakov:

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

V tomto vzorci $n_c$ označuje počet výskytov znaku $c$ a $N$ je celkový počet znakov v texte. Tento nástroj uvádza nespracované počty a celkový počet znakov, nie stĺpec s percentami, no percento ľubovoľného znaku možno vypočítať vydelením jeho počtu celkovým počtom a vynásobením hodnotou 100.

Príklad výpočtu

Uvažujme slovo „mississippi“, ktoré má 11 znakov a neobsahuje medzery ani interpunkčné znamienka.

Počítaním jednotlivých písmen získame:

Tabuľka je zoradená abecedne (i, m, p, s), čo zodpovedá spôsobu, akým tento nástroj usporadúva výsledky. Súčet počtov je 11, teda celková dĺžka slova. Stĺpec s percentami získame tak, že každý počet vydelíme hodnotou 11 a vynásobíme hodnotou 100, napríklad 4 ÷ 11 × 100 ≈ 36,4 %.

Ako používať tento nástroj

Napíšte alebo vložte text do vstupného poľa. Nástroj ho analyzuje okamžite, bez tlačidla, ktoré by bolo potrebné stlačiť. Keď sa text zmení, zoznam znakov a stĺpcový graf sa aktualizujú.

Časť s výsledkami zobrazuje:

• Stĺpcový graf s jedným stĺpcom pre každý znak. Vyššie stĺpce znamenajú, že znak sa vyskytuje častejšie.
• Celkový počet znakov v texte vrátane medzier a interpunkčných znamienok.
• Presný počet jednotlivých znakov, ktorý sa zobrazí po ukázaní na príslušný stĺpec alebo po klepnutí naň.

Tlačidlo „Kopírovať“ naformátuje výsledky ako obyčajný text, pričom na každom riadku bude jeden znak a jeho počet, pripravený na vloženie do tabuľkového procesora alebo dokumentu. Medzery sú v tomto výstupe označené slovom „medzera“, aby sa nezamenili za prázdne riadky.

V bežnom anglickom texte patria písmená ako E, T, A, O a I zvyčajne medzi najčastejšie. Text, v ktorom sa nezvyčajne často objavujú zriedkavé písmená ako Q alebo Z, môže byť kódovaný, šifrovaný alebo napísaný v inom jazyku.

Využitie analýzy frekvencie znakov

Lúštenie substitučných šifier

Substitučná šifra nahrádza každé písmeno správy iným písmenom alebo symbolom a používa pritom rovnakú náhradu v celom texte. Keďže náhrada je konzistentná, frekvenčný vzorec pôvodného jazyka sa v zašifrovanom texte zachová. V angličtine sa písmeno E vyskytuje približne v 12–13% prípadov. Ak sa jeden symbol v šifrovanom texte objavuje približne s touto frekvenciou, je vhodným kandidátom na zastupovanie písmena E. Po stáročia to bola hlavná metóda lúštenia substitučných šifier, kým moderné šifrovanie neurobilo túto metódu nepoužiteľnou na čokoľvek okrem hádaniek a historických dokumentov.

Kompresia údajov

Kompresné formáty, ako sú ZIP a GZIP, využívajú frekvenciu znakov prostredníctvom prístupu nazývaného Huffmanovo kódovanie. Často sa vyskytujúce znaky dostávajú krátke binárne kódy a zriedkavé znaky dlhšie kódy. Keďže bežné znaky zaberajú pri každom výskyte menej miesta, celý súbor sa zmenší bez straty informácií.

Odhaľovanie problémov s kódovaním

Text, v ktorom sa zobrazujú zvláštne, neočakávané znaky (napríklad „é“ namiesto očakávaného „é“), často poukazuje na nesúlad medzi kódovaním znakov, v ktorom bol súbor uložený, a kódovaním použitým pri jeho načítaní. Graf frekvencie, ktorý namiesto bežných písmen zobrazuje nezvyčajný nárast podivných symbolov, môže pomôcť potvrdiť problém s kódovaním.

Identifikácia jazyka

Rôzne jazyky majú odlišné typické rozdelenie znakov. V angličtine prevládajú E, T a A. Nemčina používa oveľa viac výskytov písmen E a N a tiež písmená ako ä, ö a ü, ktoré sa v angličtine vôbec nevyskytujú. Porovnanie frekvencií znakov v texte so známymi jazykovými profilmi poskytuje rýchly a približný spôsob odhadu jeho jazyka.

Štýl písania a autorstvo

Keďže autori mávajú ustálené návyky v používaní interpunkcie a písmen, vzorce na úrovni znakov môžu slúžiť ako malá časť dôkazov pri určovaní autorstva. Samotná frekvencia znakov len zriedka dokáže, kto niečo napísal; najlepšie funguje v kombinácii s výberom slov, dĺžkou viet a ďalšími štylistickými znakmi.

Ďalšie metódy analýzy textu

Frekvencia znakov nie je jediný spôsob analýzy textu.

• Frekvencia slov počíta celé slová namiesto znakov. Viac súvisí s významom textu a bežne sa používa pri výskume kľúčových slov a analýze tém.
• Analýza n-gramov skúma krátke postupnosti znakov alebo slov, napríklad dvojice alebo trojice. Prediktívne klávesnice a automatické dopĺňanie túto metódu používajú na odhad ďalšieho písmena alebo slova.
• Analýza sentimentu určuje, či text pôsobí pozitívne, negatívne alebo neutrálne, pričom využíva metódy ďaleko presahujúce jednoduché počítanie.
• Analýza čitateľnosti, napríklad pomocou skóre Flesch-Kincaid, odhaduje náročnosť čítania textu na základe dĺžky viet a slov.

Často kladené otázky

Čo vám prezradí analýza frekvencie znakov?

Ukazuje, ako často sa jednotlivé znaky objavujú v texte. Výsledok môže odhaliť vzorce užitočné v kryptografii, pri kompresii, odhaľovaní chýb v kódovaní alebo odhadovaní jazyka textu.

Ako tento nástroj zoraďuje výsledky?

Znaky zoraďuje abecedne. Neexistuje možnosť zoradiť ich podľa počtu. Najčastejšie a najmenej časté znaky treba nájsť prečítaním stĺpcového grafu alebo prehľadaním počtov v skopírovanom texte.

Zobrazuje nástroj percentá?

Nie. Uvádza nespracovaný počet každého znaku a celkový počet znakov. Percento možno vypočítať vydelením počtu daného znaku celkovým počtom a vynásobením hodnotou 100.

Dokáže analýza frekvencie znakov prelomiť moderné šifrovanie?

Nie. Funguje iba proti jednoduchým substitučným šifrám, pri ktorých jeden znak vždy zastupuje ten istý náhradný znak. Moderné šifrovanie, napríklad AES, vytvára výstup bez takéhoto konzistentného vzorca, takže počty frekvencií neodhaľujú nič o pôvodnej správe.

Počíta nástroj aj medzery a interpunkciu?

Áno. Počíta sa každý znak vo vstupnom texte vrátane medzier, tabulátorov, koncov riadkov a interpunkčných znamienok. Medzery sú v bežnom texte často jediným najčastejším znakom.

Koľko textu je potrebného na spoľahlivé vzorce?

Rozumným minimom je niekoľko stoviek znakov. Veľmi krátky text môže čisto náhodou vykazovať frekvencie, ktoré sa výrazne líšia od očakávaného vzorca. Dlhšie vzorky s tisícom alebo viacerými znakmi sa zvyknú viac približovať známym jazykovým vzorcom.

Zdroje

1. MDN Web Docs: Map — dokumentácia k dátovej štruktúre hašovacej mapy používanej na efektívne počítanie znakov.
2. Shannon, C. E. (1951). „Prediction and entropy of printed English.“ The Bell System Technical Journal, 30(1), 50-64.
3. Huffman, D. A. (1952). „A Method for the Construction of Minimum-Redundancy Codes.“ Proceedings of the IRE, 40(9), 1098-1101.
4. Huffmanovo kódovanie — Wikipedia