Мы активно изучаем различные алгоритмы (поиск k-ближайших соседей, задача о рюкзаке, всякие алгоритмы сортировки, поиска и т. п.). А часто ли удаётся почитать пример их практического внедрения на каком-нибудь предприятии? Такие истории встречаются реже, чем даже обзоры книг по этим же алгоритмам.

Предлагаю всем вместе начать исправлять эту ситуацию и приглашаю почитать о том, как на промышленном складе применяли — внезапно! — алгоритм Левенштейна (способ нечёткого сравнения строк).

Значительная часть нюансов спрятана под спойлеры, чтобы не отвлекать от сути статьи, а также не отпугивать маленьких. Обычно такие статьи становятся очень длинными, но мне удалось уместиться примерно в 3200 слов.

Для понимания статьи читателю хватит самого поверхностного умения чуть-чуть читать код си-подобного синтаксиса. Познания в области работы склада не обязательны.

Дано: большой склад с развитым адресным хранением, а также список товаров на нём. Список составляет многие тысячи наименований.

Сразу опишем проблему, которую нам озвучил склад. Посмотрите на изображение ниже:

Почти случайное фото из просторов сети, где глаза разбегаются
Почти случайное фото из просторов сети, где глаза разбегаются

Вы сумеете найти на ней гель-лак для маникюра «Soline»? Сколько времени у вас на это ушло? Много. С аналогичной проблемой сталкиваются сборщики товара: на одной ячейке может оказаться много похожих товаров. Ситуация усугубляется тем, что многие неопытные сотрудники даже не знают заранее, как выглядит этот товар. Это мешает им найти нужный, даже если он выделяется внешне (но и это бывает не всегда). Если на товаре есть текст, то это тоже не означает, что его быстро найдут. Таким образом, сборщик тратит время не только на то, чтобы найти полку (ячейку) на складе, но и на поиски внутри самой ячейки.

Как эту проблему решали раньше?

На складе с самого начала было адресное хранение. WMS хранила как перечень ячеек во всех помещениях, так и то, какой товар на какой из них лежит. Система сама показывала сборщикам из какой ячейки брать товар, который сейчас нужно собрать. Она же автоматически этот товар списывала с ячейки, поддерживая актуальность информации о текущих запасах.

До поры до времени использовали монотоварные ячейки. На таких ячейках разрешено размещать только идентичный товар. При сборке достаточно найти нужную ячейку, а потом набрать из него столько товара, сколько нужно и даже не читать его название.

Почему решение перестало работать? Потому что количество наименований уже давно превысило количество имеющихся ячеек. Также один и тот же товар разных серий с разными сроками годности нежелательно хранить вместе. Иными словами, ячейки закончились, а уменьшать их размер, чтобы увеличить их количество, все уже устали. Вдобавок, монотоварные ячейки часто стоят полупустые: на полке лежит последняя оставшаяся коробочка зубных щёток редкой разновидности, а из-за монотоварного ограничения на полку больше нельзя ничего положить. Это приводит к неэффективному использованию пространства.

Ситуация осложняется тем, что среди товаров достаточно много похожих, но разных. Сравните:

  • Ибупрофен 20 мг №30

  • Ибупрофен 30 мг №20

  • Индовазин 30 мг №20

Сотрудники могут легко перепутать дозировку с количеством и наоборот. У первых двух препаратов почти идентичны не только названия, но и упаковки. Ближе к концу рабочей смены ещё и появляется усталость сборщиков, которые начинают путать даже отдалённо похожие названия. Самая больная сфера, где названия имеют огромную схожесть — это лекарственные препараты со своими дозировками и формами, а также изделия медицинского назначения типа шприцов, бинтов и перчаток. Отдельно можно отметить материалы для маникюрного сервиса — не пытайтесь самостоятельно разобраться в многообразии гелей и лаков, алмазных головок, которые в каких-то местах могут называться фрезами, в каких-то других — ёлочками (вполне официально). Средства гигиены для женщин и детей имеют свою специфику, но тоже часто путаются. Я бы ещё отметил уголь — его названия не сильно схожи (берёзовый, сосновый, для шашлыков, деревенский), но упаковки похожи как две капли воды, а крупными буквами написано только одно слово — «уголь». Остальные — более важные слова — могут быть написаны мелким шрифтом и не бросаться в глаза.

Предложенное решение: процесс сборки оставить как есть, но усовершенствовать приёмку и размещение товара в ячейках. Нужно, чтобы в каждой ячейке лежали только очень разные товары, например: зубная паста, перчатки, салфетки, пластиковые банки и какие-нибудь витаминки. Нельзя, чтобы в ячейке лежали перчатки сразу нескольких размеров, ровно как и других похожих товаров.

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

Реализация сделана так, что сотрудник приёмки при поступлении нового товара автоматически получал от WMS рекомендуемую ячейку, куда этот товар следует положить. Ячейка выбирается:

  • либо пустая

  • либо не содержащая товаров с похожим названием

Конечно, и тут было гораздо больше критериев, но в статье мы их опустим.

Ищем решения

Как мы определим, что название «Хлорид натрия 500 мл №6» больше похоже на «Натрия хлорид 0,5 л 6 шт», чем «Кальция глюконат 500 мг №30»? Начинать искать ответ нужно в любимом поисковике по фразе типа: «Нечёткое сравнение строк». В ответ мы получаем несколько изобретённых алгоритмов и выбираем любой из них. Для примера — расстояние Левенштейна. Далее воспользуемся таким изобретением как «лень», и снова пойдём в поисковую систему с запросом вида: «расстояние Левенштейна ваш_любимый_язык_программирования». Если находим готовый общедоступный код — идём дальше. В нашем случае образцов хватает: тут примеры сразу на 15 языках, а в некоторых языках даже есть готовая функция.

Забегая вперёд скажу, что результат работы любого такого алгоритма будет немного грустным. Нам всегда придётся доработать алгоритм, чтобы он подходил конкретно нам. Для этого потребуется глубокое, не побоюсь этого слова, проникновение во внутренний мир алгоритма. Отмечу, что найти алгоритм — это не то же самое, что применять его. Фраза «всё уже придумано до нас» тут не работает.

Да, когда алгоритм найден — это только самое начало работы! Любое применение универсального алгоритма на практике — это в какой-то мере подгонка под ответ желаемый результат. Далее статья будет состоять последовательных шагов, которые позволят приспособить алгоритм для реального применения.

Проба пера

На уровне кода алгоритм представляет собой функцию, принимающую два параметра — строчку №1 и строчку №2. Функция возвращает в ответ число, которое показывает «похожесть» первой строки на вторую. Если число равно нулю, значит строки одинаковые. Если число небольшое, значит строки разные, но похожие. Чем больше число — тем строчки различаются сильней.

Тестировать будем вот таким кодом

Образец взят без изменений с первых страниц поисковика:

function levenshtein_distance($source, $dest)
{
    if ($source == $dest)
        return 0;

    list($slen, $dlen) = [mb_strlen($source), mb_strlen($dest)];

    if ($slen == 0 || $dlen == 0) {
        return $dlen ? $dlen : $slen;
    }

    $dist = range(0, $dlen);

    for ($i = 0; $i < $slen; $i++)
    {
        $_dist = [$i + 1];
        for ($j = 0; $j < $dlen; $j++)
        {
            $cost = ($source[$i] == $dest[$j]) ? 0 : 1;
            $_dist[$j + 1] = min(
                $dist[$j + 1] + 1,   // удаление
                $_dist[$j] + 1,      // вставка
                $dist[$j] + $cost    // замена
            );
        }
        $dist = $_dist;
    }

    return $dist[$dlen];
}

Данную функцию сохраняем в файл, который, например, можно открывать в браузере или запускать из командой строки.

Сравним строчки ниже. Например, дописав этот код в наш файл и запустив его из командой строки:

$text_1 = 'Амлодипин-Веро 5мг таб. №30';
$text_2 = 'Амлодипин-Прана 5мг таб. №90';
echo levenshtein_distance($text_1, $text_2) . PHP_EOL;

Результат: 7. Если заменить первый товар на «Анвифен 250мг капс. №20», то результат будет уже 17. Похоже, мы на верном пути. Но давайте теперь сравним эти два товара:

$text_1 = 'Амиодарон 50мл/мл конц. д/приг. р-р д/в/в 3мл амп. №10';
$text_2 = 'Амиодарон амп. 50 мл/мл конц. д/приг. р-ра в/в 3 мл №10';
echo levenshtein_distance($text_1, $text_2) . PHP_EOL; // Результат: 17

Что?! Это ведь один и тот же товар, просто во втором случае сокращённое слово «ампулы» переместили с предпоследнего места на второе! А ещё во втором наконец-то поставили пробелы между числами и единицами измерения. Выходит, качество нашей работы зависит не только от алгоритма, но и от конкретных данных.

Неглубокое, снова простите за каламбур, погружение в суть работы этого алгоритма говорит, что он учитывает обычные перестановки символов и слов местами, что лучше видно на таком примере:

$text_1 = 'Я зарабатываю хорошо';
$text_2 = 'Я хорошо зарабатываю';
echo levenshtein_distance($text_1, $text_2) . PHP_EOL;  // Результат: 12

А ещё всё это дело является регистрозависимым. Как избавиться от этих недостатков?

Для этого мы введём предварительную обработку сравниваемых строк, а уже потом будем вычислять расстояние Левенштейна между получившимися. Назовём этот процесс нормализацией. Кому-то может понравится иной термин, но на вкус и цвет всё равно все фломастеры разные.

Первое, что приходит на ум и действительно будет работать — привести все символы к одному регистру. Второе — отсортировать все слова в алфавитном порядке.

Функция, которая это сделает, может быть примерно такой
function normalize($string)
{
    $string = mb_strtolower($string);

    $array_of_words = explode(' ', $string);
    sort($array_of_words);
    $sorted_string = implode(' ', $array_of_words);

    return $sorted_string;
}

Напомню, выше мы получили расстояние 12, здесь уже всё стало хорошо:

$text_1 = 'Я хорошо зарабатываю';
$text_2 = 'Я зарабатываю хорошо';
$text_1 = normalize($text_1);
$text_2 = normalize($text_2);
echo levenshtein_distance($text_1, $text_2) . PHP_EOL; // Результат: 0

Но и тут можно увидеть недостаток, если изменить данные так:

$text_1 = 'Я, Лена, хорошо зарабатываю';
$text_2 = 'Я, Елена, хорошо зарабатываю';
$text_1 = normalize($text_1);
$text_2 = normalize($text_2);
echo levenshtein_distance($text_1, $text_2) . PHP_EOL; // Результат: 19

В реальности строка отличается одной буквой, но алгоритм всё равно выдаёт достаточно сильное расхождение. Одно-единственное отличающееся слово занимает разную позицию в алфавитном порядке, а это резко влияет на алгоритм. Фразы ниже тоже отличаются на одну букву, но расстояние уже очень маленькое, потому что алфавитный порядок остаётся прежним:

$text_1 = 'Я, Лена, хорошо зарабатываю';
$text_2 = 'Я, Ленка, хорошо зарабатываю';
$text_1 = normalize($text_1);
$text_2 = normalize($text_2);
echo levenshtein_distance($text_1, $text_2) . PHP_EOL; // Результат: 1

Как быть здесь? Тут уже нужно проявить творчество. Можно, например, убрать из сравнения все одинаковые слова — зачем их вообще сравнивать, раз они идентичные? Можно же сравнивать только различные части строк. Иногда это работает отменно.

Функция, выбирающая только отличающиеся слова, могла бы быть такой
function get_different_words(&$string_1, &$string_2)
{
    // Я опущу проверку корректности входных аргументов — статья не об этом
    $string_1 = explode(' ', $string_1);
    $string_2 = explode(' ', $string_2);
    $unique_words_1 = array_diff($string_1, $string_2);
    $unique_words_2 = array_diff($string_2, $string_1);
    $string_1 = implode(' ', $unique_words_1);
    $string_2 = implode(' ', $unique_words_2);
}

Результат работы можно показать вот так:

$text_1 = 'Светлана! Я не пью!';
$text_2 = 'Света! Я вообще не пью!';
get_different_words($text_1, $text_2);
$text_1 = normalize($text_1);
$text_2 = normalize($text_2);
echo levenshtein_distance($text_1, $text_2) . PHP_EOL; // Результат: 9

Без вызова get_different_words() результат был бы 17. Уже хорошо, но и на эту косу можно найти свой камень. Смотрите:

$text_1 = 'Невероятно, но химическое вещество "земляничный альдегид" не является альдегидом, а ещё не входит в состав земляники. На самом деле это этиловый эфир, а название просто исторически сложилось. Ошибка!';
$text_2 = 'Невероятно, но химическое вещество "земляничный альдегид" не является альдегидом, а ещё не входит в состав земляники. На самом деле это этиловый эфир, а название просто исторически сложилось. Ошибка первооткрывателя!';
get_different_words($text_1, $text_2);
$text_1 = normalize($text_1);
$text_2 = normalize($text_2);
echo levenshtein_distance($text_1, $text_2) . PHP_EOL; // Разница: 17

А вот два несвязанных (почти) слова выдали довольно скромное расстояние:

$text_1 = 'Байкал';
$text_2 = 'Эльбрус';
get_different_words($text_1, $text_2);
$text_1 = normalize($text_1);
$text_2 = normalize($text_2);
echo levenshtein_distance($text_1, $text_2) . PHP_EOL; // Разница: 6

Математически всё верно, но интуитивно мы ожидаем противоположного результата. Ведь первый пример состоит из почти идентичных кусков текста. Наши же доработки приводят к тому, что фактически вместо них сравниваются строки «» (пустая строка) и «первооткрывателя». Получается, нельзя так просто удалять общие для обеих строк слова?

Выходит, нужно придумать алгоритм, учитывающий исключённые из сравнения части текста. Такого алгоритма нет, но мы можем не изобретать велосипед, а пойти в том же русле, что и исходный алгоритм Левенштейна. Попробуем для начала учитывать количество удалённых из сравнения слов и рассматривать его как своеобразное «расстояние». Чем больше таких слов, тем строчки текста являются более похожими. Останется это только испытать. Чтобы это хорошо вписывалось в модель исходного алгоритма сделаем это расстояние отрицательным и в качестве новой метрики будем использовать алгебраическую сумму «обычного» расстояния и «необычного».

Для реализации нам потребуется функция примерно такого вида
function calculate_convergence(&$string_1, &$string_2)
{
    $string_1 = explode(' ', $string_1);
    $string_2 = explode(' ', $string_2);
    $unique_words_1 = array_diff($string_1, $string_2);
    $unique_words_2 = array_diff($string_2, $string_1);

    $quantity_common_words = count($string_1) - count($unique_words_1);

    $string_1 = implode(' ', $unique_words_1);
    $string_2 = implode(' ', $unique_words_2);

    return $quantity_common_words;
}

Да, я знаю, что функция слишком перегружена и выполняет слишком много работы: и параметры принимает по ссылке, изменяя их после выполнения, и возвращаемое значение есть в виде количества совпавших слов, но для иллюстрации идеи подойдёт. А вообще, хорошая функция всё-таки должна выполнять лишь одно действие и делать это хорошо.

Испытание двух строк из предыдущего примера можно провести теперь вот так:

$quantity_common_words = calculate_convergence($text_1, $text_2);
$text_1 = normalize($text_1);
$text_2 = normalize($text_2);
echo (levenshtein_distance($text_1, $text_2) - $quantity_common_words) . PHP_EOL;

Полученные результаты будут -10 и 6, что вписывается в нашу модель: чем меньше число, тем строчки более похожи и наоборот. Но всё равно это как-то грустно. Посмотрите на следующие два отрывка:

  1. А знаете ли вы, что самый массовый танк в битву за Москву собирался из автомобильных запчастей, а вооружался авиационной пушкой? Это был результат хардкорной борьбы за производственную технологичность машины, которой пытались компенсировать откровенно слабые боевые качества и нецелевое использование.

  2. А знаете ли вы, что самый массовый танк в битву за Москву собирался из автомобильных запчастей, а вооружался авиационной пушкой? Это был результат хардкорной борьбы за производственную технологичность машины, которой пытались компенсировать откровенно слабые боевые качества и нецелевое использование. Конструктор - Николай Астров.

Результат: -10. А вот так:

  1. Волга начинается в Тверской области и течёт в Каспийское море.

  2. Волга начинается в Тверской области и течёт в северную часть Каспийского моря.

Результат: -8. Алгоритм явно работает, но хотелось бы получить более ярко выраженный результат. Да, на совсем разных строках алгоритм выдаёт большое расстояние — это прекрасно, но нам хочется более чётко различать именно похожие названия.

Можно сделать ещё лучше? Не факт, но попробуем и посмотрим на результат. Давайте добавим для каждого исключённого общего слова некий «вес». Тогда при вычислении «компонента похожести» мы будем суммировать именно вес каждого одинакового слова, а не просто считать их количество. Почему так? Если какое-то слово длиннее, то и важность у него больше, а если слово короткое, то оно не сильно-то и влияет на сходство. Небольшой вес у коротких слов поможет избежать проблем, которые создают союзы или какие-нибудь другие короткие слова, ведь они часто не несут какой-то полезной (для наших целей!) нагрузки.

Функция, рассчитывающая вес, может быть такой
function calculate_weight(&$string_1, &$string_2)
{
    $length_1 = mb_strlen($string_1);
    $length_2 = mb_strlen($string_2);

    $words_1 = explode(' ', $string_1);
    $words_2 = explode(' ', $string_2);

    $unique_words_1 = array_diff($words_1, $words_2);
    $unique_words_2 = array_diff($words_2, $words_1);

    $common_words = array_diff($words_1, $unique_words_1);

    // Для вычисления суммарного веса потребуется перебрать все общие слова в обоих строчках:
    $weight = 0;
    foreach ($common_words as $word)
    {
        $word_length = mb_strlen($word);
        $weight_in_string_1 = $word_length / $length_1;
        $weight_in_string_2 = $word_length / $length_2;
        $word_weight = ($weight_in_string_1 + $weight_in_string_2) / 2; // смелое предположение?

        $weight = $weight + $word_weight;
    }

    return $weight;
}

Хорошо, а как этот вес учесть? Сложить? Вычесть? Умножить? Поделить? Смотрите:

$weight = calculate_weight($text_1, $text_2);

$text_1 = normalize($text_1);
$text_2 = normalize($text_2);

echo (levenshtein_distance($text_1, $text_2) * (1 - $weight)) . PHP_EOL;

Как видно, новой мерой решено взять не сам вес, а величину (1 - weight). И да, этот коэффициент используется как множитель, а не слагаемое. Поведение у этой доработки такое:

  • Если общие слова составляют 0% от обеих строк (общих слов нет), то тогда похожесть не отличается от расстояния Левенштейна.

  • Если общие слова составляют 100%, то расстояние нулевое, как и в исходном алгоритме.

  • Если общих слов много и они имеют большой вес, то коэффициент (1 - weight) сильно уменьшает расстояние, рассчитанное для оставшихся слов.

  • Если общих слов много и они имеют небольшой вес, новый коэффициент тоже уменьшает расстояние, но слабо.

Конкретный пример:

$text_1 = 'Блины - это очень вкусное блюдо. Вероятно, лучшее, что есть в мировой кухни. Я настолько люблю блины, что мог бы разместить здесь один из их многочисленных рецептов. Целиком. Но для наших экспериментов это будет излишне.';
$text_2 = 'Блины - это очень вкусное блюдо. Вероятно, лучшее, что есть в мировой кухни. Я настолько люблю блины, что мог бы разместить здесь один из их многочисленных рецептов. Целиком. Однако для наших экспериментов это будет излишне, поэтому воздержусь.';
// Результат: 5.98.

$text_1 = 'Завтра я пойду в гости и буду есть вкусные блины.';
$text_2 = 'Завтра я пойду в гости и буду есть мои любимые блины.';
// Результат: 6.69

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

Наконец, мы перешли к финальной части статьи. В ней приступим к обработке мелких нюансов. Наши основные примеры были намеренно не из названий товаров, чтобы ход мыслей был выразительней. Для реальных названий алгоритм останется тот, который мы только что создали, но принципы нормализации будут другие. Назовём мы это борьбой с результатами человеческой жизнедеятельности. Как по мне, это сильней всего смахивает на подгонку результатов алгоритма под желаемый результат. То, от чего нас отучали в школе, но активно используется вне её. Для подобных процессов есть более политкорректные названия: калибровка, юстировка или настройка. Приступим.

У пользователей есть мания на сокращения и спецсимволы, с которыми нужно что-то делать. Давайте прикинем, глубже изучив матчасть. В медикаментах, например, часто встречаются сокращения: в/в, в/м, д/п, р-р (внутривенное, внутримышечное, для приготовления, раствор) и т. п. Очень (!) часто встречаются единицы измерения: мл, ед, шт, мг, ЕМ, уп, фл, которые имеют решающее значение в применении на людях, но не для сравнения. Так уж вышло, что один и тот же препарат в разных дозировках производители измеряют одной единицей измерения: «Озверин 250 мг», «Озверин 500 мг» и «Озверин 1000 мг», хотя с точки зрения какого-нибудь метролога последний логичней было бы назвать «Озверин 1 г». Давайте зацепимся за этот факт?

С сокращениями понятно, а спецсимволы?

Разные символы могут использовать с одной целью. Для примера, слово «раствор» могут сокращать как «р-р» и «р/р». Напрашивается тотальное удаление спецсимволов, но не всё так просто!
Единичный спецсимвол имеет крайне небольшой вес в сравнении, поэтому их удаление может не оказать существенного влияния. А ещё удаление спецсимволов может привести к нежелательному объединению двух слов в одно, например: «мужской/женский» превратится в «мужскойженский», хотя в похожем названии спецсимвола могло не быть и там два слова так и будут двумя словами.

Отдельного упоминания заслуживают запятая и точка. Удалять их страшно, так как оба используются как разделитель в числах: 0,9%, 82.5, 72.5 и т. п. Однако оставлять их без внимания тоже нельзя, ведь «1,5 мг» и «1.5 мг» - это одно и то же по сути, но не одно и то же для алгоритма.

Общее решение для всего этого: заменить все запятые на точки, а остальные спецсимволы — на пробелы. По итогу в строках могут появиться сразу двойные и тройные пробелы, которые тоже нужно заменить на одинарные.

Ещё в названиях, если их копировали из какого-нибудь pdf, могли попасть и управляющие символы возврата каретки или переноса строки — их нужно удалить вовсе.

Напоминаю, что ранее у нас была функция нормализации строки:

function normalize($string)
{
    $string = mb_strtolower($string);

    $array_of_words = explode(' ', $string);
    sort($array_of_words);
    $sorted_string = implode(' ', $array_of_words);

    return $sorted_string;
}

В ней-то и нужно выполнить всю «чистку». В большинстве языков программирования уже есть подходящие для этого инструменты. Перед вызовом sort() мы могли бы вставить такие строчки:

$black_list = array('мл', ' мг', 'шт', 'уп', 'мл.', ' мг.', 'шт.', 'уп.');
$array_of_words = array_diff($array_of_words, $black_list);

Разумеется, реальный «словарь» безвозвратно удаляемых сочетаний у каждой товарной области будет свой, а сама замена — не такой прямолинейной. Но это уже детали реализации.

А каков результат-то?

В глубине души мы всегда ожидаем кратного увеличения прежних показателей. На практике такого почти не бывает. Дело в том, что мы чаще оптимизируем не с нуля, а уже после многолетнего улучшения. Поэтому показатели даже в 30% увеличения эффективности нам не снятся. Но «жалкие» 3,75% — это уже миллионы экономии в год. Когда бизнес-процессы предприятия уже хорошо отработаны, других результатов ждать не стоит даже от самых хитроумных алгоритмов. Но вы всегда пытайтесь!

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


  1. shornikov
    06.11.2022 09:15

    Думается, можно было приспособить сфинкс или эластик для этого.

    Получаем список непригодных товаров-ячеек, потом выбираем из оставшихся ячейку где хранятся товары другой категории, попутно учитывая цвет/размер/тип упаковки.


    1. sepetov Автор
      06.11.2022 09:27

      Да, это самый верный подход, нежели изобретать колесо.

      Когда я впервые реализовывал эту тему, то работать приходилось в устаревшем Navision 6.0, где подцепить что-то внешнее можно было только с большими плясками вокруг automation. В тот момент, признаюсь честно, моей квалификации для этого было недостаточно :-) Потом я этот опыт учёл.


    1. olku
      06.11.2022 10:35
      +1

      Тоже про Lucene подумал. Проблема в том, что стандартный анализатор текста хорош для естественного языка. Для медикаментов скорее всего придется писать свой. Для обслуживается универсального магазина понадобится учитывать больше контекста для построения индекса. Например, хоть медицинской уголь визуально отличается от угля для рисования или гриля, пикер, работающий лишь с наименованием товара, будет промахиваться. Поэтому для исключения человеческого фактора применяют сканер кодов.


      1. AnatolV
        06.11.2022 20:12

        я думаю для медикаментов удобнее по действующему веществу или их комбинации и дозировке подбирать а все коммерческие названия запретить


        1. sepetov Автор
          06.11.2022 20:21
          +1

          Увы, но это из рубрики "вредные советы", которые и в думу даже пропихнули. Конкретный пример:

          • препарат "Вальпроевая кислота", стоит очень недорого, уже давно снят с производства в чистом виде

          • препарат "Депакин" - действующее вещество одно и это тоже вальпроевая кислота, чуть дороже, недавно снят с производства, продавался параллельно следующему

          • препарат "Депакин Хроно" - то же действующее вещество, ещё дороже, в производстве и в продаже.

          Все три предназначены для одного и того же, но действуют с очень разной эффективностью. Разная технология производства. Это как АвтоВАЗ и BMW - и там и там ключевое слово "автомобиль", вроде бы одно и то же, а результат? На память ещё вспоминаю какие-то препараты "Эпитерра" и "Кеппра". Одно действующее вещество (и, через промежуточные лица) один производитель. Первое - дешёвый ширпотреб, эффективность чуть пониже. Второе - дороговатое, эффективность высокая.


          1. AnatolV
            06.11.2022 20:33

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


            1. sepetov Автор
              06.11.2022 20:39
              +1

              Да, маркетинг - беда-бедой! Стандартизировать бы их, как это сделано с молоком (1.5%, 2.5, 3.5 и т. д.) или маслом (82.5, 72.5 и т. д.). Хотя и там дрянь встречается даже в пределах одного производителя. Вот только чиновники за это цепляются и выходит только хуже: "Давайте нам дешёвый вариант, действующее вещество же одно!". У нас так человека уволили, а потом вдруг пациент первый помер (мозгом).


  1. 2er6e1
    06.11.2022 09:25

    Предлагаю всем вместе начать исправлять эту ситуацию и приглашаю почитать о том, как на промышленном складе применяли — внезапно! — алгоритм Левенштейна (способ нечёткого сравнения строк).

    кликбейт!

    Про то как алгоритм собсно на складе применяли - не рассказано.


    1. sepetov Автор
      06.11.2022 09:32
      +4

      Ну неправда же. Названа конкретная проблема, которая мешает работе сборщиков? Указано, что WMS теперь сама находит рекомендуемую ячейку для размещения товара, чтобы всем было хорошо?

      И, конечно, описан самый сложный момент - почему простой вызов готовой функции не дал нужного эффекта и как для этого был доработан сам алгоритм. Если этого мало, предложите дополнение и я отредактирую статью.


      1. SGordon123
        06.11.2022 10:18

        А В вмс о товаре, традиционно ничего не известно кроме названия и массогабарита?


        1. sepetov Автор
          06.11.2022 10:23

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


          1. SGordon123
            07.11.2022 11:57

            ну и если в одной - то не прощще по параметрам поделить ( или найти их в других конторах?)


            1. sepetov Автор
              07.11.2022 12:20

              Да! Там бы вполне сработала такая схема размещения: в одной ячейке не больше одного товара из одной товарной категории (там это достаточно хороший параметр). Все счастливы.

              P. S. Тут, кстати, тоже можно найти минус в алгоритме. Когда поступает новый товар и под него создаётся новая карточка, то заполнить категорию могут уже после размещения. В складах "на потоке" так обычно и есть:

              1. приёмщик заводит карточку товара, указывая лишь те параметры, которые важны ему: название, штрихкод, условия хранения и габариты.

              2. сотрудник отдела закупок заполнит карточку до конца уже позже, занося страну, производителя и прочее.


              1. SGordon123
                07.11.2022 12:30
                +1

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


              1. edo1h
                08.11.2022 06:33

                Когда поступает новый товар и под него создаётся новая карточка, то заполнить категорию могут уже после размещения

                ничего страшного, класть его пока в отдельную ячейку.


      1. nordson21
        08.11.2022 12:46
        +1

        Я как полный нуб говорю вам огромное спасибо. Намного интереснее изучать алгоритм на конкретных прикладных примерах. Код даже не смотрел, сама идея применения интересна.


        1. sepetov Автор
          08.11.2022 12:50

          Пожалуйста :-) На новогодних праздниках будет много свободного времени, есть вероятность, что я напишу о генетических алгоритмах на тему такого же склада. Там всё сложней, но в пределах разумного.


  1. sunnybear
    06.11.2022 12:27

    Почему нельзя было взять левенштейн, отнесенный к длине строки?


    1. sepetov Автор
      06.11.2022 12:49

      Провёл тест - результат хуже. Если верно понял, то предлагается мерой похожести использовать отношение расстояния Левенштейна к длине одной из строк?

      $text_1 = 'Амлодипин-Веро 5мг таб. №30';
      $text_2 = 'Амлодипин-Прана 5мг таб. №90';
      echo levenshtein_distance($text_1, $text_2) / mb_strlen($text_1)
      // Результат: 0.26
      
      $text_1 = 'Амиодарон 50мл/мл конц. д/приг. р-р д/в/в 3мл амп. №10';
      $text_2 = 'Амиодарон амп. 50 мл/мл конц. д/приг. р-ра в/в 3 мл №10';
      echo levenshtein_distance($text_1, $text_2) / mb_strlen($text_1)
      // Результат: 0.31

      Если перед вызовом функции добавить нормализацию, то результаты ещё более печальные: 0.07 для первой пары и 0.53 для второй, хотя у второй хочется нулевое расстояние.


      1. sunnybear
        06.11.2022 12:52

        спасибо, но у вас была проблема - при добавлении одного слова метрика сильно ухудшалась. Эта проблема решается нормированием разницы между строками на длину строк. Очевидно, что такой подход не решает некоторые другие проблемы, выявленные в данной статье.


  1. bruma1994
    06.11.2022 13:10

    Браво! От статьи не оторваться)


  1. Kelbon
    06.11.2022 18:34

    1. Дайте людям фотографию примера товара, чтобы они знали что ищут(в статье говорится, что иногда не знают)

    2. Расстояние должно быть смысловым, а не текстовым. Тут можно было ввести теги и т.д., но явно трудоёмко


    1. sepetov Автор
      06.11.2022 19:01
      +1

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

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

      1. Если сборка идёт с помощью ТСД - ваш первый вариант бесспорно отличный! На цветном экране удобно фотки показать. Я так сделал на молочном заводе, где большинство сотрудников цеха не умеют читать по-русски. Они ориентировались по картинкам товаров, хотя я ещё предлагал сделать перевод интерфейса на их родной фарси.

        А если сборка идёт по бумажным сборочным листам? Чёрно-белые фотографии разноцветных лаков и красок? Не пойдёт.

      2. Для бумажной сборки это очень дорого. В моей фармацевтической компании на листочке А4 бывает по 8-9 позиций: столько фотографий не поместится, а печатать кипу бумаг - ещё неудобно с собой таскать.


  1. Didimus
    06.11.2022 20:31
    +1

    Отличная работа. Не пробовали нормализатор названий сделать или найти готовый, примерно как с адресами делают?


    1. sepetov Автор
      06.11.2022 20:35

      Спасибо! На одном складе, где это делалось, к сожалению, больше ничего не предпринималось. На втором месте для товаров был создан мастер создания, который сам делал названия единообразными. Нормализатор - это оно? Если да, то работает, идея отличная. Не знаю, почему я на первом складе сам не додумался сделать.


  1. alisichkin
    06.11.2022 21:23
    +2

    История повторяется ;)
    https://habr.com/ru/post/234723/


    1. sepetov Автор
      07.11.2022 07:08

      Коллега, вы - гений! Ваша работа меня сразила наповал. Мне нечего прокомментировать :-)


    1. alsov
      09.11.2022 01:32
      +1

      тоже N-граммы пришли на ум, пока читал стать. опередили с предложением)

      мне в своё время весьма помогло словарь сделать покороче.

      но у меня была другая предметная область
      https://habr.com/ru/company/dataline/blog/512142/


  1. R72
    06.11.2022 21:38
    +1

    В WMS алгоритмы работают на основе выделенных аналитик к номенклатуре товаров и раскладка в ячейки происходит на основе заранее установленных соответствий между ячейками, аналитиками товара и правилами раскладки.

    Когда вы применили алгоритм на уровне ИИ для оперативного установления этих связей ячейка-аналитики-правила, то вы аналитическую работу по связке, которую делают "до" раскладки перенесли, фактически, в момент самой раскладки.

    Мало того, что алгоритм типа ИИ требует постоянной работы по его подправке за пределами этапа разработки и постоянного непрерывного обучения , что далеко не всегда под силу и квалификацию логистикам, т.е. он фактически всегда "сырой" и выдаёт энный процент ошибок, который, правда, уменьшается с течением, длительным течением времени, так ещё встают вопросы производительности расчета алгоритмов на больших массивах данных (больших складах и/или широкой номенклатуре и объёмных аналитиках).

    Предложенный выше нормализатор куда лучшее решение, а вариант с анализом текста рискованный для бизнеса. Правильно заметили, что если процессы бизнеса ранее были уже отлажены, то новые попытки его улучшить будут выдавать всё меньший и меньший результат. И при этом при всё больших и больших затратах. Закон Парето во всей его красе, 20/80 и 80/20!


    1. sepetov Автор
      07.11.2022 07:18

      Спасибо. Иногда принцип Парето огорчает :-) Хочется космических результатов, а их нет.


  1. CyaN
    08.11.2022 11:58

    И еще одна попытка изобретения НСИ