Реальная статистика опечаток?

Question

Где я могу найти статистику опечаток в реальном мире?

Я пытаюсь сопоставить входной текст людей с внутренними объектами, и люди склонны делать орфографические ошибки.
Есть 2 вида ошибок:

1. typos - "Helllo" вместо "Hello" / "Satudray" вместо "суббота" и т. Д.
2. Spelling - "Шикаго" вместо "Чикаго"

Я использую расстояние Дамерау-Левенштейна для опечаток и двойной метафон для орфографии (реализации Python здесь и здесь).

Я хочу сосредоточиться на Damerau-Levenshtein (или просто edit-distance). Реализации учебника всегда используют "1" для веса удалений, вставок, замен и транспозиций. Хотя это просто и допускает хорошие алгоритмы, оно не соответствует "реальности" / "вероятностям реального мира".

Примеры:

• Я уверен, что вероятность "Helllo" ("Привет") больше, чем "Helzlo", но они оба на расстоянии 1 редактирования.
• "Gello" ближе, чем "Qello" к "Hello" на QWERTY-клавиатуре.
• Транслитерация Unicode: Каково "реальное" расстояние между "München" и "Munchen"?

Какими должны быть веса "реального мира" для удалений, вставок, замен и транспозиций?

Даже очень крутой корректор орфографии Norvig использует невзвешенное расстояние редактирования.

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

Я могу настроить алгоритм, но где я могу "узнать" эти веса? У меня нет доступа к данным Google масштаба...

Должен ли я просто угадать их?

РЕДАКТИРОВАТЬ - пытается ответить на вопросы пользователя:

• Мой текущий невзвешенный алгоритм часто терпит неудачу, когда сталкивается с опечатками по вышеуказанным причинам. "Возвращение в четверг": каждый "реальный человек" может легко сказать, что четверг более вероятен, чем вторник, но они оба на расстоянии одного редактирования! (Да, я регистрирую и измеряю свою производительность).
• Я разрабатываю поисковую систему NLP Travel, поэтому мой словарь содержит ~25 тыс. Пунктов назначения (ожидается рост до 100 тыс.), Выражения времени ~200 (ожидается 1 тыс.), Выражения людей ~100 (ожидается 300), денежные выражения ~100 (ожидается 500)), "склеить логические слова" ("от", "красиво", "квартира") ~2К (ожидается 10К) и так далее...
• Использование расстояния редактирования отличается для каждой из вышеперечисленных групп слов. Я пытаюсь "автоматически исправить, когда это очевидно", например, 1 редактировать расстояние от только 1 другого слова в словаре. У меня есть много других настроенных вручную правил, например, исправление Double Metaphone, которое находится на расстоянии не более 2 от расстояния словарного слова длиной более 4... Список правил продолжает расти, поскольку я учусь на реальных данных.
• "Сколько пар словарных записей находится в пределах вашего порога?": Ну, это зависит от "системы взвешенного воображения" и от ввода реального мира (будущего), не так ли? В любом случае, у меня есть обширные модульные тесты, так что каждое изменение, которое я делаю в системе, только улучшает его (конечно, на основе прошлых данных). Большинство слов длиной менее 6 букв находятся на расстоянии 1 редактирования от слова на расстоянии 1 редактирования от другой словарной статьи.
• Сегодня, когда есть 2 словарные статьи на одинаковом расстоянии от ввода, я пытаюсь применить различные статистические данные, чтобы лучше угадать, что имел в виду пользователь (например, Париж, Франция, скорее всего, будет отображаться в моем поиске, чем Париж, Иран).
• Стоимость выбора неправильного слова - возвращение конечному пользователю полуслучайных (часто нелепых) результатов и потенциальная потеря клиента. Стоимость непонимания немного дешевле: пользователю будет предложено перефразировать.
• Стоит ли стоимость сложности? Да, я уверен, что это так. Вы не поверите количеству опечаток, которые люди бросают в систему, и ожидаете, что она это поймет, и я могу с уверенностью использовать повышение в Precision and Recall.

Answer 1

Возможный источник реальной статистики опечаток будет в полной истории редактирования Википедии.

