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
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.
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).