В далеком 2017 году, возникла идея разработать сервис мониторинга цен конкурентов. Его отличительной фишкой от остальных подобных сервисов должна была стать функция ежесуточного автоматического сопоставления товаров. Видимо из — за почти полного отсутствия информации о том, как это делать, сервисы по мониторингу цен предлагали лишь возможность ручного сопоставления силами самих клиентов, либо операторов сервиса с ценой от 0.2 до 1 рубля за факт сопоставления. Реальная же ситуация с, например, 10 сайтами и 20 000 товаров на каждом, неминуемо требует автоматизации процесса, так как ручное сопоставление уже слишком долгое и дорогое.

Ниже будет описан подход к автоматическому сопоставлению на примере ряда конкурирующих аптек с использованием технологии Elaticsearch.

Описание среды


  1. ОС: Windows 10
  2. Основа: Elaticsearch 6.2
  3. Клиент для запросов: Postman 6.2

Настройка Elaticsearch


Конфигурация маппера полей товаров и анализатора в одном запросе

PUT http://localhost:9200/app 
{
  "mappings": {
    "product": {
      "properties": {
        "name": {
          "type": "text",
          "analyzer": "name_analyzer" # указываем анализатор из настроек для имени товара
        },
        "manufacturer": {
          "type": "text"
        },
        "city_id": {
          "type": "integer"
        },
        "company_id": {
          "type": "integer"
        },
        "category_id": {
          "type": "integer"
        },
      }
    }
  },
  "settings": {
    "index": {
      "analysis": {
        "analyzer": {
          "name_analyzer": {
            "type": "custom",
            "tokenizer": "standard", # про этот токенайзер можно подробно почитать в документации, в целом подходит под нашу задачу
            "char_filter": [
              "html_strip", # удаляем случайно попавшие в названия товаров html теги
              "comma_to_dot_char_filter" # заменяем запятые на точки, чтобы вещественные числа парсились
            ],
            "filter": [
              "word_delimeter_filter", # указываем кастомные разделители термов
              "synonym_filter", # добавляем группы синонимов
              "lowercase" # переводим все в нижний регистр
            ]
          }
        },
        "filter": {
          "synonym_filter": {
            "type": "synonym_graph",
            "synonyms": [
              "тюб, тюбик",
              "кап, капельница",
              "капс, капсула",
              "амп, ампула, ампулы",
              "офтальмол, офтальмологический",
              "таб, тбл, табл, таблетки",
              "увл, увлажняющий",
              "наз, назальный",
              "доз, дозированный, дозировка",
              "жев, жеват, жевательные",
              "раств, раствор, растворимые, р-ра, р-р",
              "ин, инъекций, инъекция",
              "покр, покрытый, покрытая, покрытые",
              "инд, индивидуальная",
              "конт, контурная",
              "уп, упак, упаковка",
              "расс, рассас, рассасывания",
              "подъязыч, подъязычные",
              "шип, шипучие",
              "пор, порошек",
              "приг, приготовления",
              "шт, штук, ном, номер",
              "тр, трава",
              "г, g",
              "ml, мл"
            ]
          },
          "word_delimeter_filter": {
            "type": "word_delimiter",
            "type_table": [
              ". => DIGIT", # чтобы попадали в термы вещественные числа
              "- => ALPHANUM",
              "; => SUBWORD_DELIM",
              "` => SUBWORD_DELIM"
            ]
          }
        },
        "char_filter": {
          "comma_to_dot_char_filter": {
            "type": "mapping",
            "mappings": [
              ", => ."
            ]
          }
        }
      }
    }
  }
}

Для примера, можем посмотреть на какие части анализатор «name_analyzer» разобьет название лекарства «Гиоксизон 10мг+30мг/г мазь для наружного применения туба 10г». Используем запрос _analyze.

POST http://localhost:9200/app/_analyze
{
  "analyzer" : "name_analyzer",
  "text" : "Гиоксизон 10мг+30мг/г мазь для наружного применения туба 10г"
}

