Евгений Приходько
89

[Техпоп] Расстояние Левенштейна для работы с текстом — как найти, насколько похожи две строки

Что это, зачем это и как я это использовал в реальном проекте.

В закладки

Что это?

Здесь можно просто пересказать википедию. Расстояние Левенштейна — это количество простых операций над символами, которое нужно сделать с одной строкой, чтобы получить другую. Под простыми операциями я имею в виду замену, вставку и удаление символов. Названо в честь Владимира Левенштейна, который в 1965 году начал заниматься подобными задачами.

Например, расстояние между словами «корона» и «корова» равно 1 — нужно заменить один символ, чтобы из одного получить второе. «лол» в «ололо» можно превратить за два шага, а «муха» в «слон» превращается за 4 шага — у них вообще ни одной буквы не совпадает.

Зачем это?

Ну, раз тут сравниваются строки, то скорее всего это как-то полезно при работе с текстом. Википедия говорит, что это используется, например, при поиске опечаток и даже при сравнении цепочек генов — их тоже можно представить в виде последовательностей символов.

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

Проблема в том, что команда локализации и команда художников работают относительно независимо. Локализаторы переводят названия предметов, а потом через инструменты локализации добавляют их в игру. Художники делают предметы и добавляют их в игру через другие инструменты. Иногда из-за этого появляются опечатки в ключах локализации — либо у художников, либо у локализаторов. Причем опечатки обычно всего в одном символе. SuperCoolItems вместо SuperCoolItem. Или BFG9000large вместо BFG9000Large. Из-за того, что реальный ключ не совпадает с тем, что есть в системе локализации, получается баг.

​Получаются косяки вроде такого. Это просто пример, я не разрабатывал Tyranny. Steam Community

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

Алгоритм

А хз, если честно, какой там алгоритм. В моем коде на Java это выглядит так:

LevenshteinDistance levenshteinDistance = LevenshteinDistance.getDefaultInstance(); Integer distance = levenshteinDistance.apply(keyname, existingKeyname);

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

Котики просто так Instagram
Работаю в геймдеве. Пишу обо всём подряд, веду рубрики #техпоп и #когнитивочка
{ "author_name": "Евгений Приходько", "author_type": "self", "tags": [], "comments": 1, "likes": 11, "favorites": 2, "is_advertisement": false, "subsite_label": "unknown", "id": 123135, "is_wide": true, "is_ugc": true, "date": "Sat, 11 Apr 2020 12:49:12 +0300", "is_special": false }
Объявление на DTF
0
1 комментарий
Популярные
По порядку
2

Оч крутая инфа!
Спасибо, пищи есчо

Ответить

Комментарии

{ "jsPath": "/static/build/dtf.ru/specials/DeliveryCheats/js/all.min.js?v=05.02.2020", "cssPath": "/static/build/dtf.ru/specials/DeliveryCheats/styles/all.min.css?v=05.02.2020", "fontsPath": "https://fonts.googleapis.com/css?family=Roboto+Mono:400,700,700i&subset=cyrillic" }
null