Калькулятор расстояния Левенштейна
Этот онлайн-калькулятор измеряет расстояние Левенштейна между двумя строками.
Расстояние Левенштейна (или расстояние редактирования) между двумя строками — это количество удалений, вставок или замен, необходимых для преобразования исходной строки в целевую. Например, если исходная строка — «book», а целевая строка — «back», чтобы преобразовать «book» в «back», нужно изменить первую «o» на «a», вторую «o» на «c», без дополнительных удалений и вставок. Таким образом, расстояние Левенштейна между «book» и «back» будет равно 2.
Более подробную информацию об алгоритме расстояния Левенштейна и его применении можно найти под калькулятором.
Алгоритмы расстояния Левенштейна и их применение
Расстояние Левенштейна между двумя строками a, b (длиной |a| и |b| соответственно) определяется как lev(a,b), где
{\displaystyle \qquad \operatorname {lev} (a,b)={\begin{cases}|a|& {\text{ если }}|b|=0,\\|b|&{\text{ если }}|a|=0,\\\ operatorname {lev} (\operatorname {tail} (a),\operatorname {tail} (b))&{\text{ если }}a[0]=b[0]\\1+\min {\begin{cases}\operatorname {lev} (\operatorname {tail} (a),b)\\\operatorname {lev} (a,\operatorname {tail} (b))\\\operatorname {lev} (\operatorname {tail} (a),\operatorname {tail} (b))\\\end{cases}}&{\text{ в противном случае.}}\end{cases}}}.
Расстояние Левенштейна названо в честь ученого Владимира Левенштейна, который разработал эту метрику в 1965 году.
Существует несколько алгоритмов для вычисления расстояния Левенштейна:
- Рекурсивный; простой алгоритм, соответствующий определению
- Итеративный с полной матрицей; используемый в калькуляторе выше
- Итеративный с двумя строками матрицы
Более подробную информацию и псевдокодовые реализации для всех алгоритмов можно найти в статье Википедии «Расстояние Левенштейна».
Было доказано, что расстояние Левенштейна не может быть вычислено за время, значительно превышающее квадратичное, что делает его использование для сравнения длинных строк непрактичным, поскольку вычислительные затраты будут пропорциональны произведению длин строк. Однако расстояние редактирования может быть использовано для поиска совпадений короткой строки, например, взятой из словаря, в длинной строке. Это полезно для программ проверки орфографии, систем коррекции оптического распознавания символов и подобных продуктов.
Также вы можете использовать наш онлайн инструмент расстояния Левенштейна в направлении сопоставления URL-адресов, что поможет вам как SEO, Marketing специалисту быстро сгенерировать список URL-адресов для создания таблиц 301 редиректов со старого адреса на новый.
Просто введите в поле «Старые URL (один на строку)» старые адреса, а в поле «Новые URL (один на строку)» новые — после чего выставьте ползунок минимального сходства и сравните для получения результата.
Также, после проверки всех URL-адресов вы можете экспортировать данные в CSV-таблицу в один клик.
Важно знать об инструменте «Калькулятор расстояния Левенштейна онлайн» от SEOGeeks:
- проверка до 1000 URL происходит мгновенно с помощью JS.
- проверка большего количества адресов происходит с помощью серверного вычисления, но данные на сервере НЕ сохраняются.