Спеллчекер простой, доработанный

Как то понадобилось сделать проверку орфографии для вводимых поисковых запросов. При этом хотелось скопировать поведение поисковиков, которые на запрос "ашипка" выдадют: Возможно, вы имели в виду: ошибка. В недолгих поисках наткнулся на статью Питера Норвига, в которой описывается 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')
ошибка

Что дальше

Спелчекер вышел простым, и этим он мне очень нравится. Однако, у него есть ряд серьезных недочетов:

Отсутствует знание о морфологии слова: если в корпусе не встретится словоформа "ошибками", это слово будет считаться ошибочным, и будет исправлено на "ошибка" (извините за тавтологию).
Значительно увеличивается сложность расчета при исправлении трех и более букв. В приведенном коде мы исправляем только две. Однако, поисковые системы исправляют и большее количество (см. ашипкааа).
Невозможно использовать для исправления "слипшихся" слов (этоошибка), а также разделенного слова (оши бка).

Но если это делают поисковые системы, значит можем и мы. О том как написать более мощный спеллчекер я расскажу в следующей части.

Oбработка текста