Разработка алгоритма быстрого поиска по БД

30 000 руб. за проект • наличный расчёт, безналичный расчёт
08 июня 2018, 17:34 • 7 откликов • 72 просмотра
Необходимо написать алгоритм быстрого поиска логотипа организации.

Логотипы есть, в базе логотипов всего три поля: ID, название на русском языке (Якитория, МТС, МегаФон итд.), прямая ссылка на файл логотипа. База сейчас в простом текстовом формате (.csv).

С процессинга приходят строки вида:
MTS*MOSCOW*Russia
ITUNES.COM/BILL
YANDEX.TAXI
PRODUKTY
AUCHAN VEGASITUNES.COM/BILL
YANDEX.TAXI
PRODUKTY
AUCHAN VEGAS

По этим строкам нужно найти компании в нашей базе:
МТС
iTunes
Яндекс.Такси
Ашан

Непонятные наименования вроде: "PRODUKTY" мы пропускаем.

Но у нас в базе примерно 5000 компаний с логотипами, а пользователей по примерным оценкам будет около 600 тыс. Запрос выписки - один из самых часто-используемых запросов в приложении.
То есть на сервер будет лететь примерно 14 запросов на выписку в секунду.
В выписке мы возвращаем по 100 операций (в приложении реализована пагинация).

То есть получается, если делать по-простому, придется для каждой операции в выписке бежать по базе из 5000 компаний. Это получается 14 x 100 x 5000 = 7 млн тактов в сек. С такой логикой можно разориться на серверах :)

В общем нужно это как-то оптимизировать.

Идеи:

1. Кешировать названия мерчантов. Как только найдена компания для мерчанта из операции в выписке, например для "MULTICARTA*MTS*MOSCOW*Russia" найдено "МТС". Мы можем записать "MULTICARTA*MTS*MOSCOW*Russia" и информацию по организации в отдельную базу и потом бежать сначала по ней, искать точные совпадения.

2. Групировка по MCC-коду. У каждой операции есть 4-ех значный код категории (MCC). После того как организация найдена, мы можем сохранить информацию по ней и название мерчанта в файл с названием в соответсвии с mcc-кодом, например 4543.postgres. В след. раз мы уже проверим есть ли файл с MCC-кодом операции и побежим по нему сначала.

3. Hash для быстрого поиска по таблице.

Для тестирования алгоритма есть 120 тыс. уникальных названий мерчантов.

Сервер написан на Java, поэтому алгоритм желательно тоже писать на Java для простой интеграции.

Сроки: 7-10 дней.