результат
{
    "tokens": [
        {
            "token": "гиоксизон",
            "start_offset": 0,
            "end_offset": 9,
            "type": "<ALPHANUM>", 
            "position": 0
        },
        {
            "token": "10",
            "start_offset": 10,
            "end_offset": 12,
            "type": "<ALPHANUM>",
            "position": 1
        },
        {
            "token": "мг",
            "start_offset": 12,
            "end_offset": 14,
            "type": "<ALPHANUM>",
            "position": 2
        },
        {
            "token": "30",
            "start_offset": 15,
            "end_offset": 17,
            "type": "<ALPHANUM>",
            "position": 3
        },
        {
            "token": "мг",
            "start_offset": 17,
            "end_offset": 19,
            "type": "<ALPHANUM>",
            "position": 4
        },
        {
            "token": "g",
            "start_offset": 20,
            "end_offset": 21,
            "type": "SYNONYM", #видим, что строка "g" определилась как SYNONYM, это означает, что она совпадет с любым вхождением своей группы синонимов "г, g"
            "position": 5
        },
        {
            "token": "г",
            "start_offset": 20,
            "end_offset": 21,
            "type": "<ALPHANUM>",
            "position": 5
        },
        {
            "token": "мазь",
            "start_offset": 22,
            "end_offset": 26,
            "type": "<ALPHANUM>",
            "position": 6
        },
        {
            "token": "для",
            "start_offset": 27,
            "end_offset": 30,
            "type": "<ALPHANUM>",
            "position": 7
        },
        {
            "token": "наружного",
            "start_offset": 31,
            "end_offset": 40,
            "type": "<ALPHANUM>",
            "position": 8
        },
        {
            "token": "применения",
            "start_offset": 41,
            "end_offset": 51,
            "type": "<ALPHANUM>",
            "position": 9
        },
        {
            "token": "туба",
            "start_offset": 52,
            "end_offset": 56,
            "type": "<ALPHANUM>",
            "position": 10
        },
        {
            "token": "10",
            "start_offset": 57,
            "end_offset": 59,
            "type": "<ALPHANUM>",
            "position": 11
        },
        {
            "token": "g",
            "start_offset": 59,
            "end_offset": 60,
            "type": "SYNONYM",
            "position": 12
        },
        {
            "token": "г",
            "start_offset": 59,
            "end_offset": 60,
            "type": "<ALPHANUM>",
            "position": 12
        }
    ]
}

Заполнение тестовыми данными


Запрос _bulk

POST http://localhost:9200/_bulk
{
  "index": {
    "_index": "app",
    "_type": "product",
    "_id": 195111
  }
}
{
  "name": "Гиоксизон 10мг+30мг/г мазь для наружного применения туба 10г",
  "manufacturer": "Муромский приборостроительный завод АО",
  "city_id": 1,
  "company_id": 2,
  "category_id": 1
}
{
  "index": {
    "_index": "app",
    "_type": "product",
    "_id": 195222
  }
}
{
  "name": "ГИОКСИЗОН мазь для наружнего применения 10 мг+30 мг/г: 10 г",
  "manufacturer": "МПЗ",
  "city_id": 1,
  "company_id": 3,
  "category_id": 1
}

Поиск сопоставлений


Пусть товар нашего клиента, для которого мы хотим найти все похожие товары конкурентов имеет характеристики

{
  "name": "Гиоксизон мазь для наружного применения 10 мг+30 мг/г туба алюминиевая 10 г",
  "manufacturer": "Муромский приборостроительный завод АО",
  "city_id": 1,
  "company_id": 1,
  "category_id": 1
}

Пользуясь справочником лекарственных средств выделяем из названия товара наименование препарата. В данном случае это слово «Гиоксизон». Это слово будет обязательным критерием.

Вырезаем так же все числа из названия — «10 30 10», они также будут обязательным критерием. При этом если какое то число входило дважды, в найденных товарах оно тоже должно входить джважды, иначе мы увеличим шанс совпадения с неправильными товарами.

Запрос _search

GET http://localhost:9200/app/product/_search
{
  "query": {
    "bool": {
      "filter": [
        {
          "terms": {
            "company_id": [
              2,
              3,
              4,
              5,
              6,
              7,
              8
            ]
          }
        },
        {
          "term": {
            "city_id": {
              "value": 1,
              "boost": 1
            }
          }
        },
        {
          "term": {
            "category_id": {
              "value": 1,
              "boost": 1
            }
          }
        }
      ],
      "must": [
        {
          "bool": {
            "should": [
              {
                "match": {
                  "name": {
                    "query": "мазь для наружного применения мг+ мг/г туба алюминиевая г",
                    "boost": 1,
                    "operator": "or",
                    "minimum_should_match": 0,
                    "fuzziness": "AUTO"
                  }
                }
              }
            ],
            "must": [
              {
                "match": {
                  "name": {
                    "query": "Гиоксизон",
                    "boost": 2,
                    "operator": "or",
                    "minimum_should_match": "70%",
                    "fuzziness": "AUTO"
                  }
                }
              },
              {
                "match_phrase": {
                  "name": {
                    "query": "10 30 10",
                    "boost": 2,
                    "slop": 100
                  }
                }
              }
            ]
          }
        }
      ],
      "should": [
        {
          "bool": {
            "should": [
              {
                "match": {
                  "manufacturer": {
                    "query": "Муромский приборостроительный завод АО",
                    "boost": 1,
                    "operator": "or",
                    "minimum_should_match": "70%",
                    "fuzziness": "AUTO"
                  }
                }
              },
              {
                "match": {
                  "manufacturer": {
                    "query": "Вalenta Фarmacevtika ОАО",
                    "boost": 1,
                    "operator": "or",
                    "minimum_should_match": "70%",
                    "fuzziness": "AUTO"
                  }
                }
              }
            ]
          }
        }
      ]
    }
  },
  "highlight": {
    "fields": {
      "name": {}
    }
  },
  "size": 50
}

На выходе получаем id товаров, а также их названия + score для аналитики, с выделенными совпавшими фрагментами.

  • Гиоксизон 10мг+30мг/г мазь для наружного применения туба 10г — Оценка алгоритмом: 69.84
  • ГИОКСИЗОН мазь для наружнего применения 10 мг+30 мг/г: 10 г — Оценка алгоритмом: 49.79

Заключение


Описанный способ конечно не даст 100% точности сопоставления, но намного облегчит процесс ручного сопоставления товаров. Также подойдет для задачи, не требующей абсолютной точности.
В целом, если улучшать поисковый запрос методами дополнительных эвристик и увеличения количества синонимов, можно добиться результата близкого к удовлетворительному.
Кроме того, тесты производительности, производимые на стареньком i7, показали хорошие результаты. 10 поисковых запросов в массиве из 200000 товаров выполняются в пределах пары секунд. В живую данный пример с лекарствами можно посмотреть здесь.

Предлагайте свои варианты, способы сопоставления в комментариях.

Спасибо за внимание!

Комментарии (13)


  1. Razoomnick
    05.11.2018 20:39

    Я сейчас работаю над похожей задачей. Только elasticsearch мне не подошел из-за быстродействия, инфраструктуру сам пишу.

    Пока результаты такие: на ноутбуке с Core i5 7300HQ и SSD на массиве в 750 тысяч товаров обрабатывается примерно 5500 сопоставлений в секунду, это с парсингом входящих данных и сохранением результатов в базу, но без ответа на http запросы. Просто модель взаимодействия с клиентами предполагается другая, обработка не по одному запросу, а сразу большого массива данных.

    Возможно, из этого получится сервис или что-то вроде того, но пока в публичном доступе ничего нет, к сожалению, продемонстрировать не могу.


    1. GHostly_FOX
      05.11.2018 23:30

      Если работать с Elasticsearch то там точно ноута маловато будет.
      За счет того что он работает на Java то кушает довольно таки много оперативы.

      Несколько индексов с объемом от 3 до ~12 млн записей. Ведет себя замечательно…


    1. mentalMedley
      06.11.2018 13:48

      Я тоже работаю на сопоставлением лекарств и меня поражает скорость Вашего алгоритма! Можете поподробнее рассказать на каких технологиях разработан алгоритм, какая у алгоритма точность сравнения?


      1. Razoomnick
        08.11.2018 02:29

        Если вкратце — то алгоритм состоит из последовательных шагов, от быстрых и надежных к более медленным и менее надежным. Скорость достигается за счет использования хэш-таблиц почти везде, где возможно. Сначала просто поиск по полному хэшу, потом поиск с использованием другой хэш-функции, которая нечувствительна к перемене слов местами, потом поиск по третьему хэшу и так далее до момента, когда либо нашли что-то надежное, либо разбиваем исходную строку на части и начинаем сначала. Все это перемешано со множеством костылей (ну или эвристик, как угодно :))

        Что касается точности, то мы ведем статистику по 5 категориям. На каталоге с электроникой, бытовой техникой и товарами для дома (тот самый на 750 тысяч товаров) точность такая:

        • товар есть в каталоге и сопоставился правильно — 84%
        • товар есть в каталоге, но не сопоставился, требуется ручное сопоставление — 16%
        • товар есть в каталоге и сопоставился неправильно — 0.2%
        • товара нет в каталоге, и программа это правильно определила — 98.5%
        • товара нет в каталоге, но программа его сопоставила какому-то из товаров — 1.5%

        По 80% позиций все решения принимаются автоматически, среди них 0.1% ошибок. Остальное сопоставляется или уже сопоставленное подтверждается человеком, естественно, по каждой позиции — один раз, поэтому со временем процент автоматических решений растет.


        1. Razoomnick
          08.11.2018 03:17

          Вдогонку к 16%, отправленным на ручное сопоставление. Если электроника, бытовая техника и остальной массовый продукт у разных поставщиков называется хотя бы похоже, то с мебелью — часто мрак. Условно, диван «Диприз трехместный кожа» на сайте — это «Мебель для гостиной 11-21-311» в прайсе.


    1. FYR
      06.11.2018 21:29

      На самом деле если говорить про FTS индексаторы, то сейчас де факто стандарт это:

      • Библиотека Apache lucene и построенные на ней Elastic и Solr. Причем если вам не нужно горизонтальное масштабирование — я бы советовал Solr — там версии lucene посвежей, а elastic получше с кластерностью.
      • Sphinx: отечественный, не очень кластерный, но шустрее за счет с++ и кучи оптимизаций.


      Но в принципе под капотом одинаково: токенайзер => стемминг/словарь => инвертированный индекс


  1. Mantikor_WRX_STi
    05.11.2018 22:40

    С 16 года делаю клиентам софт для сравнения цен конкурентов, по заданным алгоритмам. У кого то сравниваются готовые прайсы, у кого то парсинг с сайтов. Все на чистом питоне. GUI для редактирования настроек алгоритма писал на Delphi


  1. GHostly_FOX
    05.11.2018 23:33

    Было бы интереснее если бы в статье рассказали про свой способ индексации большого объема данных. Просто сейчас это как пособие для начинающий в котором описаны базовые вещи.


    1. bormotov
      06.11.2018 00:05

      Автор и рассказал — способ индексации — elasticsearch.
      Если нтересно «больше внутренностей» — apache lucene — вокруг это библиотки elastic построен


      1. GHostly_FOX
        06.11.2018 13:13

        Нет, это пара товаров…
        А вот вопрос как подходить к вопросу с большими данными!? Когда в индексе около 5 млн. записей? Как их индексировать? Как по ним поддерживать актуальность? Не проводить же каждый раз Full Index


        1. AlexSidor Автор
          06.11.2018 13:51

          Если использовать symfony и бандл elastica, то можно не заботиться об актуальности данных, бандл следит за изменениями в entitymanager и обновляет индекс elasticsearch


        1. FYR
          06.11.2018 21:24

          5 млн… записей это не большие данные.
          На сервере класса HP gen9 elastic переваривает индексацию Bulk потоком 5-10 мегабайт/секунду практически из коробки. Если у вас запись под килобайт то пережует он эти 5 млн записей по килобайту за 7-15 минут.
          Но никто не отменял апдейты и партиционирование.


  1. loskamo
    06.11.2018 15:19

    В далеком 2017 году

    Всмысле?