Soundex • Aleksandrs Piperski • Zinātniski populāras problēmas "Elementos" • Lingvistika

Soundex

Soundex ir algoritms pareizu nosaukumu kodēšanai. Tas tika izveidots 1918-1922. ASV, Roberts Russell un Margaret King Odell, lai atvieglotu meklēšanu līdzīgu skanvārdi. 20. gadsimta vidū Soundex tika plaši izmantots ASV, analizējot 1890.-1920. Gada iedzīvotāju skaitīšanas rezultātus. Zemāk ir piemērs 1910. gada skaitīšanas kartītei. Šeit jūs varat redzēt, ka Soundex kods pēdu vārdam Wilson izskatās kā W425:

Uzdevums

Pseidonīmu un to atbilstošo Soundex kodu kodi ir norādīti neskaidrā secībā. Trūkst dažu rakstzīmju:

Allaway, Andersons, Ashcombe, Buckingham, Chapman, Colquhoun, Evans, Fairwright, Kingscott, Lewis, Littlejohns, Stanmore, Stubbs, Tocher, Tonks, Kāpēc iet

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

1. uzdevums. Sīki aprakstiet, kā ģenerē Soundex kodu.

2. uzdevums. Saskaņojiet Soundex vārdus un kodus un ievietojiet trūkstošās rakstzīmes.

3. uzdevums. Izveidojiet Soundex kodu šādiem vārdiem: Fergusons, Fitzgerald, Hamnett, Keefe, Maxwells, Razijs, Šovs, Upfield.


Padoms

Katrs kods sastāv no burta un trim cipariem. Vēstule atkārto pirmās uzvārda vēstuli, un numuri kodē līdzskaņus, kas atrodas nākamajā vārdam.


Šķīdums

Visi kods Soundex sastāv no latīņu burta un trīs cipariem. Nav grūti uzminēt, kāpēc uzvārda kodu Vilsons sākas W: jo tā ir šī vārda pirmā vēstule.

Kad kļuva skaidrs, ka pirmā vēstule ir saglabāta, uzdevums sadalās sešos mazos uzdevumos ar neskaidrām atbilstībām:

Allaway, Andersons, Ashcombe
A536, A251, A400

Chapman, Colquhoun
C42␣, C155

Lewis, Littlejohns
L␣42, L2␣0

Stanmore, Stubbs
S312, S356

Tocher, Tonks
T66, T520

Buckingham, Evans, Fairwright, Kingscott, Kāpēc iet
␣5␣3, ␣623, ␣252, ␣152, ␣330

Atcerieties, ka Soundex ir algoritms, kas paredzēts, lai atrastu līdzīgi skanus vārdus. Iespējams, ka skaitļiem vajadzētu kodēt kādu raksturīgu skaņu. Ir iespējams hipotēzēt, ka tie atbilst līdzvārdiskiem burtiem, kas atrodami uzvārdā. Patiesi, tikai seši cipari nozīmē, ka viens un tas pats cipars kodē veselas līdzskaņu grupas.

Šīs grupas ir:

bpv (f)cgjkqs (xz)dtlmnr
123456

Burtu klasifikācija Soundex vairāk vai mazāk atbilst skaņu klasifikācijai atbilstoši to izteikšanai: 1. grupa ietver līdzskaņus, kas izteikti ar lūpu piedalīšanos; 2. grupā līdzskaņi izteikti, izmantojot mēles aizmuguri un svilpšanu; 3. grupa – priekšgala okluzāls (d un t); 5. grupā – deguns. Pamatojoties uz to, ir iespējams sadalīt grupās un tajās vēstulēs, kuras mēs neredzējām stāvoklī (tabulā tās ir iekļautas iekavās). Vēstule f iedalīsies 1. grupā līdz labajās līdzskaņās (jau ir vpāris f kurfs izteikts) un x un z – 2. grupā (x sastāv no k un skas ir 2. grupā, bet z – zvana pāri uz s) Vēstules h un w Šī tabula nav iekļauta: tās tiek ignorētas, ģenerējot Soundex kodu. Tas pats attiecas arī uz vēstuli. ykas angļu valodā tiek uzskatīts par patskaņu.

Jūs varat pamanīt, ka vienā grupā līdzskaņu kombinācijas atbilst tikai vienam ciparam kodā. Piemēram, no datiem uzvārda kodu statusā Kingscott var atbilst tikai ␣5␣3, kurā 5 ir atbildīgs n, 3 – par tun par to ir jāuzņemas numurs vidū g, s un c (protams, tas būs skaitlis 2).

Kodu nulles atbilst gadījumiem, kad līdzskaņiem nebija pietiekami, lai aizpildītu trīs pozīcijas. Piemēram, jūs varat to iestatīt Allaway – tas ir A400, kur divi l atbilst 4, un a, w, a un y nepiedalās kodēšanā.

Atbilde uz uzdevumu 1. Apkopojot visus šos novērojumus, mēs varam veidot kodēšanas algoritmu. Ir svarīgi pievērst uzmanību operāciju secībai, lai tā varētu saņemt visus kodus bez kļūdām.

1. Atstājiet pirmo burtu bez izmaiņām.

2. Dzēst h un w.

3. Aizstāt visus līdzskaņus ar cipariem (burti, kuru visbiežākie rādījumi ir līdzīgi, tiek apvienoti grupās):

bfpvcgjkqsxzdtlmnr
123456

4. Divus vai vairākus identiskus numurus pēc kārtas, lai samazinātu līdz vienam.

5. Noņemiet visus patskaņus (a, e, i, o, tu, y).

6. Atstājiet tikai pirmos trīs ciparus vai pievienojiet nulles pa labi, lai koda garums būtu viens burts un trīs cipari.

Atbilde uz 2. uzdevumu (atgūtās rakstzīmes ir pasvītrotas).

Allaway: A400, Andersons: A536, Ashcombe: A251, Buckingham: B252, Chapman: C155, Colquhoun: C425, Evans: E152, Fairwright: F623, Kingscott: K523, Lewis: L200, Littlejohns: L342, Stanmore: S356, Stubbs: S312, Tocher: T260, Tonks: T520, Kāpēc iet: W330.

Atbilde uz uzdevumu 3.

Fergusons: F622, Fitzgerald: F326, Hamnett: H530, Keefe: K100, Maxwells: M240, Razijs: R200, Šovs: S000, Upfield: U143.


Pēcvārds

Problēma, kurai tika izmantots Soundex algoritms (un dažkārt joprojām tiek izmantots šodien), parasti tiek saukts par izplūdušo virkņu meklēšanu (aptuvena virknes atbilstība, izplūdušo virkņu meklēšana).

Spēja saprast, ka divas valodas izteiksmes ir līdzvērtīgas, ir svarīga cilvēka valodas zināšanas. Šī prasme var izpausties dažādos līmeņos. Piemēram, semantikas (vārdu nozīmes) un sintakses līmenī (saiknes starp vārdiem frāzē un teikumā) krievu runātājs viegli saprot, ka frāzes Viņa simt metru attālumā viņš peldēja 45 sekundēs, Pēc simts metriem rāpot viņu paņēma 45 sekundes. un Viņš peldēja alu pēc ¾ minūtes (Apresyan 1995: I, 12) nozīmē to pašu. Tāpat arī burtu līmenī mēs to viegli saprotam Muravjovs un Muravyev – tas ir tas pats vārds, bet Natālija un Natālija – tas pats vārds (kaut arī situācijās, kad vēlaties atrast vainu, mēs varam nepatiesi teikt kaut ko līdzīgu: "Nu, protams, tā saka Natalia Muravyova, un jums ir pase – Natalia Muravyova")Taču automatizējot šādu pamata spēju saprast tādu vārdu un izteiksmju līdzvērtību, kas nav precīzi atbilstošas, ir ļoti grūts uzdevums.

