http___blog.yavor.info__m_20111223_1.xml
http___blog.yavor.info__m_201112_lang_en.xml
1.1 1.2 2.1 3.1 4.1 5.1 5.2 5.3 5.4 6.1 7.1 7.2 7.3 8.1 9.1 9.2 10.1 10.2 10.3 11.1 11.2 11.3 11.4 12.1 13.1 13.2 13.3 13.4 13.5 14.1 15.1 16.1 17.1 17.2 18.1 18.2 18.3 18.4 19.1 19.2 19.3
Имаме следната задача: 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 реда (всичките от един град), минава за десетки секунди и дава доста смислени резултати. Разбира се, доста от съвпаденията може да са случайни – не само един мюнхенец се казва Ханс Шмит. Но все пак е някакво начало. По време на research-а попаднахме на многообещаващия Петьо. Отказахме се от него, защото иска extproc, а ние избягваме този механизъм защото може да отвори дупка в сигурността. Иначе изглежда прекрасно
1.1 1.2 2.1 3.1 4.1 5.1 5.2 5.3 5.4 6.1 6.2 7.1 7.2 7.3 8.1 9.1 9.2 10.1 10.2 10.3 11.1 11.2 11.3 11.4 11.5 12.1 13.1 13.2 13.3 13.4 13.5 14.1 15.1 16.1 17.1 17.2 18.1 19.1 19.2 19.3 19.4 20.1 20.2 20.3
We have the following task: Table1 contains the clients of the biggest grocery store in Munich, and Table2 all the fans of Bayern (Munich). The question is how many Bayern fans visit the grocery. Let’s assume we have the columns First Name (FNAME), Last Name (LNAME), CITY, COUNTRY. The easiest solution is: 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) But this will give us the result if all names are written correctly. Which, unfortunately, happens rarely. For example Mr. Schmitt from the fans may be written as Schmidt in the grocery; Mrs Pavlovich may be Pavlovic; John Smith is not the same as John Smit, etc. We need something better. There is one SQL function which returns a character string containing the phonetic representation a string. The function is soundex. The algorithm behind it is relatively simple and can be found here. Let’s try it: 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) (to make the things simple, i have assumed the CITY and COUNTRY are written fine. We can use the same transformation on them) But this gives us too many false positives. I do not think Marko Mjagkov is the same as Marica Moisejevs, but soundex returns the same – M620 M221. We need something else There is one nice, relatively new package, named utl_match. In this package there are functions using two different algorithms facing this problem. The first one is developed in Russia by Vladimir Levenshtein in 1965 (the function EDIT_DISTANCE). The other seems to be developed in US, by Matthew Jaro and William Winkler, published in 1990. Let’s see what we can do using the latter: 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) Hm, we have another problem – there is no effective way to speedup the query. If the grocery has 10 000 clients in Munich, and the football cub has 500 000 fans in the city, we will execute the function utl_match.jaro_winkler more than 5 000 000 000 times. It will, for example, try to compare Adolf with Gretta, which is nonsense. One cannot index this, or use another infrastructure tricks – only raw computing power will help. So it takes time. And so, I decided to combine both approaches and came up with this: 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) Here soundex limits the number of checks, although there may be many false positives. One can even do a function-based index on Soundex, or a MView. Then utl_match.jaro_winkler gives us the most “similar” names. Believe it or not, this works fine – on tables with 20K and 2M rows (all from the same city), it completed in tens of seconds and returns mostly reasonable results. Of course, there may be many coincidences – there are many men in Munich named Hans Shmidt. But it is useful. P.S. During the research we encountered PETER. We did not test it because it requires using extproc, which can potentially lead to security problem. But the product looks very promising.