Создание проверки орфографии с помощью Solr

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

Наша стратегия состоит в том, чтобы использовать специальный индекс Lucene и запрашивать его, используя нечеткие запросы, чтобы получить список кандидатов. Затем мы собираемся ранжировать кандидатов с помощью скрипта Python (который можно легко преобразовать в подкласс проверки правописания Solr, если мы получим лучшие результаты).

Выбор кандидата

Нечеткие запросы исторически считались запросами с низкой производительностью по сравнению с другими, но, поскольку они были оптимизированы в версии 1.4, они являются хорошим выбором для первой части нашего алгоритма. Итак, идея будет очень простой: мы собираемся создать индекс Lucene, где каждый документ будет словарным словом. Когда нам нужно исправить слово с ошибкой, мы собираемся выполнить простой нечеткий запрос этого слова и получить список результатов. Результатами будут слова, похожие на те, что мы предоставили (т.е. с небольшим расстоянием редактирования). Я обнаружил, что примерно с 70 кандидатами мы можем получить отличные результаты.

С нечеткими запросами мы покрываем все опечатки, потому что, как я сказал в предыдущем посте, большинство опечаток имеют расстояние редактирования 1 относительно правильного слова. Но хотя это самая распространенная ошибка, которую люди допускают при наборе текста, существуют и другие виды ошибок.

Мы можем найти три типа орфографических ошибок [Кукич] :

1. Типографские ошибки
2. Когнитивные ошибки
3. Фонетические ошибки

Типографские ошибки — это опечатки, когда люди знают правильное написание, но при наборе текста нарушается координация движений. Когнитивные ошибки — это ошибки, вызванные незнанием человека. Наконец, фонетические ошибки — это особый случай когнитивных ошибок, которые являются словами, которые звучат правильно, но являются орфографически неправильными. Мы уже покрыли типографские ошибки нечетким запросом, но мы также можем что-то сделать для фонетических ошибок. Solr имеет в своем аналитическом пакете фонетический фильтр, который, помимо прочего, имеет алгоритм двойной метафоны. Таким же образом мы выполняем нечеткий запрос, чтобы найти похожие слова, мы можем индексировать метафоновый эквивалент слова и выполнять нечеткий запрос для него.Мы должны вручную получить метафоновый эквивалент слова (поскольку анализатор запросов Lucene не анализирует нечеткие запросы) и создать нечеткий запрос с этим словом.

В двух словах, для выбора кандидата мы строим индекс со следующей схемой solr:

<fieldType name="spellcheck_text" class="solr.TextField" positionIncrementGap="100" autoGeneratePhraseQueries="true">
      <analyzer type="index">
        <tokenizer class="solr.KeywordTokenizerFactory"/>
        <filter class="solr.LowerCaseFilterFactory"/>
        <filter class="solr.PhoneticFilterFactory" encoder="DoubleMetaphone" maxCodeLength="20" inject="false"/>
     </analyzer>
    </fieldType>

   <field name="original_word" type="string" indexed="true" stored="true" multiValued="false"/>
   <field name="analyzed_word" type="spellcheck_text" indexed="true" stored="true" multiValued="false"/>
   <field name="freq" type="tfloat" stored="true" multiValued="false"/>

Как вы можете видеть, поле analysis_word содержит слово «звуки». Поле freq будет использовано на следующем этапе алгоритма. Это просто частота термина в языке. Как мы можем оценить частоту слова в языке? Подсчет частоты слова в большом текстовом корпусе. В этом случае источником терминов является википедия, и мы используем TermComponents Solr, чтобы подсчитать, сколько раз каждый термин появляется в википедии.

Но Википедия написана простыми людьми, которые делают ошибки! Как мы можем доверять этому как «правильному словарю»? Мы используем «коллективное знание» людей, которые пишут Википедию. В этом словаре терминов, извлеченных из Википедии, много терминов! Более 1.800.00, и большинство из них даже не слова. Вполне вероятно, что слова с высокой частотой правильно написаны в Википедии. Такой подход построения словаря из большого набора слов и считая правильными наиболее часто встречающиеся, не нов. В [Cucerzan] они используют ту же концепцию, но используют журналы запросов для построения словаря. Похоже, что Google «Вы имели в виду» используют аналогичную концепцию .

