Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 28.01.2011, 13:42
Новичок

Отправить личное сообщение для zhazhah Посмотреть профиль Найти все сообщения от zhazhah
 
Регистрация: 28.01.2011
Сообщений: 7

Проверка орфографии, реализация алгоритма..
Здравствуйте. Каким образом можно сделать проверку орфографии. По какому принципу вообще проверка орфографии работает....?
У меня есть словарь 160 000 слов
Я сделал простенькую программу в которой загружаю весь словарь и в цикле делаю проверку с каждым словом... исправляет довольно не плохо

срвчник => справочник

но для обработки одного слова требуется 300 мс... это очень долго..
при том что словарь ёще маленький...
  #2  
Старый 28.01.2011, 13:54
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

1. Выполнять проверку сторонними библиотеками (например, из MS Ofiice или Open Office)
2. простой алгоритм коррекции небольшого числа ошибок - гуглить
Peter Norvig spell checker
  #3  
Старый 28.01.2011, 14:10
гocть

 
Сообщений: n/a

ну, есть, например, BK-дерево (http://en.wikipedia.org/wiki/BK-tree), можеш им ускорить свой поиск

Цитата:
Я сделал простенькую программу в которой загружаю весь словарь и в цикле делаю проверку с каждым словом... исправляет довольно не плохо
можешь сделать еще лучше (в смысле качества), если станешь учитывать частоту слова, на которое исправляешь.

т.е. P(слово | опечатка) = P(опечатка | слово) * P(cлово) / const
расстояние между словами моделирует всего лишь член P(опечатка | слово). моделируя частоту слова (P(cлово)) получишь самую настоящюю noisy-channel модель, которую все собственно и используют.
  #4  
Старый 29.01.2011, 18:48
гocть

 
Сообщений: n/a

вместо сравнивания слов левенштейном, проще генерировать все возможные опечатки, скажем до расстояния 1 или 2, и проверять их наличие в словаре через хеш-таблицы. словарь ты можешь предварительно также расширить опечатками до расстояния, скажем 1, тогда в сумме выйдет, что твоя программу будет икать опечатки до расстояния 3, что достаточно в твоем примере.
  #5  
Старый 29.01.2011, 18:52
гocть

 
Сообщений: n/a

ну и если на входе твоей программе поступают не отдельные слова, а предложания, то ты можешь построить n-граммные языковые модели (на уровне слов) на каком-нибудь корпусе, и учитывать их при оценке вероятности исправления. Таким образом можно определить опечатку в "икать опечатки".
  #6  
Старый 30.01.2011, 16:19
Новичок

Отправить личное сообщение для zhazhah Посмотреть профиль Найти все сообщения от zhazhah
 
Регистрация: 28.01.2011
Сообщений: 7

Чёт ни чё не понял... как это поиск по опечаткам... это как? можно пример?
  #7  
Старый 30.01.2011, 19:21
гocть

 
Сообщений: n/a

что конкретно непонятно? к чему пример?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
реализация алгоритма хаффмана на Php и си Саня Реализация, исходники, языки 5 19.05.2010 14:03
Реализация алгоритма Ху (Hu) RARIA Графы 2 25.12.2009 00:47
универсальная реализация алгоритма сотрировки ice Сортировка и поиск 19 11.12.2009 01:23
Реализация алгоритма на Delphi Игорь_1988 Реализация, исходники, языки 2 23.01.2009 15:45
реализация алгоритма ахо-корасик Straight Сортировка и поиск 0 28.04.2007 09:32