Jak na přelkepy 2: standardizace pomocí fonetických algoritmů

Ve finále Ligy mistrů hrál i Bastian Schweinsteiger, Franck Ribéry, Anatoliy Tymoshchuk, José Bosingwa, Florent Malouda. Zvládnete to přečíst? A zvládnete to i stejně napsat? Já ne.

A další otázka. Bývalý lybijský vůdce* se jmenoval?

  • Muammar Kaddáfí
  • Moammar Gadhafi
  • Muammar Qaddafi
  • Muammar Gaddafi

Všechno, závisí, na který zápis jména právě narazíte – označuje tu samou osobu.

Redaktorka ABC News našla 112 způsobů zapsání tohoto jména (a to brala do úvahy jenom vybrané zdroje).

Pokud budete chtít hledat toto jméno v textu, elegantním řešením může být (pro část Kaddáfí bez diakritiky) použití regulárního výrazu b[KG]h?add?af?fi$b.

Podívejme se na to ale jinak. Uvažujme podobnosti v databáze krátkých textových řetězců (například příjmení).

* – Problém se zápisem jména není jenom u libyjských politiků. Taky není jednoznačné, zda je ministr zahraničních věcí Karel nebo německy Karl a bývalý ministr dopravy není Gustáv, ale Gustav (to jsou jenom příklady z posledních 2 vlád).

Ekvivalence díky standardizaci

Pro potřeby vyhledávání (například proti existujícímu seznamu osob nebo množině nejčastějších slov) můžeme použít i standardizaci. Za standardizaci pro potřebu tohoto článku budu považovat nahrazení textu (řekneme jméno osoby) nějakým výrazem – reprezentantem, který vznikl z textu pro potřeby další analýzy. Standardizací může být například odstranění diakritiky, úprava na velká písmena, odstranění nealfanumerických znaků a samohlásek, vyhození titulů, nahrazení dvou stejných znaků následujících za sebou stejným znakem a podobně. Řekneme, že podobnost 2 slov na základě standardizace znamená, že tato dvě slova mají stejného reprezentanta.Tato podobnost má výhodu, že je nejen reflexivní a symetrická, ale i tranzitivní (tým se liší od Levenstheina i od Jaro-Winklerminulého článku). Podobnost na základě standardizace je tedy ekvivalence. Díky tomu může být reprezentant v naší DB indexován a tak se samotné vyhledávání výrazně zrychlí (ale časově náročnější budou DML SQL příkazy).

Fonetické algoritmy

V tomto pohledu je však i použití fonetických algoritmů standardizací. Fonetické algoritmy vycházejí z různých přepisů zvukové podoby jednotlivých slov a hledají k slovu nejlepšího reprezentanta.

Podívejme se na slovo Kaddáfi z výše uvedeného seznamu pomocí nejznámějších fonetických algoritmů (bez diakritiky). V tabulce jsem použil implementaci z VB pro Excel. Stejná barva vyjadřuje stejného reprezentanta.

Tabulku najdete i v textové podobě.

Soundex (rok 1918) je nejznámější a byl vyvinut pro potřeby opětovné analýzy výsledků sčítání lidu v USA (fonetické algoritmy se na tento typ úkolů skvěle hodí – máte mnoho záznamů od lidí původem z různých častí světa a přepis jejich jmen do latinky není jednoznačný, navíc děláte analýzu až po získání všech dat).

Jak funguje soundex:

  1. Zachová se první písmeno a ze zbytku se vyhodí písmena a, e, i, o, u, y, h, w.
  2. Druhé a další písmeno se nahradí číslicí dle schématu.
    • b, f, p, v ⇒ 1
    • c, g, j, k, q, s, x, z ⇒ 2
    • d, t ⇒ 3
    • l ⇒ 4
    • m, n ⇒ 5
    • r ⇒ 6
  3. Dvě stejná čísla za sebou se nahradí jednou číslicí.
  4. Pokud je výraz delší než 4 znaky, ořízne se zleva na 4 znaky.
  5. Pokud je výraz kratší než 4 znaky, doplní se zprava na 4 znaky číslicí 0.

Vidíme, že pokud je špatně zapsáno první písmeno nebo narazíme na prohození souhlásek nebo na jejich přidání nebo odebrání (pokud ovlivní výsledek), tak nám soundex nepomůže.

D-M soundex (1985), taky židovský index neboli východoevropský index, je novější a vytváří k slovu číselné reprezentanty (pozor, může jich být i víc – takže opatrně s tou ekvivalencí). Do úvahy bere i písmena s diakritikou, a to z polské nebo rumunské abecedy.

Metaphon (1990) vychází z anglické výslovnosti. Existuje i verze Double metaphone (2000), který se snaží kromě jiné vzít do úvahy i slova slovanského původu. Stejného autora má i Metaphone 3 (2009).

NYSIIS (1970) je algoritmus vyvinutý v rámci New York State Identification and Intelligence System. Je o 2,7 % lepší než soundex. Detaily v přehledné online verzi.

Existují i další fonetické algoritmy jako caverphone, MRA,…

Použití fonetických algoritmů (v češtině)

Fonetické algoritmy se hodí, pokud nevíme, jak máme slovo napsat, pokud známe jeho zvukovou podobu. Naopak se nehodí, pokud uděláme ve slově „obyčejný“ překlep (tedy pokud nejde o překlep „správným“ způsobem). Zvláště se fonetické algoritmy hodí ke standardizaci údajů získaných přes zaznamenávání hlasu, což je stále aktuálnější (uměl vás váš mobil poslechnout před 10 lety?).

Na druhou stranu fonetické algoritmy jednotlivá slova často výrazně upraví, a tak můžou vrátit stejné reprezentanty pro výrazně odlišná slova. Například soundex vrátí pro slova Novák a Neubyfekeqoax stejnou hodnotu – N120.

Soundex funguje i pro některé typické chyby v češtině jako i/y nebo s/z. Nicméně použití fonetických algoritmů pro libovolné české slovo je díky blízkosti psané a mluvené formy v češtině málo přínosné (oproti angličtině).

Existují ale skupiny slov, u kterých to v češtině má smysl, a to například u jména a příjmení (s německým, ukrajinským nebo vietnamským původem), odborné výrazy a obecně slova přijímaná z jiných jazyků. Tam se fonetické algoritmy hodí. Například Levensteinh, Levenstajn, Levenshtein, Levensten i Levhenstein mají soundex L152.

Vystudoval matematickou statistiku na MFF UK, Pracuje jako matematik pro vyhledávač hotelů trivago

Věděli jste, že nám můžete zasílat zprávičky? (Jen pro přihlášené.)

Komentáře: 12

Přehled komentářů

Karel Špatný příklad (arabština)
Martin Hassman Re: Špatný příklad (arabština)
Me Re: Špatný příklad (arabština)
Peter Brejčák Re: Špatný příklad (arabština)
Karel Re: Špatný příklad (arabština)
Me Re: Špatný příklad (arabština)
petr_p Re: Špatný příklad (arabština)
Biktop Anatoliy Tymoshchuk? (off topic)
Peter Brejčák Re: Anatoliy Tymoshchuk? (off topic)
backup Re: Anatoliy Tymoshchuk? (off topic)
to máš fuk Re: Anatoliy Tymoshchuk? (off topic)
RiHL Přelkepy
Zdroj: https://www.zdrojak.cz/?p=3660