Мы можем добавить небольшие оптимизации здесь. Я обнаружил, что мы можем удалить некоторые слова и получить хорошие результаты. Например, я удалил слова с частотой 1 и слова, начинающиеся с цифр. Мы можем продолжить удаление слов на основе других критериев, но мы оставим это так.

Таким образом, процедура построения индекса проста, мы извлекаем все термины из индекса википедии через членский состав Terr, а также частоты, а затем создаем индекс в Solr, используя SolrJ.

Рейтинг кандидатов

Теперь рейтинг кандидатов. Для второй фазы алгоритма мы собираемся использовать теорию информации, в частности, модель зашумленных каналов . Канал с шумом, применяемый к этому случаю, предполагает, что человек знает правильное написание слова, но некоторый шум в канале вносит ошибку, и в результате мы получаем другое слово с ошибкой. Мы интуитивно знаем, что очень маловероятно, что мы получим «sarasa» при попытке напечатать «house», поэтому модель с шумным каналом вводит некоторую формальность в нахождение вероятности ошибки.
Например, мы неправильно написали «houze» и хотим знать, какое слово является наиболее вероятным для ввода. Для этого у нас есть большой словарь возможных слов, но не все из них одинаково вероятны. Мы хотим получить слово с наибольшей вероятностью того, что оно предназначено для ввода. В математике это называется условной вероятностью; учитывая, что мы ввели «houze», насколько высока вероятность того, что каждое из правильных слов будет тем словом, которое мы намеревались. Обозначение условной вероятности: P («дом» | «houze»), обозначающее вероятность «дом» при «houze».

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

Мы должны максимизировать эту вероятность и для этого у нас есть только один параметр: правильное слово-кандидат («дом» в показанном случае).

По этой причине вероятность ошибочного слова будет постоянной, и мы не заинтересованы в этом. Формула сводится к

И чтобы добавить больше структуры к этому, ученые назвали эти два фактора. Коэффициент P (‘houze’ | ‘house’) — это модель ошибок (или модель канала), которая связана с вероятностью того, что канал вводит этот конкретный орфографический пробел при попытке написать второе слово. Второй термин P («дом») называется моделью языка и дает нам представление о том, насколько распространено слово в языке.

До этого момента я только представил математические аспекты модели. Теперь нам нужно придумать конкретную модель этих двух вероятностей. Для языковой модели мы можем использовать частоту термина в текстовом корпусе. Эмпирически я обнаружил, что гораздо эффективнее использовать логарифм частоты, а не только частоту. Может быть, это потому, что мы хотим уменьшить вес очень частых терминов больше, чем менее частых, и логарифм делает именно это.

Существует не только один способ построения модели канала. Было предложено много разных идей. Мы собираемся использовать простой, основанный на расстоянии Дамерау-Левенштейна. Но также я обнаружил, что нечеткий запрос первого этапа хорошо помогает в поиске кандидатов. Это дает правильное слово в первую очередь в более чем половине тестовых случаев с некоторыми наборами данных. Таким образом, модель Channel будет представлять собой комбинацию расстояния Дамерау-Левенштейна и балла, который Lucene создал для условий нечеткого запроса.

Формула ранжирования будет:

Я запрограммировал небольшой скрипт (python), который делает все, что было сказано ранее:

from urllib import urlopen
import doubleMethaphone
import levenshtain
import json

server = "http://benchmarks:8983/solr/testSpellMeta/"