Šādas neatbilstības praksē notiek regulāri. Soundex sākotnēji tika izgudrots precīzi nosaukumu salīdzināšanai, jo 20. gadsimta sākumā pareizo vārdu pareizrakstības atšķirības bija daudz augstākas nekā tagad, bet pat tagad tas nav pilnībā samazināts līdz nullei. Tādējādi grāmata (Lisbach, Meyer 2013: 15) sniedz piemēru no divām iespējām reģistrēt informāciju par vienu un to pašu personu – piemēram, no klausīšanās zvanu centrā un pārrakstot no dokumentiem ar iedalījumu laukos:

Kate suzanne jankowiz
Belrive iela 20, 65920 Frankfurte pie Mainas (Vācija)
KatrīnaSusanJenniferYankovits-brunner
20BellerivestrasseFrankfurt / M65920DE

Svarīga Soundex priekšrocība, kas daudzējādā ziņā nodrošināja tās popularitāti, ir vienkāršāka īstenošana: jo īpaši šī algoritma vārdnīca nav nepieciešama. Soundex tiek minēts Donalda Knuta klasiskajā programmēšanas mākslā (Knuth 1998: 395-396). Tomēr pirmajā izdevumā (Knuth 1973: 391-392) autors vēl nav ņēmis vērā visas smalkumus un ierosināja vienlaikus izteikt patskaņus, h un w; tad, piemēram Chapman dod nē Chapman → Capman → Ca15a5 → C155 un Chapman → Cpmn → C155 → C15 → C150.

Soundex tiek īstenots desmitiem programmēšanas valodu. Piemēram, iebūvētā SOUNDEX funkcija ir MySQL datu bāzes pārvaldības sistēmā.Un Python 3 jūs varat ierakstīt visu šī uzdevuma saturu vairākās rindās (koda autors ir Ivan Derzhansky):

Trūkumi Soundex atrodas uz virsmas. Dažreiz šis algoritms nespēj atklāt līdzības starp ļoti tuviem uzvārdiem: piemēram, Levinsons saņems kodu L152 un Lewinson – kods L525. Turklāt Soundex nedarbojas labi situācijās, kad izruna ļoti atšķiras no pareizrakstības, kas bieži notiek angļu valodā. Piemēram, Skotijas uzvārds Colquhoundota stāvoklī skan kaut kas līdzīgs Cahun, un tā Soundex C425 kods atspoguļo nepabeigto l (4) un q (2). Vēl viena šī vārda variācija ir Colhoun (atceraties kapteini Cassius Kolhoun no "bezgalīgi jātnieks" Mine Reed) – ir atšķirīgs kods: tas izrādās C450. Tomēr šādā pareizrakstībā parasti izrunā l (Kolhun), tādēļ šajā gadījumā dažādi kodi nav tik slikti.

Lai atrisinātu neskaidras meklēšanas problēmu, bieži tiek izmantoti vairāk uzlaboti algoritmi. Tas var būt gan fonētiski algoritmi, piemēram, Soundex (piemēram, Metaphone), gan pilnīgi atšķirīgas pieejas, piemēram, saistītas ar redakcijas attālumu, par kuru mūsu vietnē jau ir publicēts uzdevums.

Literatūra:
1. Yu D. Apresyan. Atlasīti darbi. T. I. // Leksiskā semantika. M .: Krievu kultūras valodas, 1995. gads.
2. Donalds Knuts. Datorprogrammēšanas māksla. Vol.3: šķirošana un meklēšana // Reading (Mass.), 1973.
3. Donalds Knuts. Datorprogrammēšanas māksla. Vol. 3: šķirošana un meklēšana. 2nd ed. // Lasīšana (masa), 1998.
4. Bertrands Lisbaks un Viktorija Meijere. Valodas identitātes atbilstība // Wiesbaden: Springer, 2013.

Šo uzdevumu izmantoja XIII Starptautiskajā lingvistikas olimpiādē 2015.gadā Blagoevgradā (Bulgārijā).


Like this post? Please share to your friends:
Atbildēt

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