Функция LEVENSTEIN из статьи доступна во всех версиях !SEMTools, в том числе бесплатной.
Расстояние Левенштейна между двумя строками это наименьшее число правок, которыми одну строку можно превратить в другую. Правка бывает трёх видов: вставить символ, удалить символ или заменить один символ другим, каждая стоит 1. Для «лето» и «лента» расстояние равно 2: вставить «н» и заменить «о» на «а». В Excel такой функции нет, но её можно посчитать вручную на листе или подключить как формулу =LEVENSTEIN(A2;B2) из !SEMTools. Чем меньше число, тем больше строки похожи, поэтому расстояние Левенштейна используют для поиска опечаток и почти одинаковых названий, см. функцию LEVENSTEIN.
Что такое расстояние Левенштейна простыми словами
Метрику придумал советский математик Владимир Левенштейн в 1965 году. Идея простая: считаем минимальное число одиночных правок. Три разрешённые операции:
- вставка: «кот» → «скот», расстояние 1;
- удаление: «скот» → «кот», расстояние 1;
- замена: «кот» → «код», расстояние 1.
Перестановка соседних букв считается двумя правками, а не одной: из «ab» в «ba» нужно заменить две буквы. Регистр важен: «Excel» и «excel» отличаются заменой одной буквы. Сравнивая слова, приводите их к одному регистру, например через СТРОЧН.
| Пара | Расстояние | Почему |
|---|---|---|
| кот и кот | 0 | строки одинаковы |
| кот и код | 1 | заменить «т» на «д» |
| кот и скот | 1 | вставить «с» |
| лето и лента | 2 | вставить «н», заменить «о» на «а» |
| кот и дом | 2 | заменить «к» на «д» и «т» на «м» |
Как считается расстояние: матрица на листе Excel
Вручную расстояние считают по таблице. По горизонтали пишут буквы одной строки, по вертикали буквы другой, а первую строку и первый столбец заполняют числами 0, 1, 2 и так далее: столько правок нужно, чтобы получить пустую строку. Каждая внутренняя ячейка берёт наименьшее из трёх значений: сосед сверху плюс 1 (удаление), сосед слева плюс 1 (вставка), сосед по диагонали плюс 0, если буквы совпали, и плюс 1, если нет (замена). Значение в правом нижнем углу и есть расстояние.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| 1 | л | е | н | т | а | ||
| 2 | 0 | 1 | 2 | 3 | 4 | 5 | |
| 3 | л | 1 | 0 | 1 | 2 | 3 | 4 |
| 4 | е | 2 | 1 | 0=МИН(D3+1;C4+1;C3+(A4<>D1)) | 1 | 2 | 3 |
| 5 | т | 3 | 2 | 1 | 1 | 1 | 2 |
| 6 | о | 4 | 3 | 2 | 2 | 2 | 2 |
В ячейке D4 буквы «е» и «е» совпадают, поэтому из диагональной ячейки C3 берём 0 и прибавляем 0. Формулу в остальные ячейки матрицы можно протянуть с закреплением строки заголовка и столбца букв, ссылка на A4 и D1 смотрит на буквы текущей ячейки.
Ответ 2 стоит в правом нижнем углу, в ячейке G6.
В английском Excel: =MIN(D3+1,C4+1,C3+(A4<>D1))
Для двух слов по пять букв матрица занимает 36 ячеек, для двух фраз по 30 символов уже 961. Считать таблицей десять пар можно, а тысячу нельзя, для этого нужна готовая функция.
Функция LEVENSTEIN в Excel
В !SEMTools функция называется LEVENSTEIN (так в названии, без «h»). Она принимает две строки и возвращает расстояние. Работает как обычная формула, подключается вместе с надстройкой.
| A | B | C | |
|---|---|---|---|
| 1 | Слово | Эталон | Расстояние |
| 2 | эксель | эксель | 0=LEVENSTEIN(A2;B2) |
| 3 | эксил | эксель | 2=LEVENSTEIN(A3;B3) |
| 4 | ексель | эксель | 1=LEVENSTEIN(A4;B4) |
| 5 | таблица | эксель | 7=LEVENSTEIN(A5;B5) |
«эксил» → «эксель»: заменить «и» на «е» и вставить «ь», итого 2. «ексель» отличается первой буквой.
Функция различает регистр, поэтому в нормальной работе оборачивайте обе строки в СТРОЧН: =LEVENSTEIN(СТРОЧН(A2);СТРОЧН(B2)). Пробелы тоже считаются символами, лишние уберёт СЖПРОБЕЛЫ.
Процент сходства строк
Абсолютное расстояние плохо сравнивать между парами разной длины: 2 правки для слова из трёх букв это много, а для фразы из тридцати мало. Поэтому часто считают сходство в процентах, деля расстояние на длину более длинной строки: =1-LEVENSTEIN(A2;B2)/МАКС(ДЛСТР(A2);ДЛСТР(B2)). Результат от 0 до 1, формат ячейки «Процентный». Для «эксил» и «эксель» получится 1 − 2/6, то есть 67%. Длину берёт ДЛСТР.
Порог сходства подбирают на своих данных. Для коротких слов 80% уже означает почти полное совпадение, а на длинных названиях товаров нормой бывает и 60%.
Найти в списке ближайшее значение к искомому
Типичная задача: есть «грязное» название и справочник, нужно найти самое похожее из справочника. Без формул массива это делается вспомогательным столбцом: рядом с каждым значением справочника считаем расстояние до искомого слова и берём минимум.
| A | B | C | D | |
|---|---|---|---|---|
| 1 | Справочник | Расстояние до «мосва» | Результат | |
| 2 | Москва | 1=LEVENSTEIN(СТРОЧН(A2);"мосва") | Москва=ИНДЕКС(A2:A4;ПОИСКПОЗ(МИН(B2:B4);B2:B4;0)) | |
| 3 | Казань | 6=LEVENSTEIN(СТРОЧН(A3);"мосва") | ||
| 4 | Курск | 5=LEVENSTEIN(СТРОЧН(A4);"мосва") |
ПОИСКПОЗ с типом 0 находит позицию наименьшего расстояния, а ИНДЕКС возвращает значение из этой позиции. Если несколько значений одинаково близки, берётся первое.
Если ближайшее значение слишком далеко (например, расстояние больше половины длины слова), его лучше не подставлять. Для этого результат оборачивают в ЕСЛИ и сравнивают минимум с порогом, а пустое значение прячут через ЕСЛИОШИБКА.
Такой поиск «как похоже» подробнее рассматривается в статье нечёткий поиск в Excel.
Ограничения расстояния Левенштейна
- Порядок слов не учитывается как смысл: «Иван Петров» и «Петров Иван» дают большое расстояние. Для сравнения как наборов слов подходит WORDDIFF (пословное расстояние), см. возможности !SEMTools, доступные бесплатно, а для поиска дублей с другим порядком слов процедура неявные дубли.
- Метрика ничего не знает о смысле: «дом» и «лом» близки (расстояние 1), хотя слова разные.
- Число пар растёт быстро: 1000 значений против 1000 это миллион сравнений, формулы на таком объёме считаются долго.
- Падежи и словоформы дают заметное расстояние: «книга» и «книгой» отличаются двумя правками.
Если нужны просто точные повторы, не считайте расстояния, а воспользуйтесь статьёй повторяющиеся значения в Excel.
Расстояние Левенштейна: частые вопросы
Что такое расстояние Левенштейна?
Минимальное число вставок, удалений и замен одного символа, которыми одну строку можно превратить в другую.
Есть ли в Excel функция расстояния Левенштейна?
Встроенной нет. Её можно посчитать матрицей на листе или использовать функцию LEVENSTEIN из надстройки !SEMTools.
Как посчитать расстояние Левенштейна для «лето» и «лента»?
Нужно две правки: вставить «н» и заменить «о» на «а», расстояние равно 2.
Как получить процент сходства строк?
Разделите расстояние на длину более длинной строки и вычтите результат из единицы: =1-LEVENSTEIN(A2;B2)/МАКС(ДЛСТР(A2);ДЛСТР(B2)).
Учитывает ли расстояние Левенштейна регистр?
Да. «Excel» и «excel» отличаются на 1. Приводите строки к одному регистру через СТРОЧН.
Найти почти одинаковые названия, убрать неявные дубли с другим порядком слов, свести похожие значения справочника: такие задачи в !SEMTools решаются процедурами на тысячах ячеек сразу.
!SEMTools решает эту и сотни других задач в пару кликов!
Итоги: расстояние Левенштейна в Excel
Расстояние Левенштейна это число правок между двумя строками, а в Excel его даёт функция LEVENSTEIN. Для сравнения пар разной длины переводите его в процент сходства, а для подбора ближайшего значения используйте вспомогательный столбец с МИН и ПОИСКПОЗ. Другие приёмы поиска похожих значений собраны в статье нечёткий поиск в Excel, а общий список вопросов для начинающих в разделе частые вопросы по Excel.