def spellWord(word, candidateNum = 70):
    #fuzzy + soundlike
    metaphone = doubleMethaphone.dm(word)
    query = "original_word:%s~ OR analyzed_word:%s~" % (word, metaphone[0])

    if metaphone[1] != None:
        query = query + " OR analyzed_word:%s~" % metaphone[1]

    doc = urlopen(server + "select?rows=%d&wt=json&fl=*,score&omitHeader=true&q=%s" % (candidateNum, query)).read( )
    response = json.loads(doc)
    suggestions = response['response']['docs']

    if len(suggestions) > 0:
        #score
        scores = [(sug['original_word'], scoreWord(sug, word)) for sug in suggestions]
        scores.sort(key=lambda candidate: candidate[1])
        return scores
    else:
        return []

def scoreWord(suggestion, misspelled):
    distance = float(levenshtain.dameraulevenshtein(suggestion['original_word'], misspelled))
    if distance == 0:
        distance = 1000
    fuzzy = suggestion['score']
    logFreq = suggestion['freq']

    return distance/(fuzzy*logFreq)

Из предыдущего списка я должен сделать несколько замечаний. В строках 2 и 3 мы используем сторонние библиотеки для алгоритмов расстояния и метафона Левенштейна . В строке 8 мы собираем список из 70 кандидатов. Этот конкретный номер был найден опытным путем. С более высокими кандидатами алгоритм медленнее, а с меньшим — менее эффективным. Мы также исключаем слово с ошибкой из списка кандидатов в строке 30. Поскольку мы использовали википедию в качестве источника, часто слово с ошибкой встречается в словаре. Поэтому, если расстояние Левештейна равно 0 (то же слово), мы добавляем 1000 к его расстоянию.

тесты

Я провел несколько тестов с этим алгоритмом. Первый будет использовать набор данных, который Питер Норвиг использовал в своей статье. Я нашел правильное предложение слова в первой позиции примерно в 80% случаев !!! Это действительно хороший результат. Norvig с тем же набором данных (но с другим алгоритмом и набором обучения) получил 67%

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

FAWTHROP1DAT.643

45,61%

81,91%

31,50

74,19

79,58%

135,55%

batch0.tab

28,70%

56,34%

21,95

47,05

96,30%

114,34%

SHEFFIELDDAT.643

60,42%

86,24%

19,29

35,12

42,75%

82,06%

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

Будущая работа

Как мы можем улучшить эту проверку орфографии. Что ж, изучая список кандидатов, можно обнаружить, что правильное слово обычно (95% случаев) содержится в нем. Поэтому все наши усилия должны быть направлены на улучшение алгоритма подсчета очков.

У нас есть много способов улучшить модель канала; Несколько работ показывают, что вычисление более сложных расстояний, взвешивающих различные преобразования букв в соответствии со статистикой языка, может дать нам лучшую меру. Например, мы знаем, что написание «houpe» менее вероятно, чем написание «houze».

Для языковой модели можно добиться значительных улучшений, добавив больше контекста к слову. Например, если мы неправильно написали «nouse», очень трудно сказать, что правильным словом является «дом» или «мышь». Но если мы добавим больше слов «нарисуй мою носик», очевидно, что слово, которое мы искали, было «дом» (если только у тебя нет странных привычек с участием грызунов). Они также называются нграммами (но в данном случае это слова, а не буквы). Google предложил большую коллекцию нграмм, доступных для скачивания, с их частотами.

Наконец, что не менее важно, производительность можно улучшить, запрограммировав скрипт на языке Java. Часть алгоритма была на питоне.

До свидания!

Как обновление для всех вас, Роберт Мьюр  сказал мне  в списке пользователей Solr, что есть новая проверка орфографии, DirectSpellChecker, которая была в стволе тогда и сейчас должна быть частью Solr 3.1. Он использует технику, аналогичную той, которую я представил в этой записи, без потери производительности.

Ссылки

[Кукич] Карен Кукич — Методы автоматической коррекции слов в тексте — ACM Computing Surveys — Том 24, выпуск 4, декабрь 1992 г.

[Cucerzan] S. Cucerzan и E. Brill Исправление орфографии как итерационный процесс, который использует коллективные знания веб-пользователей. Июль 2004

Питер Норвиг — Как написать корректор орфографии