http://download.wikimedia.org/

Также вас может заинтересовать RegExTypoFix AWB

http://en.wikipedia.org/wiki/Wikipedia:AWB/T

Answer 2

Я бы посоветовал вам проверить трилогограмму алогрита. На мой взгляд, он лучше работает для поиска опечаток, чем для редактирования алгоритма расстояния. Он также должен работать быстрее, и если вы храните словарь в базе данных postgres, вы можете использовать индекс.

Вы можете найти полезную тему стекопотока о Google "Вы имели в виду"

Answer 3

Может помочь оценка вероятности исправления орфографии Церковью и Гейлом. В этой статье авторы моделируют опечатки как шумный канал между автором и компьютером. В приложении есть таблицы опечаток, которые можно увидеть в корпусе публикаций Associated Press. Существует таблица для каждого из следующих видов опечаток:

• удаление
• вставка
• замена
• перестановка

Например, изучая таблицу вставок, мы видим, что l было вставлено неправильно после l 128 раз (наибольшее число в этом столбце). Используя эти таблицы, вы можете сгенерировать искомые вероятности.

Answer 4

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

Я не могу помочь вам со статистикой опечаток, но я думаю, что вы также должны играть с difflib Python. В частности, метод ratio() для SequenceMatcher. Он использует алгоритм, который заявка docs http://docs.python.org/library/difflib.html хорошо подходит для совпадений, которые выглядят "правильно", и может быть полезен для дополнения или проверки того, что вы делаете.

Для программистов на Python, которые просто ищут опечатки, это хорошее место для начала. Один из моих коллег использовал как расстояние редактирования Левенштейна, так и отношение SequenceMatcher (), и получил гораздо лучшие результаты от коэффициента ().

Answer 5

Несколько вопросов, которые помогут вам определить, следует ли вам задавать вопрос "где я могу найти веса в реальном мире":

Вы на самом деле измерили эффективность реализации равномерного взвешивания? Как?

Сколько разных "внутренних объектов" у вас есть, т.е. каков размер вашего словаря?

Как вы на самом деле используете расстояние редактирования, например, Джон / Джоан, Мармадьюк / Мармедюк, Фезерстоунхау / Фезерстонхаух: это "ошибка всех 1" или разница 25% / 11,1% / 5,9%? Какой порог вы используете?

Сколько пар словарных записей находится в пределах вашего порога (например, Джон против Джоан, Джоан против Хуана и т. Д.)? Если бы вы внедрили причудливую систему весов, сколько пар словарных статей мигрировало бы (а) из порога во внешний (б) и наоборот?

Что делать, если в вашем словаре есть и Джон, и Хуан, а пользователь вводит Джоан?

Каковы штрафы / издержки (1) выбора неправильного словарного слова (а не того, которое имел в виду пользователь) (2) не распознавания ввода пользователя?

Будет ли введение сложной системы весов фактически уменьшить вероятности вышеупомянутых двух типов ошибок с достаточным запасом, чтобы оправдать усложнение и более медленную скорость?

Кстати, как узнать, какую клавиатуру использовал пользователь?

Обновить:

"" "Мой текущий невзвешенный алгоритм часто дает сбой при обнаружении опечаток по вышеуказанным причинам." Возвращение в четверг ": каждый" реальный человек "может легко сказать, что четверг более вероятен, чем вторник, но оба они - 1-edit-distance прочь! (Да, я регистрирую и измеряю свою производительность)."""

Да, четверг -> четверг, опуская "h", но вторник -> четверг, подставляя "r" вместо "e". E и R находятся рядом друг с другом на клавиатурах qwERty и azERty. Каждый "настоящий человек" может легко догадаться, что четверг более вероятен, чем вторник. Даже если статистика и предположения указывают на то, что четверг будет более вероятным, чем вторник (возможно, отсутствие h будет стоить 0.5, а e->r будет стоить 0,75), будет ли разница (возможно, 0,25) достаточно значимой, чтобы всегда выбирать четверг? Может ли ваша система спросить "Вы имели в виду вторник?" или будет / пойдет ли вперед с четверга?