Имаме следната задача: Table1 съдържа имена на клиентите на най-голямата квартална бакалия в Мюнхен, а Table2 съдържа феновете на Байерн Мюнхен. Пита се колко от феновете на Байерн пазаруват в бакалията.
Да предположим, че данните са First Name (FNAME), Last Name (LNAME), CITY, COUNTRY.
Най-елементарното решение е следното:
select *
from table2 t2
where exists (select 1
from table1 t1
where t1.fname = t2.fname
and t1.lname = t2.lname
and t1.city = t2.city
and t1.country = t2.country)
Това ще ни даде резултат ако всички имена са написани по паспорт. Но както всички знаем, данните не винаги са така чисти. Примерно господин Schmitt от феновете може да е записан в бакалията като Schmidt; госпожица Pavlovich може да е Pavlovic; John Smith не съвпада с John Smit и т.н. Абе трябва нещо по-добро.
Има една функция, което се опитва да оцени звуковото съответствие (работи само за латиница!) и това е soundex. Начина и на действие е относително прост и е описан тук. Да видим какво става с нея:
select *
from table2 t2
where exists (select 1
from table1 t1
where soundex(t1.fname) = soundex(t2.fname)
and soundex(t1.lname) = soundex(t2.lname)
and t1.city = t2.city
and t1.country = t2.country)
(за простота, или от простотия, приемам че държавите и градовете са написани еднакво. Иначе може да се приложи същата трансформация)
Опа… излязоха твърде много резултати. За мен няма нищо общо между Marko Mjagkov и Marica Moisejevs, но на soundex му звучат еднакво – M620 M221. Да опитаме нещо друго
Има едни красив, относително нов пакет, известен като utl_match. В този пакет има реализирани 2 алгоритъма, разработени за борба с точно такъв проблем – сравняване на имена. Единият е измислен от руския математик Владимир Левенщайн през далечната 1965 (функцията EDIT_DISTANCE), а другия комай е с американски произход, резултат от дългогодишния труд на господата Matthew Jaro и William Winkler, публикуван през 1990. Колкото и да бях добър с математиката като ученик и студент, сега съм забравил всичко и математическия апарат ми е твърде сложен; но пък мога да използвам функциите наготово и без да му мисля много, да проверя колко са „близки“ имената:
select *
from table2 t2
where exists (select 1
from table1 t1
where utl_match.jaro_winkler(t1.fname, t2.fname) > 0.9
and utl_match.jaro_winkler(t1.lname, t2.lname) > 0.9
and t1.city = t2.city
and t1.country = t2.country)
Тук, обаче, достигам до друг проблем – няма ефективен начин а ускоря заявката. Ако бакалията има 10 000 клиенти от Мюнхен, а Байерн има 500 000 фена в родния си град, то имаме реален шанс да изпълним функцията utl_match.jaro_winkler над 5 000 000 000 пъти. При това ще сравнява, примерно, Адолф с Грета – нищо общо. Никакви индекси или оптимизации не помагат, просто груба сила. Това си отнема доста (процесорно) време.
И така, за нуждите на моето изследване аз достигнах до следното комбинирано решение
select *
from table2 t2
where exists (select 1
from table1 t1
where soundex(t1.fname) = soundex(t2.fname)
and soundex(t1.lname) = soundex(t2.lname)
and utl_match.jaro_winkler(t1.fname, t2.fname) > 0.9
and utl_match.jaro_winkler(t1.lname, t2.lname) > 0.9
and t1.city = t2.city
and t1.country = t2.country)
Тук със soundex сравнението орязвам значително проверките, макар и да имаме доста false positives. За по-извратени случаи може да направим функционален индекс по soundex.
После с utl_match.jaro_winkler намирам най-вероятните съвпадения от вече намаления набор. Вярвате или не, това върви доста добре – при таблици с 20К и 2M реда (всичките от един град), минава за десетки секунди и дава доста смислени резултати. Разбира се, доста от съвпаденията може да са случайни – не само един мюнхенец се казва Ханс Шмит. Но все пак е някакво начало.
P.S. По време на research-а попаднахме на многообещаващия Петьо. Отказахме се от него, защото иска extproc, а ние избягваме този механизъм защото може да отвори дупка в сигурността. Иначе изглежда прекрасно
