Комментарии 17
Он медленее существующих поисковых движков (0,4 секунды против 0,09)
не знаком с R, но немного пишу на C# и там LINQ (SQL подобная семантика) весьма медленная, при очень простом и быстром написании сложных многоуровневых команд. Нет ли в вашем случае такой же проблемы?
LINQ - весьма быстр. Быстрее циклов и так далее. А еще есть Parallel LINQ. Просто, как и SQL, его надо "уметь готовить". На SQL можно SELECT FROM SELECT FROM SELECT... И удивляться, что-ж оно так медленно. Так и LINQ - нужно понимать и экспериментировать, что куда и как.
Я соглашусь с тем что инструментом нужно уметь пользоваться, но абсолютно не согласен что LINQ быстрый. Если например почитать статьи или StackOverflow, то про низкую производительность говорят регулярно. Я в своей статье эту тему затрагивал.
Интересная задачка. Сам с подобной сейчас работаю. Но у меня все хуже - нужно сравнить два массива адресов и найти совпадения. Массивы достаточно большие - в пределе порядка 250млн в одном и порядка 1млн в другом (это верхние оценки).
Причем совпадение считается, например,
РОССИЙСКАЯ ФЕДЕРАЦИЯ, Г. САНКТ-ПЕТЕРБУРГ, УЛ. ВАСИ АЛЕКСЕЕВА, Д. 26, ЛИТ. А, ПОМ. 2Ни
Д. 26, УЛ. АЛЕКСЕЕВА ВАСИ, Г. САНКТ-ПЕТЕРБУРГГде один из адресов неполный и порядок слов не сопадает.
Первое что делаем - нормализуем адрес.
РОССИЙСКАЯ ФЕДЕРАЦИЯ, Г. САНКТ-ПЕТЕРБУРГ, УЛ. ВАСИ АЛЕКСЕЕВА, Д. 26, ЛИТ. А, ПОМ. 2НВ нормализованном виде выглядит
САНКТ ПЕТЕРБУРГ ВАСИ АЛЕКСЕЕВА 26 ЛИТ ПОМ 2НДалее разбиваем адрес на элементы (слова) и составляем из него набор уникальных элементов.
Совпадение двух адресов - когда все уникальные элементы меньшего (с меньшим количеством элементов) набора входят в больший набор.
Т.е. остается только взять тот набор, где элементов меньше и проверить чтобы все его элементы присутствовали во втором наборе, где элементов больше или равно.
В принципе, когда все адреса лежат в БД, можно держать "витрину" адресов (где адреса представлены наборами элементов) и тогда задача решается одним SQL запросом.
А что произойдет, если с одной стороны будет "..., дом 6, квартира 10", а с другой "..., дом 10, квартира 6"?
Также решал задачу слияния справочника по лекарствам от разных аптек. Нормализуем до символов и цифр, удаляем остальное, удаляем пробелы, разбиваем на чанки по 3 символа, с возвратом на один, т.е. получаем набор из символов [0-2],[2-4],[4-6] и т.д., делаем хэши чанков и пишем в бд. При поиске аналога делает также, и ищем получившиеся хэши, немного магии сортировки и получаем аналог с приемлемой точностью. Делал 8 лет назад, уже подробности не помню.
Увы, но "приемлемая точность" тут не годится. Речь идет о формировании стоплистов для контроля платежей а основе совпадений адресов клиентов и адресов разного рода злодеев из списков росфинмониторинга.
Хеши тут излишни - в витринах хранятся элементы. Дальше просто - есть набор элементов адреса клиента и количество уникальных элементов в нем. Аналогично для субъекта списка росфина.
А дальше скулем просто пары выбираем тех, у кого количество пересечений по уникальным элементам равно или количеству элементов адреса клиента, или количество элементов адреса субъекта.
если массив адресов, в котором ищем, преобразовать в дерево Города - Улицы города - Дома на улице - Квартиры в доме, то скорость поиска будет логарифмичекской, причём с основанием не 2, как у бинарного дерева, а с размером вложенных массивов. Соответственно проверяемые адреса тоже имеет смысл нормализовывать не в строки, а в кортежи Город Улица Дом Квартира.
В теории все верно. Но есть проблема реализации всего этого на практике.
Да, на стороне клиентов есть т.н. "структурированные адреса". Там действительно все разбито на поля - страна, регион, населенный пункт, район и т.п. Правда, там сложнее все с адресами. Населенный пункт может быть не просто город, а поселок с черте города (нп. г.Екатеринбург, пос.Медный). А улицы вообще может не быть.... Например, вполне реальный адрес - "Тюменская область, г.Тобольск, микрорайон 7А д.5Д"
Но проблема в том, что много адресов не структурированы (и там совершенно не обязательно будет идти строго в порядке регион-населенный пункт-улица-дом-квартира, там ччто угодно и как угодно может быть - как д.10, кв.5, дат и 10-5, например...). Т.е. просто строка. Как их разбирать? Руками? Кто это будет делать? При этом любой адрес может быть не полным...
И проблема тут не столько в сравнении двух адресов - это как раз быстро. Проблема в том, что в БД лежит с одной стороны 250млн адресов, а с другой еще 1млн. И нужно за осмысленное время сравнить все со всеми. И не просто "вроде бы похоже...", а "этот совпал, тот не совпал".
Т.е. проблемы в объемах. И реализации быстрого поиска совпадений. Пока что удалось добиться - на тестовом юните 17тыс с одной стороны, 18тыс с другой находит чуть менее 11тыс совпадений (это тестовые данные) за 277сек при параллельной обработке в 5 потоков. Быстрее пока не получается никак...
Но это с "витринами", где адреса уже разложены по элементам и можно SQL запросом сразу искать пересечения по элементам.
Выбранное вами расстояние не нормализовано - это очень не удобно в использовании, так как по значению не понятна степень различия. При перестановке слов получается большое различие, хотя для человека, очевидно, различие минимально. Кроме того, точное вычисление этого расстояния довольно дорогое удовольствие.
Гляньте лучше расстояние Карловского, где сначала для каждого текста в отдельности строится профиль (вектор в пространстве триплетов), который можно кешировать, а потом от них просто берётся нормализованная манхеттенская норма.
На ваших примерах это даёт следующую картину:
Эски сары ~ Эски сары кёл = 0.18181818181818182
Эски сары ~ Хасаутская = 1
Эски сары ~ Нартов = 1
Эски сары ~ Новый Карачай = 1
Эски сары ~ Мара-Аягъы = 0.8947368421052632
Эски сары ~ Кавказская = 1
Нарты ~ Эски сары кёл = 1
Нарты ~ Хасаутская = 1
Нарты ~ Нартов = 0.2727272727272727
Нарты ~ Новый Карачай = 0.8888888888888888
Нарты ~ Мара-Аягъы = 0.8666666666666667
Нарты ~ Кавказская = 1Обратите внимание, что полностью различные тексты - это именно полностью различные, без градации по степени непохожести.
Ой, опять $mol рекламирую. По жопе мне.
В clickhouse для этого есть всякие готовые ngramDistance*(). Неплохо работает для приведенных примеров (даже явно получше, чем в статье для Нарт). Оно смотрит процент совпадающих последовательностей байт в строках - можно это реализовать на удобном вам языке.
Hidden text
with
['Эски сары', 'Нарты']
as queries,
['Эски сары кёл', 'Хасаутская', 'Нартов', 'Новый Карачай', 'Мара-Аягъы', 'Кавказская']
as target_vector
select
arrayJoin(queries) as query,
arrayJoin(target_vector) as target,
ngramDistance(query, target) as similarity1,
ngramDistanceCaseInsensitiveUTF8(query, target) as similarity2
order by query, similarity2, similarity1
format PrettyCompactMonoBlock
;
+-query-----+-target--------+-similarity1-+-similarity2-+
1. | Нарты | Нартов | 0.375 | 0.42857143 |
2. | Нарты | Эски сары кёл | 0.85714287 | 1 |
3. | Нарты | Мара-Аягъы | 0.9130435 | 1 |
4. | Нарты | Новый Карачай | 0.9310345 | 1 |
5. | Нарты | Хасаутская | 1 | 1 |
6. | Нарты | Кавказская | 1 | 1 |
7. | Эски сары | Эски сары кёл | 0.2 | 0.22222222 |
8. | Эски сары | Хасаутская | 0.7419355 | 1 |
9. | Эски сары | Нартов | 0.82608694 | 1 |
10. | Эски сары | Кавказская | 0.87096775 | 1 |
11. | Эски сары | Мара-Аягъы | 0.93333334 | 1 |
12. | Эски сары | Новый Карачай | 0.9444444 | 1 |
+-----------+---------------+-------------+-------------+https://fiddle.clickhouse.com/466ee362-dbff-4161-9553-ae6abcd565ec
Спасибо, интересный результат выдаёт
На R делал "процент совпадающих последовательностей байт в строках", но у меня результат был хуже в поиске. Возможно в кликхаусе прокаченнее функция, изучу
Специфика адресов и имен/наименований в том, что там нельзя сравнивать последовательности байт. Сравнение должно идти по наборам слов (элементов). И с учетом полный/неполный. Для имен то же самое:
ИВАНОВ ИВАН ИВАНОВИЧи
ИВАН ИВАНОВсчитаются совпадением т.к все уникальные элементы более коротого набора
ИВАН
ИВАНОВвходят в более длинный
ИВАН
ИВАНОВ
ИВАНОВИЧАналогично и для адресов.
Т.е. на самом деле там очень простой алгоритм:
Нормализуем строки (приведение к одному регистру, удаление лишних символов, возможно, исключение каких-то "лишних" слов и т.п.
Разбиваем строки на слова (элементы) и заносим в наборы с уникализацией (все элементы в наборе уникальны)
Выбираем набор с меньшим количеством элементов (если количество элементов набора равное - любой набор).
Проходим поэлементно по выбранному набору и проверяем каждый элемент на присутствие во втором наборе.
Если все элементы меньшего набора присутствуют в большем - есть совпадение.
Вот как-то так.
В первом же абзаце статьи: "Главный критерий - нахождение адреса, если написано с ошибками или не дописан он в полной мере." Чуть опечатался и всё, разбиение на слова и точная проверка ломаются сразу. Ну и выше вам показывали про дом с квартирой. Тоже самое с улицей и населенным пунктом может быть.
ИВАНОВ ИВАН ИВАНОВИЧ
и
ИВАН ИВАНОВ
считаются совпадением т.к все уникальные элементы более коротого набора
Мне кажется, что ИВАНОВ ИВАН ИВАНОВИЧ и ИВАНОВ ИВАН ИВАНОВИЧ всё-таки совпадение получше, то есть логично меру для ИВАН ИВАНОВ и ИВАНОВ ИВАН ИВАНОВИЧ видеть хуже.
Возможно, вы не совсем поняли про "последовательности байт" (собственно я и не пояснял особо). Там ищется не максимально длинное совпадение. Там строки разбиваются на все возможные последовательности N байт (для фиксированного N), например: 'ИВАН', 'ВАН ', 'АН И', 'Н ИВ' и т.д. И вот число совпадающих этих наборов сравнивается. Это достаточно хорошо работает с перестановками слов, опечатками и.т.п. (поэтому я и предложил метод автору). Но пункт про нормализацию строк в той или иной степени может быть полезен в каких-то случаях и здесь.
P.S. Я ни разу не специалист в этой теме, не знаю, как лучше будет работать у автора статьи и как лучше будет работать у вас. Я лишь запостил еще один вариант. Кажется, что у каждого метода есть недостатки, выстреливающие в зависимости от ситуации. Собственно не было бы нескольких разных методов если бы это было не так.
С опечатками да - беда.
Дом-квартира - есть такая проблема, наш бизнес в курсе, пока мирятся. Но это вопрос нормализации. Если д.5, кв.10 нормализовать не в 5 10, а в Д5 КВ10 - проблема уйдет. В принципе, это алгоритмизуется.
Насчет "недописали" - это как раз неполное имя/адрес. Т.е. ИВАНОВ ИВАН и ИВАН ИВАНОВИЧ ИВАНОВ запросто может быть одним и тем же человеком. А вот ИВАНОВ ИВАН ИВАНОВИЧ и ИВАН ПЕТРОВИЧ ИВАНОВ - разные люди и тут совпадений не будет (т.к. у них нет пересечений по полному количеству элементов ни для одного из наборов - в обеих наборах есть элементы, отсутствующие в другом).
В целом это достаточно непростая на самом деле задача, особенно когда речь идет о больших объемах данных.
Сначала мы думали использовать "ключевое слово" - элемент адреса, который реже всего встречается в витрине элементов с которыми надо искать совпадения. И делать предвыборку адресов где потенциально возможны совпадения, а потом уже каждый адрес из предвыборки проверять на совпадения по алгоритму. Но не взлетело - очень плохая селективность получилась и слишком большие объемы для достаточно "тяжелого" точного сравнения. Сейчас перешли на поиск по пересечению витрин. Вот отдали на нагрузочное тестирование на копии промсреды, ждем результат.
Алгоритм расчёта расстояния между строками