Soundex • Alexander Piperski • Videnskabeligt populære problemer på "Elements" • Lingvistik

Soundex

Soundex er en algoritme til kodning af rigtige navne. Det blev oprettet i 1918-1922. i USA, Robert Russell og Margaret King Odell, for at lette søgen efter lignende lydende efternavne. I midten af ​​det 20. århundrede blev Soundex bredt anvendt i USA ved at analysere resultaterne af censuses af befolkningen i 1890-1920. Nedenfor er et eksempel på et 1910 folketællingskort. Her kan du se, at Soundex-koden for efternavnet Wilson ligner W425:

opgave

En fortegnelse over efternavne og deres tilhørende Soundex koder gives i forvirret rækkefølge. Nogle tegn mangler:

Allaway, Anderson, Ashcombe, Buckingham, Chapman, Colquhoun, Evans, Fairwright, Kingscott, Lewis, Littlejohns, Stanmore, Stubbs, Tocher, Tonks, Whytehead

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

Opgave 1. Beskriv trin for trin hvordan Soundex-koden genereres.

Opgave 2. Match navnene og koderne for Soundex og indsæt de manglende tegn.

Opgave 3. Bygg Soundex koder for følgende efternavne: Ferguson, Fitzgerald, hamnett, Keefe, Maxwell, Razey, Shaw, ad banen.


hjælpe

Hver kode består af et bogstav og tre tal. Brevet gentager første bogstav i efternavnet, og tallene koder de konsonanter, der er i det næste navn.


beslutning

Alle koder Soundex består af et latinsk bogstav og tre cifre. Det er ikke svært at gætte hvorfor koden for efternavnet Wilson starter på W: fordi det er første bogstav i dette efternavn.

Efter at det var klart, at første bogstav bevares, opdeles opgaven i seks små opgaver med forvirrede korrespondancer:

Allaway, Anderson, Ashcombe
A536, A251, A400

Chapman, Colquhoun
C42, C155

Lewis, Littlejohns
L42, L220

Stanmore, Stubbs
S312, S356

Tocher, Tonks
T␣6␣, T520

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

Husk at Soundex er en algoritme designet til at finde lignende lydende ord. Sandsynligvis skal tallene kode for en karakteristisk lyd. Det er muligt at antage at de svarer til konsonantbreve, der findes i efternavnet. Sandt nok betyder kun seks cifre, at det samme ciffer koder for hele grupper af konsonanter.

Disse grupper er:

bpv (f)cgjkqs (xz)dtlmnr
123456

Klassificeringen af ​​bogstaver i Soundex svarer mere eller mindre til klassificeringen af ​​lyde alt efter hvordan de udtales: gruppe 1 indeholder konsonanter udtalt med læbernes deltagelse; i gruppe 2 udtales konsonanter ved hjælp af ryggen af ​​tungen og fløjter; gruppe 3 – flersproget okklusal (d og t); i gruppe 5 – nasal. Ud fra dette er det muligt at distribuere i grupper og de breve, som vi ikke så i betingelsen (i tabellen er de angivet i parentes). brev f vil falde i gruppe 1 til labialkonsonanterne (der er allerede vet par f døvhed-voiced), og x og z – i gruppe 2 (x består af k og ssom er i gruppe 2, men z – ringepar til s). breve h og w Denne tabel er ikke inkluderet: de ignoreres, når der genereres Soundex-kode. Det samme gælder for brevet. ysom på engelsk betragtes som en vokal.

Du kan bemærke, at kombinationerne af konsonanter fra en gruppe kun svarer til et ciffer i koden. For eksempel fra data i efternavnet koder tilstand Kingscott kan kun matche ␣5␣3, hvor 5 er ansvarlig for n, 3 – for tog tallet i midten skal være ansvarlig for g, s og c (det vil naturligvis være nummer 2).

Nulerne i koden svarer til de tilfælde, hvor konsonanterne ikke var nok til at fylde tre positioner. For eksempel kan du indstille det Allaway – Det er A400, hvor to l svarer til 4 og en, w, en og y deltager ikke i kodning.

Svaret på opgaven 1. Sammenfatning af alle disse observationer, vi kan konstruere en kodningsalgoritme. Det er vigtigt at være opmærksom på rækkefølgen af ​​operationer, så den tillader at modtage alle koder uden fejl.

1. Lad det første bogstav være uændret.

2. Slet h og w.

3. Udskift alle konsonanter med tal (bogstaver, hvis hyppigste aflæsninger er ens, kombineres i grupper):

bfpvcgjkqsxzdtlmnr
123456

4. To eller flere identiske tal i træk for at reducere til en.

5. Fjern alle vokaler (en, e, jeg, o, u, y).

6. Lad kun de første tre cifre eller tilføj nuller til højre, så kode længden er et bogstav og tre cifre.

Svar til opgave 2 (genoprettede tegn er understreget).

Allaway: A400, Anderson: 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, Whytehead: W330.

Svaret på opgaven 3.

