Справочная информация о реальном мире?

Question

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

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

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

Я использую Damerau-Levenshtein distance для опечаток и Double Metaphone для проверки орфографии (реализации Python here и here).

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

Примеры:

• Я уверен, что вероятность "Helllo" ("Hello") больше, чем "Helzlo", но они оба-редактировать расстояние.
• «Gello» ближе, чем «Qello» к «Hello» на клавиатуре QWERTY.
• Юникодские транслитерации: что такое «реальное» расстояние между «Мюнхен» и «Мюнхен»?

В чем должны быть веса «реального мира» для делеций, вставок, замещений и транспозиций?

Даже Norvig's very cool spell corrector использует невесомое расстояние редактирования.

BTW- Я уверен, что весовые коэффициенты должны быть функции, а не простые поплавки (в приведенных выше примерах ) ...

я могу настроить алгоритм, но где я могу «изучить» эти веса? Я не имею доступа к Google-scale data ...

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

EDIT - пытается ответить на вопросы пользователей:

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

Answer 1

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

http://download.wikimedia.org/

Кроме того, вы можете быть заинтересованы в RegExTypoFix ДСА в

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

Answer 2

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

Вы можете найти полезную StackOverflow topic о Google «Вы имели в виду»

Answer 3

Некоторые вопросы для вас, чтобы помочь вам определить, нужно ли спрашивать ваш «где я могу найти реальных весов» вопрос:

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

Сколько разных «внутренних объектов» у вас есть - например, какой размер вашего словаря?

Как вы на самом деле используете расстояние редактирования, например? John/Joan, Marmaduke/Marmeduke, Featherstonehaugh/Featherstonhaugh: это «все 1 ошибка» или разница 25%/11.1%/5.9%? Какой порог вы используете?

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

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

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

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

BTW, откуда вы знаете, какую клавиатуру пользовался пользователь?

Update:

«» "Моя текущая невзвешенная алгоритм не может часто, сталкиваясь с опечатками по указанным выше причинам.„Возвращение на Tursday“: каждый„реальный человек“может легко сказать четверг, скорее всего, чем во вторник , но они оба находятся на расстоянии 1 отредактирования от расстояния (да, я регистрирую и измеряю свою работу). "" "

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

Answer 4

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

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

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

Answer 5

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

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

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