Компьютер — штука очень глупая. Например, человеку очевидно, что «корова» и «Корова» — это одно и то же слово и даже если сделать в слове ошибку и написать «карова», мы все равно догадаемся, что имелось ввиду. Не таковы компьютерные программы, поменяй одну букву — машина будет уверена, что перед ней новое слово. Это здорово осложняет дело, когда приходится работать с данными, собранными на просторах Интернета, как например, в тьюториале «Корпус из твитов своими руками».
Однако есть способ научить компьютер сравнивать слова и вычислять степень их похожести по тому, сколько нужно вставить, удалить или заменить символов, чтобы получить из одного слова другое. Способ был придуман советским математиком Владимиром Левенштейном, статья которого с момента публикации в 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('солоный')] # Проверим, найдется ли в табличке слово "солоный". После замены на "соленый" его там быть не должно и следующий код должен выдать пустую табличку.Материалы
- Полный код на Github
- Корпус из твитов своими руками
- Levenshtein, Vladimir I. «Binary codes capable of correcting deletions, insertions, and reversals.»
- Картография и хронология жадин, N+1
- Картография жадин-говядин, блог N+1
- Peter Norvig How to Write a Spelling Corrector
- Лекция Александра Пиперски о расстояниях Хэмминга и Левенштейна
