2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Soundex algoritmas

Taškai: 12

Soundex algoritmas skirtas atpažinti angliškus vardus pagal skambesį ir juos indeksuoti. Kiekvienam vardui generuojamas 4 skaitmenų kodas pagal šias taisykles:

1. Palikti pirmąją žodžio raidę.
2. Pašalinti visas šias raides: A, E, I, O, U, H, W, Y.
3. Likusias raides pakeisti skaitmenimis iš lentelės:

Raidės

Skaitmenys

B, F, P, V

1

C, G, J, K, Q, S, X, Z

2

D,T

3

L

4

M, N

5

R

6

4. Du ar daugiau iš eilės einančius tuos pačius skaitmenis pakeisti vienu tuo pačiu skaitmeniu.
5. Imti tik pirmuosius keturis žodžio simbolius; jei žodis trumpesnis, pabaigoje pridėti nulių.

Pavyzdys:

Žodis

Kodas

BOB

B100

BEAVER

B160

HEILBRONN

H416

ESSAY

E200

 

Koks kodas būtų sugeneruotas vardui HILBERT?

A. H410

B. B540

C. H041

D. H416

Paaiškinimas

Algoritmas žinomas Soundex vardu.

Soundex algoritmas naudojamas vardų paieškai pritaikant tarimą anglų kalba. Algoritmas daug dėmesio skiria fonetinių klaidų korekcijai: klaidoms, atsirandančioms rašant vardų sekas, ypač kai yra panašiai tariamų žodžių. Algoritmą naudoja įvairios tarptautinės institucijos (pavyzdžiui, Interpolas), tačiau kai kurių šalių vardams netinka.

https://en.wikipedia.org/wiki/Soundex

Algoritmas išpopuliarėjo, kai jį aprašė Donaldas Knuthas savo knygoje "The Art Of Computer Programming, vol. 3: Sorting And Searching".

Raktiniai žodžiai: algoritmas, klaidos.

Atsakymas

Teisingas atsakymas: D.

1. Paliekama pirmoji žodžio raidė (H).

2. Hilbert → H4163 (pritaikius pirmąsias tris taisykles).

3. H416 (paliekami tik pirmieji keturi simboliai).