Алгоритми зіставлення для імпорту

Під час імпорту даних дуже часто виникають невеликі розбіжності між іменами, географічними назвами та іншими довідковими даними.

ActivityInfo розроблено для автоматичного зіставлення довідкових даних на основі набору правил, які враховують поширені розбіжності в іменах, що виникають через відмінності в транслітерації та написанні.

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

Зіставлення латинських назв

Алгоритм оцінки латинських назв (Latin Name scorer) допомагає ідентифікувати пари географічних назв, написаних латиницею, які, ймовірно, є однаковими, але по-різному транслітеровані.

Ці відмінності можуть виникати внаслідок низки випадкових процесів:

  1. Один і той самий звук може бути написаний по-різному, можливо, через іншу схему транслітерації, наприклад:

    • [ou]adi ⇒ [w]adi
    • zou[q] bha[nn]ine ⇒ zou[k] bha[n]ine
    • z[ai]toun ⇒ z[ei]toun[e]

  2. Звуки можуть змінюватися регіонально та з часом, і ці відмінності призводять до нового написання.

  3. Назви, що включають в себе частини мови, можуть бути переставлені або довільно відкинуті:

    • "Santa Rosa City" ⇒ "City of Santa Rosa"
    • "Commune de Goumera" ⇒ "Goumera"

  4. Слова можуть бути розділені або об'єднані

    • "Bara Sara" ⇒ "Barassara"
    • "Nema Badenyakafo" ⇒ "Nema Badenya Kafo"

Щоб бути корисними при зіставленні великих наборів даних, нам потрібен низький рівень хибнопозитивних спрацьовувань, інакше аналітики будуть перевантажені сотнями або тисячами непотрібних збігів для перевірки.

Традиційні метрики редакційної відстані, такі як відстань Левенштейна або схожість Джаро-Вінклера, як правило, дають занадто багато хибнопозитивних результатів. Наприклад, рядки AAIN та ZEBDINE мають схожість за Джаро-Вінклером 0.60, незважаючи на те, що немає жодних шансів, що ZEBDINE є альтернативним написанням AAIN.

Натомість, алгоритм оцінки латинських назв (Latin Name Scorer) в ActivityInfo розглядає ймовірність того, що AAIN може бути перетворено на ZEBDINE за допомогою перелічених вище процесів. Оскільки ми вважаємо додавання приголосних, таких як Z, B, D, вкрай малоймовірним, алгоритм оцінки повертає значення нуль.

З іншого боку, рядок AIN відрізняється лише однією голосною, що є дуже поширеною відмінністю в транслітерації, і це дає оцінку 0.925.

Алгоритм

Алгоритм зіставлення латинських назв в ActivityInfo працює наступним чином:

Спочатку кожен вхідний рядок переводиться у верхній регістр і з нього видаляються всі діакритичні знаки, включаючи апострофи, якщо вони знаходяться між літерами. Наприклад:

Далі кожен вхідний рядок розбивається на одну або кілька «частин». Всі символи, такі як «-», «/», «(» і т.д., вважаються початком нових частин, а цифри починають нову частину, якщо їм передують символи. Наприклад:

Маючи два вхідні рядки, кожен з яких розбитий на масив частин, наприклад, [COMMUNE, DE, GOUMERA] та [GOUMERA, COMUNE], ми обчислюємо показник схожості для кожної пари частин зліва та справа:

| | COMMUNE | DE | GOUMERA ||--------|--------:|---------:|:---------:||GOUMERA | 0.0 | 0.00 | 1.0 | |COMUNE |0.93 | 0.00 | 0.0 |

«Ліва» та «права» назви обираються таким чином, щоб «ліва» назва мала менше або однакову кількість частин, ніж «права».

Показник схожості між двома частинами обчислюється залежно від типу частин:

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

Нарешті, ми обчислюємо показник від 0 до 1, який вказує, наскільки добре збігаються дві назви. Зокрема:

Ми визначаємо чисельник як суму довжин усіх відповідних частин, зважену за їхніми показниками схожості. У наведеному вище прикладі «COMMUNE» найкраще відповідає «COMUNE» зі схожістю 0.93. Ми використовуємо мінімальну довжину двох частин, яка в цьому випадку становить 6 символів, зважену на 0.93, що дає 5.58 до чисельника.

«GOUMERA» точно відповідає «GOUMERA», тому додає 6 * 1.0 до чисельника.

Знаменник включає в себе довжини відповідних частин (6 + 6), а також невідповідної частини «DE» (2).

Алгоритм фонетичної схожості

При обчисленні схожості двох буквених частин використовується алгоритм відстані між латинськими словами (Latin Word Distance) ActivityInfo для обчислення відстані між двома частинами, які вважаються словами, написаними латиницею.

Подібно до алгоритму Левенштейна, ми обчислюємо мінімальну кількість «редагувань» — замін, вставок і видалень — але замість того, щоб однаково трактувати кожну різницю в символах, кожному «редагуванню» присвоюється вартість, що базується на ймовірності того, що вона виникла внаслідок різниці в транслітерації.

Наприклад, голосні часто транслітеруються по-різному, тому зайвим голосним або заміні голосних присвоюється відносно низька вартість. Наприклад, у випадку MREISSE та MRAISSE заміні E на A присвоюється вартість 0.25.

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

Деякі заміни приголосних є поширеними, включаючи M → N та K → Q, і їм присвоюється вартість 0.5 та 0.25 відповідно.

Додаткові правила були розроблені на основі наборів даних, що зустрічалися в Афганістані, Лівані, Малі та на Філіппінах.