Soundex • Олександр Піперская • Науково-популярні завдання на "Елементи" • Лінгвістика

Soundex

Soundex – це алгоритм для кодування назв. Його створили в 1918-1922 рр. в США Роберт Расселл і Маргарет Кінг Оделл, щоб полегшити пошук схоже звучать прізвищ. В середині XX століття Soundex широко використовувався в США при аналізі результатів переписів населення 1890-1920 рр. Нижче дан приклад картки з даними перепису населення 1910 р Тут ви бачите, що код Soundex для прізвища Wilson виглядає як W425:

завдання

Дан список прізвищ і відповідних їм кодів Soundex в переплутав порядок. Деякі символи пропущені:

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

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

Завдання 1. Опишіть покроково, як генерується код Soundex.

Завдання 2. Встановіть відповідності між прізвищами та кодами Soundex і вставте пропущені символи.

Завдання 3. Побудуйте коди Soundex для наступних прізвищ: Ferguson, Fitzgerald, Hamnett, Keefe, Maxwell, Razey, Shaw, Upfield.


Підказка

Кожен код складається з букви і трьох цифр. Буква повторює першу літеру прізвища, а цифри кодують приголосні, які містяться в цій прізвища далі.


Рішення

Всі коди Soundex складаються з латинської літери і трьох цифр. Неважко здогадатися, чому код для прізвища Wilson починається на W: Тому що це перша буква цього прізвища.

Після того як стало ясно, що перша буква зберігається, завдання розпадається на шість невеликих завдань з переплутаними відповідниками:

Allaway, Anderson, Ashcombe
A536, A251, A400

Chapman, Colquhoun
C42␣, C155

Lewis, Littlejohns
L␣42, L2␣0

Stanmore, Stubbs
S312, S356

Tocher, Tonks
T␣6␣, T520

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

Згадаймо, що Soundex – алгоритм, розроблений для пошуку схоже звучать слів. Ймовірно, цифри повинні кодувати якісь характерні звучання. Можна висунути гіпотезу, що вони відповідають згодним буквах, які зустрічаються в прізвища. Правда, цифр тільки шість – значить, одна і та ж цифра кодує цілі групи приголосних.

Ці групи такі:

bpv (f)cgjkqs (xz)dtlmnr
123456

Класифікація букв в Soundex більш-менш відповідає класифікації звуків по тому, як вони вимовляються: в групу 1 входять приголосні, вимовлені з участю губ; в групу 2 – приголосні, вимовлені за допомогою задньої частини мови, і свистячі; в групу 3 – переднеязичниє смичние (d і t); в групу 5 – носові. Виходячи з цього, можна розподілити по групах і ті букви, які ми не бачили в умови (в таблиці вони дані в дужках). Літера f потрапить в групу 1 до губні згодним (там вже знаходиться v, пара f по глухість-дзвінкості), а x і z – до групи 2 (x складається з k і s, Які знаходяться в групі 2, а z – дзвінка пара до s). букви h і w в цю таблицю не ввійшли: вони при генерації коду Soundex ігноруються. Те ж стосується букви y, Яка в англійській мові вважається гласною.

Можна помітити, що сполученням приголосних з однієї групи відповідає тільки одна цифра в коді. Наприклад, з даних в умови кодів прізвища Kingscott може відповідати тільки ␣5␣3, в якому 5 відповідає за n, 3 – за t, А цифра в середині повинна відповідати за g, s і c (Очевидно, це буде цифра 2).

Нулі в коді відповідають випадкам, коли приголосних не вистачило на те, щоб заповнити три позиції. Наприклад, можна встановити, що Allaway – це A400, де двом l відповідає 4, а a, w, a і y в кодуванні не беруть участь.

Відповідь на завдання 1. Узагальнюючи всі ці спостереження, можна побудувати алгоритм кодування. Важливо звернути увагу на порядок операцій, щоб він дозволив отримати всі коди без помилок.

1. Залишити першу букву незмінною.

2. Видалити h і w.

