Soundex • Alexander Piperski • Vedecko-populárne problémy na "prvkoch" • Lingvistika

Soundex

Soundex je algoritmus na kódovanie vlastných mien. Vznikla v rokoch 1918-1922. v Spojených štátoch, Robert Russell a Margaret King Odell, s cieľom uľahčiť hľadanie podobných znejúcich krstných mien. V polovici 20. storočia bola spoločnosť Soundex široko používaná v USA pri analýze výsledkov sčítania obyvateľov v rokoch 1890-1920. Nižšie je uvedený príklad karty sčítania ľudu z roku 1910. Tu vidíte, že Soundex kód pre priezvisko Wilson vyzerá ako W425:

úloha

Zoznam posledných mien a ich zodpovedajúcich Soundex kódov je uvedený v zmätenom poradí. Niektoré znaky chýbajú:

Allaway, Anderson, Ashcombe, Buckingham, drobný obchodník, Colquhoun, Evans, Fairwright, Kingscott, lewis, Littlejohns, Stanmore, Stubbs, tocher, Tonksová, Whytehead

S312, T␣6␣, ␣5␣3, C42␣, T520, L␣42, A536, C155, 623, S356, 252, 1552, 332, A251, A400, L2␣0

Úloha 1. Postupne popíšte, ako sa generuje kód Soundex.

Úloha 2. Priraďte názvy a kódy Soundex a vložte chýbajúce znaky.

Úloha 3. Vytvorte Soundex kódy pre nasledujúce priezviská: Ferguson, Fitzgerald, Hamnett, Keefe, Maxwell, razom, shaw, posun vo.


pomôcť

Každý kód pozostáva z písmena a troch čísel. Písmeno opakuje prvé písmeno posledného mena a čísla zakódujú súhlasy, ktoré sú v ďalšom názve.


rozhodnutie

Všetky kódy Soundex sa skladajú z latinského písmena a troch číslic. Nie je ťažké odhadnúť, prečo je kód pre priezvisko wilson začína W: pretože je to prvé písmeno tohto priezviska.

Keď sa ukázalo, že prvé písmeno je zachované, úloha sa rozdelí na šesť malých úloh s zmätenou korešpondenciou:

Allaway, Anderson, Ashcombe
A536, A251, A400

drobný obchodník, Colquhoun
C42H, C155

lewis, Littlejohns
L␣42, L2␣0

Stanmore, Stubbs
S312, S356

tocher, Tonksová
T␣6␣, T520

Buckingham, Evans, Fairwright, Kingscott, Whytehead
␣5␣3, ␣623, ␣252, ␣152, ␣330

Pripomeňme si, že Soundex je algoritmus určený na hľadanie podobných zvukových slov. Pravdepodobne by čísla mali zakódovať určitý charakteristický zvuk. Je možné predpokladať, že zodpovedajú zhodným písmenám, ktoré sa nachádzajú v priezvisku. Je pravda, že iba šesť číslic znamená, že tá istá číslica kóduje celé skupiny súhlásk.

Tieto skupiny sú:

bpv (f)cgjkqs (xz)dtlmnr
123456

Klasifikácia písmen v Soundexu viac či menej zodpovedá klasifikácii zvukov podľa toho, ako sa vyslovujú: skupina 1 zahŕňa súhlasy vyslovované za účasti pier; v skupine 2 súhlasy vyslovované pomocou zadnej časti jazyka a hvízdanie; skupina 3 – predzvukový okluzálny (d a T); v skupine 5 – nazálne. Vychádzajúc z toho je možné rozdeliť do skupín a tých listov, ktoré sme v podmienkach nevideli (v tabuľke sú uvedené v zátvorkách). písmeno F bude patriť do skupiny 1 do labiálnych súhlasov (už existuje protipár F hluchotvorná) a x a z – v skupine 2 (x pozostáva z k a sktoré sú v skupine 2, ale z zvonenie pár s). literatúra hod a w Táto tabuľka nie je zahrnutá: ignorujú sa pri generovaní kódu Soundex. To isté platí aj pre list. yčo sa v angličtine považuje za samohlásku.

Môžete si všimnúť, že kombinácie súhlasov z jednej skupiny zodpovedajú iba jednej číslici v kóde. Napríklad z údajov v podmienkach kódov priezvisk Kingscott môže zodpovedať len ␣5␣3, za ktoré zodpovedá 5 n, 3 – pre Ta číslo v strede by malo byť zodpovedné za g, s a C (samozrejme, toto číslo bude číslo 2).

Nuly v kóde zodpovedajú prípadom, keď súhlasy nestačili na obsadenie troch pozícií. Môžete to napríklad nastaviť Allaway – to je A400, kde dva l zodpovedá 4 a , w, a y nezapojili sa do kódovania.

Odpoveď na úlohu 1. Sumarizáciou všetkých týchto pozorovaní môžeme vytvoriť kódovací algoritmus. Je dôležité venovať pozornosť poradie operácií, aby bolo možné prijímať všetky kódy bez chýb.

1. Nechajte prvé písmeno nezmenené.

2. Odstrániť hod a w.

3. Nahraďte všetky súhlasy číslami (písmená, ktorých najčastejšie čítania sú podobné, sú kombinované do skupín):

bfpvcgjkqsxzdtlmnr
123456

4. Dve alebo viac rovnakých čísel za sebou, aby ste ich znížili na jednu.

5. Odstráňte všetky samohlásky (, e, ja, o, u, y).

6. Ponechajte iba prvé tri číslice alebo pridajte nuly napravo, aby bola dĺžka kódu jedna písmena a tri číslice.

Odpoveď na úlohu 2 (vymazané znaky sú podčiarknuté).

