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

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

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

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

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

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

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

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

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

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

#техпоп #приходько_техпоп