Ferguson: F622, Fitzgerald: F326, hamnett: H530, Keefe: K100, Maxwell: M240, Razey: R200, Shaw: S000, ad banen: U143.


efterskrift

Opgaven, som Soundex-algoritmen blev brugt til (og nogle gange fortsætter med at blive brugt i dag) kaldes i almindelighed fuzzy string-søgning (omtrentlig string matching, fuzzy string search).

Evnen til at forstå, at to sprogudtryk er ækvivalente, er en vigtig del af at kende det menneskelige sprog. Denne færdighed kan manifestere sig på forskellige niveauer. For eksempel forstår en russisk taler på niveau med semantik (ordbetydninger) og syntaks (forbindelser mellem ord i en sætning og en sætning), at sætningerne En hundrede meter afstand svømmede han i en kryb i 45 sekunder, I hundrede meter tog gennemsøgningen ham 45 sekunder. og Han floated hulen i ¾ minut (Apresyan 1995: I, 12) betyder det samme. På samme måde forstår vi det lettere på bogstavniveau Muravyova og Muravyev – Det er samme efternavn, men Natalia og Natalia – Det samme navn (selvom i situationer hvor jeg vil finde fejl, kan vi fejlagtigt sige noget som: "Nå siger det selvfølgelig Natalia Muravyova, og du har et pas – Natalia Muravyova").Men at automatisere en sådan grundlæggende evne til at forstå ækvivalensen mellem ord og udtryk, der ikke passer perfekt sammen, er en meget vanskelig opgave.

Sådanne uoverensstemmelser forekommer jævnligt. Soundex blev oprindeligt opfundet netop til sammenligning af egne navne, da i begyndelsen af ​​det 20. århundrede var variationen i stavningen af ​​de rigtige navne meget højere end nu, men selv nu er den ikke helt reduceret til nul. Således indeholder bogen (Lisbach, Meyer 2013: 15) et eksempel på to muligheder for registrering af oplysninger om den samme person – f.eks. Fra en høring i et callcenter og ved omskrivning fra dokumenter med opdeling i felter:

Kate Suzanne Jankowiz
Belrive Str. 20, 65920 Frankfurt am Main (Tyskland)
CatherineSusanJenniferYankovits-Brunner
20BellerivestrasseFrankfurt / M65920DE

En vigtig fordel ved Soundex, som på mange måder sikrede sin popularitet, er let implementering: især en ordbog er ikke nødvendig for denne algoritme. Soundex er nævnt i Donald Knuths klassiske "The Art of Programming" (Knuth 1998: 395-396). Men i den første udgave (Knuth 1973: 391-392) har forfatteren endnu ikke taget højde for alle de finesser og foreslog samtidig at smide vokalerne ud, h og w; så for eksempel Chapman giver nej Chapman → Capman → Ca15a5 → C155 og Chapman → Cpmn → C155 → C15 → C150.

Soundex er implementeret i snesevis af programmeringssprog. For eksempel er den indbyggede SOUNDEX-funktion i MySQL database management system.Og i Python 3 kan du optage hele indholdet af denne opgave i flere linjer (forfatteren af ​​koden er Ivan Derzhansky):

Ulemper Soundex ligger på overfladen. Nogle gange er denne algoritme ikke i stand til at opdage ligheder mellem meget tætte efternavne: for eksempel, Levinson vil modtage koden L152, og Lewinson – kode L525 Desuden fungerer Soundex ikke godt i situationer, hvor udtalen er meget forskellig fra stavningen, som ofte sker på engelsk. For eksempel, skotsk efternavn Colquhoungivet i en tilstand læses noget som Kehun, og dens Soundex C425 kode afspejler det uprøvede l (4) og q (2). En anden variant af dette efternavn er Colhoun (husk kaptajn Cassius Kolhoun fra "Headless Rytter" Mine Reed) – har en anden kode: det viser sig at være C450. Imidlertid er en sådan stavning normalt udtalt l (Kolhun), så forskellige koder i dette tilfælde ikke er så dårlige.

For at løse problemet med fuzzy search bruges mere avancerede algoritmer ofte. Det kan være både fonetiske algoritmer som Soundex (for eksempel Metaphone) og helt forskellige tilgange – for eksempel relateret til redaktionel afstand, en opgave, som allerede er publiceret på vores hjemmeside.

Referencer:
1. Yu. D. Apresyan. Udvalgte værker. T. I. // Lexisk semantik. M.: Sprog af russisk kultur, 1995.
2. Donald Knuth. Kendskab til computer programmering. Vol.3: Sortering og søgning // Reading (Mass.), 1973.
3. Donald Knuth. Kendskab til computer programmering. Vol. 3: Sortering og søgning. 2nd red. // Reading (Mass.), 1998.
4. Bertrand Lisbach & Victoria Meyer. Sproglig identitet matchning // Wiesbaden: Springer, 2013.

Opgaven blev brugt på XIII International Olympiad i Lingvistik i 2015 i Blagoevgrad (Bulgarien).


Like this post? Please share to your friends:
Skriv et svar

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