http://www.linguis.ru/art/spell
Спеллчекер простой, доработанный
Как то понадобилось сделать проверку орфографии для вводимых поисковых запросов. При этом хотелось скопировать поведение поисковиков, которые на запрос "ашипка" выдадют: Возможно, вы имели в виду: ошибка. В недолгих поисках наткнулся на статью Питера Норвига, в которой описывается Spellcheker на питоне размером в 30 строк кода. В этой статье показывается, каким образом его можно доработать, чтобы:
- спеллчекер проверял слова на нескольких языках (здесь, на русском и английском);
- выявлял ошибки неверной раскладки (jib,rf -> ошибка).
Предыстория
Для полноты рассказа, привожу оригинальный код, взятый с сайта Питера Норвига.
import re, collections def words(text): return re.findall('[a-z]+', text.lower()) def train(features): model = collections.defaultdict(lambda: 1) for f in features: model[f] += 1 return model NWORDS = train(words(file('big.txt').read())) alphabet = 'abcdefghijklmnopqrstuvwxyz' def edits1(word): s = [(word[:i], word[i:]) for i in range(len(word) + 1)] deletes = [a + b[1:] for a, b in s if b] transposes = [a + b[1] + b[0] + b[2:] for a, b in s if len(b)>1] replaces = [a + c + b[1:] for a, b in s for c in alphabet if b] inserts = [a + c + b for a, b in s for c in alphabet] return set(deletes + transposes + replaces + inserts) def known_edits2(word): return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS) def known(words): return set(w for w in words if w in NWORDS) def correct(word): candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word] return max(candidates, key=NWORDS.get)
Не буду описывать код деталях: любой желающий сможет прочесть оригинальную статью, либо ту же в русском переводе. Если кратко, работа спеллчекера состоит из трех шагов:
- Формируется модель языка. Фактически, это словарь, ключами которого являются допустимые слова языка, а значениями - количество повторений каждого из слов в неком эталонном наборе текстов (корпусе языка).
- Для проверяемого слова составляется множество из всех возможных слов для замены. Это делается с помощью четырех преобразований: удаления, вставки, замены и перестановки.
- В финале, каждый кандидат из построенного множества слов проверяется на наличие в словаре. При этом, выбирается наиболее вероятное слово (т.е. то слово, которое чаще всего встречается в корпусе).
Ошибки ввода текста для русского и английского
Заставить спеллчекер говорить по-русски не составит труда: нужно просто заменить алфавит на русский и использовать русский корпус. Однако, нам необходимо два языка: спеллчекер должен исправлять как русские слова, так и английские.
Один из вариантов решения - расширить английский алфавит русскими буквами: alphabet = 'abcd...абвгд...'. Но этот вариант ведет к побочному эффекту: при формировании кандидатов формируется много лишних слов. К примеру преобразование типа "замены" для слова "карова" даст нам следующие варианты с английской буквой 'r': ['rарова', 'кrрова', 'каrова', 'карrва', 'кароrа', 'каровr'].
Чтобы избежать этого, нам придется выполнить две задачи: 1 - разделить алфавиты, 2 - определить, к какому алфавиту принадлежит проверяемое слово. Разделение реализуем словарем алфавитов, а принадлежность слова к языку будем определять по максимальному совпадению букв слова с имеющимися алфавитами. Код:
alphabets = { 'en':u'abcdefghijklmnopqrstuvwxyz', 'ru':u'абвгдежзийклмнопрстуфхцчшщъыьэюя' } def get_lang(word): return max(alphabets, key=lambda lang: sum(1 for l in word if l in alphabets[lang]))
Принадлежность слова к алфавиту можно было бы определить и полным соответствием всех букв слова какому-либо алфавиту. Однако, такой подход не позволит нам исправлять слова типа 'ошибкаh', т.е. с "вкрапленными" буквами из другого языка.
Итак, первая задача решена. Осталось лишь передать нужный алфавит в функцию edits1 (и known_edits2), а также подправить функцию words c тем, чтобы она выделяла также и русские слова. Исходный файл в юникоде. Соответственно, делаем необходимое преобразование в юникод-строку.
def words(text): return re.findall(u'[a-z]+|[а-я]+', text.decode('utf-8').lower())
Ошибки неверной раскладки
Теперь перейдем к решению второй задачи - определению неверной раскладки. Это можно сделать следующим кодом:
ttable = { 'en':u'qwertyuiop[]asdfghjkl;'zxcvbnm,', 'ru':u'йцукенгшщзхъфывапролджэячсмитьбю' } def translate(word, from_lang): words = [] for to_lang in alphabets: if to_lang == from_lang: continue to, frm = ttable[to_lang], ttable[from_lang] try: words.append(''.join(to[frm.index(char)] for char in word)) except ValueError: pass return words
Функция translate формирует список преобразованных слов, по одному для каждого языка (исключая, естественно, изначальный язык). В случае, если для какой-либо буквы слова не находится соответствие в словаре транслитераций ttable, пропускаем это слово. Все что нам осталось сделать - поместить вызов этой функции в функцию correct, отфильтровав все неизвестные слова функциейknown.
В итоге, полный код нашего спеллчекера будет выглядеть следующим образом:
# -*- coding: utf-8 -*- import re, collections def words(text): return re.findall(u'[a-z]+|[а-я]+', text.decode('utf-8').lower()) def train(features): model = collections.defaultdict(lambda: 1) for f in features: model[f] += 1 return model NWORDS = train(words(file('big.txt').read())) alphabets = { 'en':u'abcdefghijklmnopqrstuvwxyz', 'ru':u'абвгдежзийклмнопрстуфхцчшщъыьэюя' } ttable = { 'en':u'qwertyuiop[]asdfghjkl;'zxcvbnm,', 'ru':u'йцукенгшщзхъфывапролджэячсмитьбю' } def get_lang(word): return max(alphabets, key=lambda lang: sum(1 for l in word if l in alphabets[lang])) def translate(word, from_lang): words = [] for to_lang in alphabets: if to_lang == from_lang: continue to, frm = ttable[to_lang], ttable[from_lang] try: words.append(''.join(to[frm.index(char)] for char in word)) except ValueError: pass return words def edits1(word, lang): alphabet = alphabets[lang] s = [(word[:i], word[i:]) for i in range(len(word) + 1)] deletes = [a + b[1:] for a, b in s if b] transposes = [a + b[1] + b[0] + b[2:] for a, b in s if len(b)>1] replaces = [a + c + b[1:] for a, b in s for c in alphabet if b] inserts = [a + c + b for a, b in s for c in alphabet] return set(deletes + transposes + replaces + inserts) def known_edits2(word, lang): return set(e2 for e1 in edits1(word, lang) for e2 in edits1(e1, lang) if e2 in NWORDS) def known(words): return set(w for w in words if w in NWORDS) def correct(word): lang = get_lang(word) candidates = known([word]) or known(edits1(word, lang)) or known_edits2(word, lang) or known(translate(word, lang)) or [word] return max(candidates, key=NWORDS.get)
Пример использования:
>>> correct(u'ашибка') ошибка >>> correct(u'ашипка') ошибка >>> correct(u'jib,rf') ошибка
Что дальше
Спелчекер вышел простым, и этим он мне очень нравится. Однако, у него есть ряд серьезных недочетов:
- Отсутствует знание о морфологии слова: если в корпусе не встретится словоформа "ошибками", это слово будет считаться ошибочным, и будет исправлено на "ошибка" (извините за тавтологию).
- Значительно увеличивается сложность расчета при исправлении трех и более букв. В приведенном коде мы исправляем только две. Однако, поисковые системы исправляют и большее количество (см. ашипкааа).
- Невозможно использовать для исправления "слипшихся" слов (этоошибка), а также разделенного слова (оши бка).
Но если это делают поисковые системы, значит можем и мы. О том как написать более мощный спеллчекер я расскажу в следующей части.
Комментариев нет:
Отправить комментарий