Блог несуществующего сайта MyWare.Ru: ноября 2010

суббота, 27 ноября 2010 г.

тест

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

ОРИГИНАЛ ТУТ
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') ошибка

Что дальше

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

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

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

Невозможно использовать для исправления "слипшихся" слов (этоошибка), а также разделенного слова (оши бка).

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

вторник, 30 ноября 2010 г.

понедельник, 29 ноября 2010 г.

суббота, 27 ноября 2010 г.

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

Предыстория

Ошибки ввода текста для русского и английского

Ошибки неверной раскладки

Что дальше

четверг, 25 ноября 2010 г.

среда, 24 ноября 2010 г.

понедельник, 22 ноября 2010 г.

воскресенье, 21 ноября 2010 г.

пятница, 19 ноября 2010 г.

среда, 17 ноября 2010 г.

понедельник, 15 ноября 2010 г.

воскресенье, 14 ноября 2010 г.

суббота, 13 ноября 2010 г.

пятница, 12 ноября 2010 г.

четверг, 11 ноября 2010 г.

среда, 10 ноября 2010 г.

вторник, 9 ноября 2010 г.

суббота, 6 ноября 2010 г.

четверг, 4 ноября 2010 г.

вторник, 2 ноября 2010 г.

понедельник, 1 ноября 2010 г.

вторник, 30 ноября 2010 г.

понедельник, 29 ноября 2010 г.

суббота, 27 ноября 2010 г.

четверг, 25 ноября 2010 г.

среда, 24 ноября 2010 г.

понедельник, 22 ноября 2010 г.

воскресенье, 21 ноября 2010 г.

пятница, 19 ноября 2010 г.

среда, 17 ноября 2010 г.

понедельник, 15 ноября 2010 г.

воскресенье, 14 ноября 2010 г.

суббота, 13 ноября 2010 г.

пятница, 12 ноября 2010 г.

четверг, 11 ноября 2010 г.

среда, 10 ноября 2010 г.

вторник, 9 ноября 2010 г.

суббота, 6 ноября 2010 г.

четверг, 4 ноября 2010 г.

вторник, 2 ноября 2010 г.

понедельник, 1 ноября 2010 г.