Калькулятор відстані Левенштейна

Цей онлайн-калькулятор вимірює відстань Левенштейна між двома рядками.

Відстань Левенштейна (або відстань редагування) між двома рядками — це кількість видалень, вставок або замін, необхідних для перетворення вихідного рядка в цільовий. Наприклад, якщо вихідний рядок — «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 спеціалісту швидко згенерувати список урлів для створення таблиць 301 редиректів зі старої адресу на нову.

Просто введіть у поле «Старі URL (один на рядок)» старі адреси, а в поле «Нові URL (один на рядок)» нові – після чого виставте повзунок мінімальної схожості та порівняйте для отримання результату.

Також, після перевірки всіх URL адрес ви можете зробити експорт даних у CSV таблицю в один клік.

Важливо знати, про інструмент «Калькулятор відстані Левенштейна онлайн» від SEOGeeks:

• перевірка до 1000 URL відбувається миттєво за допомогою JS.
• перевірка більшої кількості адрес відбувається за допомогою серверного обчислювання, але данні на сервері НЕ зберігаються.