3. Замінити всі згодні на цифри (букви, найбільш часті читання яких схожі, об'єднуються в групи):

bfpvcgjkqsxzdtlmnr
123456

4. Дві або більше однакових цифр поспіль скоротити до однієї.

5. Видалити всі голосні (a, e, i, o, u, y).

6. Залишити тільки перші три цифри або дописати нулі справа, щоб довжина коду склала одну букву і три цифри.

Відповідь на завдання 2 (Відновлені символи підкреслені).

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.

Відповідь на завдання 3.

Ferguson: F622, Fitzgerald: F326, Hamnett: H530, Keefe: K100, Maxwell: M240, Razey: R200, Shaw: S000, Upfield: U143.


Післямова

Завдання, для вирішення якої використовувався (і часом продовжує використовуватися в наші дні) алгоритм Soundex, в загальному вигляді називається нечітким пошуком (approximate string matching, fuzzy string searching).

Уміння розуміти, що два мовних вираження еквівалентні, – важлива частина володіння людською мовою. Це вміння може проявлятися на різних рівнях. Наприклад, на рівні семантики (значень слів) та синтаксису (зв'язків між словами в словосполученні і пропозиції) носій російської мови легко розуміє, що фрази Стометрову дистанцію він проплив кролем за 45 секунд, На сто метрів кролем у нього пішло 45 секунд і Стометрівку він проплив кролем за ¾ хвилини (Апресян 1995: Додати I, 12) означають одне і те ж. Точно так само і на рівні букв ми легко розуміємо, що Муравйова і Муравйова – це одна і та ж прізвище, а Наталія і Наталя – одне і те ж ім'я (хоча в ситуаціях, коли хочеться причепитися, ми можемо удавано говорити щось на кшталт "Ну як же, тут написано Наталія Муравйова, А у вас в паспорті – Наталія Муравйова").Але автоматизувати таке базове для нас вміння – розуміти еквівалентність не збігаються точно слів і виразів – завдання дуже складне.

Такі розбіжності на практиці зустрічаються регулярно. Soundex спочатку придумувався саме для зіставлення назв, оскільки на початку XX століття варіативність в написанні власних назв була набагато вище, ніж зараз, – але і зараз вона не зовсім зведена до нуля. Так, в книзі (Lisbach, Meyer 2013: 15) наводиться приклад двох варіантів запису інформації про одне й те ж людину – наприклад, зі слуху в колл-центрі і при переписуванні з документів з поділом на поля:

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

Важливе значення Soundex, яке багато в чому і забезпечило його популярність, – легкість в реалізації: зокрема, для цього алгоритму не потрібен словник. Soundex згадується в класичному посібнику "Мистецтво програмування" Дональда Кнута (Knuth 1998: Додати 395-396). Правда, в першому виданні (Knuth 1973: 391-392) автор ще не врахував всі тонкощі і пропонував одночасно викидати голосні, h і w; тоді, наприклад, Chapman дає НЕ Chapman → Capman → Ca15a5 → C155, а Chapman → Cpmn → C155 → C15 → C150.

Soundex реалізований в десятках мов програмування. Наприклад, вбудована функція SOUNDEX є в системі управління базами даних MySQL.А на Python 3 можна записати весь зміст цього завдання в декількох рядках (автор коду – Іван Держанскій):

Недоліки Soundex лежать на поверхні. Іноді цей алгоритм нездатний виявити схожість між дуже близькими прізвищами: наприклад, Levinson отримає код L152, а Lewinson – код L525. Крім того, Soundex погано працює в ситуаціях, коли вимова сильно розходиться з написанням, що в англійській мові буває нерідко. Наприклад, шотландська прізвище Colquhoun, Дана в умови, читається приблизно як Кехун, А його код Soundex C425 відображає невимовні l (4) і q (2). Інший варіант цього прізвища – Colhoun (Згадаємо капітана Касія Колхауна з "Вершника без голови" Майн Ріда) – має інший код: вийде C450. Втім, в такому написанні зазвичай вимовляється л (Колхуна), Так що різні коди в даному випадку – це не так вже й погано.

Для вирішення завдання нечіткого пошуку нерідко використовуються і більш просунуті алгоритми. Це можуть бути як фонетичні алгоритми зразок Soundex (наприклад, Metaphone), так і зовсім інші підходи – наприклад, пов'язані з редакційним відстанню, завдання про яке вже публікувалася на нашому сайті.

література:
1. Ю. Д. Апресян. Вибрані праці. Т. I. // Лексична семантика. М .: Мови російської культури, 1995.
2. Donald Knuth. The art of computer programming. Vol.3: Sorting and searching // Reading (Mass.), 1973.
3. Donald Knuth. The art of computer programming. Vol. 3: Sorting and searching. 2nd ed. // Reading (Mass.), 1998..
4. Bertrand Lisbach & Victoria Meyer. Linguistic identity matching // Wiesbaden: Springer, 2013.

Завдання використовувалася на XIII Міжнародній олімпіаді з лінгвістики в 2015 році в Благоєвграді (Болгарія).


Like this post? Please share to your friends:
Залишити відповідь

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