Allaway: A400, Anderson: A536, Ashcombe: A251, Buckingham: B252, drobný obchodník: C155, Colquhoun: C425, Evans: E152, Fairwright: F623, Kingscott: K523, lewis: L200, Littlejohns: L342, Stanmore: S356, Stubbs: S312, tocher: T260, Tonksová: T520, Whytehead: W330.

Odpoveď na úlohu 3.

Ferguson: F622, Fitzgerald: F326, Hamnett: H530, Keefe: K100, Maxwell: M240, razom: R200, shaw: S000, posun vo: U143.


Doslov

Problém, pre ktorý bol algoritmus Soundex použitý (a niekedy sa používa aj dnes), je všeobecne nazývaný fuzzy reťazec vyhľadávanie (približné zhody reťazca, fuzzy reťazec vyhľadávanie).

Schopnosť pochopiť, že dva jazykové výrazy sú ekvivalentné, je dôležitou súčasťou poznania ľudského jazyka. Táto zručnosť sa môže prejaviť na rôznych úrovniach. Napríklad, na úrovni sémantiky (slovné významy) a syntaxe (spojenie medzi slovami vo fráze a vetou), ruský hovorca ľahko pochopí, že frázy Vo vzdialenosti sto metrov plával do 45 sekúnd, Po sto metroch sa mu plazilo 45 sekúnd. a Plavil jaskyňu v ¾ minúte (Apresyan 1995: I, 12) znamenajú to isté. Podobne na úrovni listov to ľahko pochopíme Muravyov a Muravyev – je to rovnaké priezvisko, ale natalia a natalia – rovnaký názov (aj keď v situáciách, kde chcem nájsť chybu, môžeme falošne povedať niečo ako: "No, samozrejme, hovorí Natalia Muravyová, a máte pas – Natalia Muravyová").Ale automatizácia takejto základnej schopnosti pochopiť rovnocennosť slov a výrazov, ktoré sa nezhodujú presne, je veľmi náročná úloha.

Takéto nezrovnalosti sa v praxi vyskytujú pravidelne. Soundex bol pôvodne vynájdený práve pre porovnanie vlastných mien, pretože na začiatku 20. storočia bola zmena pravopisu vlastných mien oveľa vyššia než teraz, ale aj teraz to nie je úplne znížené na nulu. Kniha (Lisbach, Meyer 2013: 15) poskytuje príklad dvoch možností na zaznamenávanie informácií o tej istej osobe – napríklad z vypočutia v call centre a pri prepísaní z dokumentov s rozdelením do polí:

Kate suzanne jankowiz
Belrive Str. 20, 65920 Frankfurt am Main (Nemecko)
KateřinaSusanJenniferYankovits-Brunner
20BellerivestrasseFrankfurt / M65920DE

Dôležitou výhodou Soundexu, ktorá v mnohých ohľadoch zabezpečuje jeho popularitu, je jednoduchá implementácia: pre tento algoritmus nie je potrebný najmä slovník. Soundex je spomenutý v klasike Donalda Knutha "The Art of Programming" (Knuth 1998: 395-396). Avšak v prvom vydaní (Knuth 1973: 391-392) autor ešte nebral do úvahy všetky jemnosti a navrhol súčasne vyhadzovať samohlásky, hod a w; potom napríklad drobný obchodník dáva nie drobný obchodník → Capman → Ca15a5 → C155 a drobný obchodník → Cpmn → C155 → C15 → C150.

Soundex je implementovaný v desiatkach programovacích jazykov. Napríklad vstavaná funkcia SOUNDEX je v systéme správy databáz MySQL.A v programe Python 3 môžete zaznamenať celý obsah tejto úlohy v niekoľkých riadkoch (autorom kódu je Ivan Deržánsky):

Nevýhody Soundex leží na povrchu. Niekedy tento algoritmus nedokáže rozpoznať podobnosti medzi veľmi blízkymi priezviskami: napríklad, Levinson dostane kód L152 a Lewinson – kód L525. Okrem toho Soundex nefunguje dobre v situáciách, kde je výslovnosť veľmi odlišná od pravopisu, čo sa často deje v angličtine. Napríklad škótske priezvisko Colquhoundaný v stave číta niečo ako Kehun, a jeho kód Soundex C425 odráža nepodložené l (4) a q (2). Ďalšou variantou tohto priezviska je Colhoun (pamätajte na kapitána Cassia Kolhúna z "Headless Horseman" Mine Reed) – má iný kód: ukáže sa to ako C450. Avšak v takomto hláskovaní sa zvyčajne vyslovuje l (Kolhun), takže rôzne kódy v tomto prípade nie sú tak zlé.

Na vyriešenie problému fuzzy hľadania sa používajú pokročilejšie algoritmy. Môžu to byť ako fonetické algoritmy ako Soundex (napríklad Metaphone), tak aj úplne odlišné prístupy – napríklad súvisiace s redakčnou vzdialenosťou, úloha, o ktorej už bola publikovaná na našich stránkach.

Referencie:
1. Yu D. Apresyan. Vybrané diela. T.I // Lexikálna sémantika. M .: Jazyky ruskej kultúry, 1995.
2. Donald Knuth. Umenie počítačového programovania. Vol.3: Triedenie a vyhľadávanie // Čítanie (Mass.), 1973.
3. Donald Knuth. Umenie počítačového programovania. Vol. 3: Triedenie a vyhľadávanie. 2nd ed. // Reading (Mass.), 1998.
4. Bertrand Lisbach & Victoria Meyer. Zhoda s jazykovou identitou // Wiesbaden: Springer, 2013.

Táto úloha bola využitá na Medzinárodnej olympiáde XIII. Lingvistiky v roku 2015 v Blagoevgrad (Bulharsko).


Like this post? Please share to your friends:
Pridaj komentár

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: