Применение расстояния Левенштейна с целью оптимизации работы склада06.11.2022 10:17

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

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

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

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

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

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

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

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

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

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

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

Реализация сделана так, что сотрудник приёмки при поступлении нового товара автоматически получал от 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 г». Давайте зацепимся за этот факт?

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

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

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% — это уже миллионы экономии в год. Когда бизнес-процессы предприятия уже хорошо отработаны, других результатов ждать не стоит даже от самых хитроумных алгоритмов. Но вы всегда пытайтесь!

© Habrahabr.ru