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

Однако есть способ научить компьютер сравнивать слова и вычислять степень их похожести по тому, сколько нужно вставить, удалить или заменить символов, чтобы получить из одного слова другое. Способ был придуман советским математиком Владимиром Левенштейном, статья которого с момента публикации в 1965 году была процитирована более 10 тысяч раз.

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

Посмотрим, что можно сделать с помощью расстояния Дамерау-Левенштейна на реальных примерах.

Жадина-говядина vs. соленый огурец

Данные, с которыми мы будет работать, для этой статьи любезно предоставила редакция портала N+1. Это небольшой фрагмент датасета, собранного для исследования региональных вариантов детской дразнилки про «жадину-говядину».

Данные собирали через онлайн-анкету, которую заполняли читатели. Всего анкета собрала 40,5 тысячи ответов, в которых, как отмечают авторы, встретилось множество опечаток.

Для вылавливания всевозможных опечаток во всех словах большого объема текстов понадобится полноценный спеллчекер, но когда важно одно или несколько слов, расстояние Дамерау-Левенштейна вполне пригодится

Разных написаний «Москвы» в нашем фрагменте не встретилось, поэтому посмотрим, как можно было бы выловить и исправить опечатки в самом частотном варианте продолжения дразнилки: «соленый огурец».

Что понадобится?

Среда для работы с Python Jupyter Notebook. Если вы хотите запускать код у себя на компьютере, прочитать, как его устанавливать, можно здесь. Более простой вариант — попробовать код в приложении Google Colaboratory (как это можно сделать, описано в нашем Github репозитории). Перед этим скачайте данные и положите в папку edit_distance на своем гугл-диске.

Мы будем использовать библиотеки
fuzzywuzzy — для вычисления расстояния Дамерау-Левенштейна и дополнительными фукнциями, упрощающими работу;
pandas — для работы с таблицей;
re — для использования регулярных выражений;
string — из нее нам пригодится латинский алфавит;

Если не знаете, как устанавливать библиотеки в Python, не пугайтесь, Интернет полон различных гайдов о том, как это делать. Например, тут.

Шаг 0

Загружаем библиотеки:

import pandas as pd
import re
from fuzzywuzzy import fuzz
import string

Шаг 1

df = pd.read_csv(впишите путь к файлу) #  Загружаем .csv-файл с данными. Предполагается, что он лежит на гугл-диске в папке edit_distance

Шаг 2

Пишем функцию для разбиения фрагментов текста на слова с использованием магии регулярных выражений. Функция — это набор команд для решения какой-то небольшой подзадачи. Она принимает данные на вход и выдает результат. Набор команд можно описать один раз, а дальше вызывать функцию, используя только ее имя. Если выбирать понятные имена, то использование функций делает код более читаемым. Пока функция только одна, польза от нее не очевидна, но к концу тьюториала она станет более заметной. В питоне функция задается с помощью ключевого слова def.

def tokenize(text):
  return re.findall(r'[^\w\s]+|\w+', text) 

tokenize("солёный огурец, на полу валяется, никто её не ест") # функция tokenize принимает на вход текст и разбивает его на слова и знаки препинания

['солёный',
 'огурец',
 ',',
 'на',
 'полу',
 'валяется',
 ',',
 'никто',
 'её',
 'не',
 'ест']

Шаг 3

Теперь можно искать огурцы, задействуя расстояние Левенштейна: сравним каждое слово в строке, разбитой на слова, с искомым.

fuzz.ratio выдает число, которое характеризует степень схожести слов.

В функции ниже задано условие: выбрать только те слова, для которых степень схожести с исходным не меньше 75. Значение подобрано эмпирически: 100%-ное совпадение нам не нужно, раз мы ищем опечатки, поэтому можно уменьшать значение, пока функция не начнет выдавать слишком далекие от искомого слова.

def find_variation(tokenized_string, standard):
  for word in tokenized_string:
    if fuzz.ratio(standard, word) > 75: # Можно поменять это значение и посмотреть, что будет.
      return word

find_variation(tokenize("солёный агурец, на полу валяется, никто её не ест"), "огурец") # функция find_variation принимает на вход строку, разбитую на слова, и слово, которое будет образцом для поиска похожих слов

'агурец'

Шаг 4

Теперь напишем функцию, которая пройдется по всей таблице и поймает вариации на тему искомого слова.

def find_all_variations(standard, df):
  variations = []
  for index, row in df.iterrows():
    row[1] = row[1].lower().replace('ё', 'е') # делаем все буквы в строке строчными и заменяем "ё" на "е"
    tokenized = tokenize(row[1])
    variation = find_variation(tokenized, standard)
    if variation:
      variations.append(variation)
  return set(variations)

Шаг 5

Посмотрим, как всё работает вместе:

standard = ‘огурец’ # в качестве слова-образца возьмем “огурец”
variations = set(find_all_variations(standard, df))
print(variations)

{'огуоец', 'огурцом', 'огурец'}

Вариантов написания слова «огурец» не так много, зато какое разнообразие «соленых»!

standard = 'соленый'
variations = set(find_all_variations(standard, df))
print(variations)

{'соленым', 'солоный', 'cоленый', 'соленый', 'соленный', 'солный', 'слоеный'}

Шаг 6

В этом списке смущают две вещи:

во-первых, «слоеный» — в данном случае будем считать его тоже опечаткой,

во-вторых, похожие как две капли воды «соленый» и «соленый». Видимо, чем-то они все же различаются, посмотрим не затесалось ли там латиницы.

for word in variations:
  for letter in word:
    if letter in string.ascii_letters: # в питоне есть встроенный список латинских символов, используем его; в принципе он эквивалентен регулярному выражению [a-zA-Z]
      print("Нашлась латинская буква \"{}\" в слове \"{}\"".format(letter, word))

Нашлась латинская буква "c" в слове "cоленый"

Шаг 7

Теперь можно приводить все это разнообразие к единому написанию.

variations_to_replace = {
   'огуоец': 'огурец',
   'соленный': 'соленый',
   'солный': 'соленый',
   'слоеный': 'соленый',
   'солоный': 'соленый',
   'cоленый': 'соленый' # заменим слово с латиницей на слово с кириллицей, хотя выглядят они одинаково
}

df["text"].replace(variations_to_replace, regex=True, inplace=True)

Проверка

df[df['text'].str.contains('солоный')] # Проверим, найдется ли в табличке слово "солоный". После замены на "соленый" его там быть не должно и следующий код должен выдать пустую табличку.

Материалы