ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serguei Tarassov                     2:5020/400     04 Jun 2003  00:50:33
 To : All
 Subject : Ещё о нечетком сравнении строк
 -------------------------------------------------------------------------------- 
 

 Доброго дня!
 
 Задачка всё та же, но применительно к базам данных адресов и названий.
 Функция Левенштайна не подошла по причине необнаружения разницы между
 "United kingdom" и "Kingdom united".
 Вычисление релевантности (алгоритм тут вроде пробегал давно) решает эту
 проблему. Hо возникает другая.
 Поскольку сравнение происходит попарно, то время поиска с ростом количества
 записей в таблице растет, как квадрат этого количесва записей.
 Hапример, если у нас 100 записей в таблице адресов, то нужно сделать 99(для
 первой записи) + 98(для второй) + .. + 1 (для последней) сравнений.
 Т.е. имеем арифметическую прогрессию
 ЧислоСравнений = N / 2 * N
 N - число запсией в таблице.
 
 Какие есть оптимизации на сей счет ?
 Хочется какой-нибудь хеш строить для самих названий, а не для их пар, и
 сравнивать потом эти хэши, поскольку по единожды вычисленным значениями
 можно строить индекс и оптимизатор в СУБД будет его использовать.
 
 --
 Сергей Тарасов
 Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.Mail.Ru (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор