История опечатки в реальном мире?

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

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

  • typos - "Helllo" вместо "Hello" / "Satudray" вместо "Saturday" и т.д.
  • Spelling - "Шикаго" вместо "Чикаго"

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

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

Примеры:

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

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

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

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

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

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

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

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

Ответы

Ответ 2

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

Вы можете найти полезный stackoverflow тему о Google "Возможно, вы имели в виду"

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

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

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

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

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

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

Update:

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

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