Меню
Что нового?

[Алгоритмы] Быстрого исправления опечаток.

WP

^_^
[Алгоритмы] Быстрого исправления опечаток.

Добрый день. Размышляю над созданием быстрого исправления опечаток по словарю, нечто вроде indexed levenstein. Слов будут миллионы, время индексации словаря значения не имеет, важно лишь время нахождения слов. Данная функция хорошо работает в MS Word.
Есть результаты, но они пока оставляют желать лучшего.
Буду рад если кто-то поделится своими мыслями. Спасибо.
 

dimagolov

Новичок
мне говорили про индексацию словарей (для макс. быстрого поиска образца в словаре):
есть алфавит из N символов, есть сортированный список слов. храним такие индексы
PHP: 
WordLength= array(
1 => array(' ' =>-1,
                  'A' =>0 ,
                  'B'=>123,
......
),
2 => array(' ' =>-1,
                  'A' => array( 'A' => -1, 'B'=>'1'....),
                  'B' => array( 'A' => 123, 'B'=>'-1'....),
.....
),
.....
);
Кстати вот написал и подумал, что массив по идее нужен один - на максимальную глубину индекса, прото отсутствие слов и полное совпадение надо как-то обозначать дополнительно.

И так на глубину индексации. В итоге имея образец мы выбираем интересующую нас длинну и используя каждую букву как индекс находим последовательно индексы подстроки определенной длинны. аналогично легко мы находим индекс сделущей буквы для каждой длинны. Если к этому прибавить набор возможных опечаток, то вся наша задача сведется к следующему:
1. сформировать набор опечаток
2. перебрать по словарю начальное слово и набор опечаток
если начальное слово есть в словаре, а опечаток нету - типа все ОК
если начального слово есть, опечатки тоже - подозрительно, но не меняем, а информируем
есди начального слова нету, из опечаток получили один вариант - заменяем
есди начального слова нету, из опечаток получили более одного варианта - спрашиваем.
 
phprus

phprus

Moderator
Команда форума
dimagolov
есть сортированный список слов. храним такие индексы
Нажмите для раскрытия...
Распиши пожалуйста алгоритм формирования такого индекса более подробно, а то я не очень понимаю как он получается.

1. сформировать набор опечаток
Нажмите для раскрытия...
А как? С ростом количество допустимых опечаток в слове ресурсоемкость этого процесса очень резко возрастает.

P.S. Ссылка в тему: http://gmdidro.googlepages.com/Ru_HowtoWriteaSpellingCorrector.html
 

WP

^_^
Спасибо. Кто знает, реализован ли данный функционал в OpenOffice? :) Это ж open source, никто не мешает заимствовать.

dimagolov
Интересно.

phprus
Хорошая статья.

-~{}~ 31.03.08 06:57:

Кстати, хорошо бы научить программу предлагать раздельное написание, например "ямашина" в "я машина".

-~{}~ 31.03.08 06:58:

З.ы. корректор раскладки я уже реализовал.
 
phprus

phprus

Moderator
Команда форума
Ermitazh
хочу добавить что для поиска не помешало бы воспользоваться алгоритмом двоичного поиска.
Нажмите для раскрытия...
Зачем такие тормоза то добавлять? Для таких целей прекрасно подходит хеш-таблица.

WP
Кто знает, реализован ли данный функционал в OpenOffice? Это ж open source, никто не мешает заимствовать.
Нажмите для раскрытия...
Какой функционал? Разделение слитно написанных слов? Вроде-бы реализован.
В опенофисе используется http://hunspell.sourceforge.net/
И еще посмотри исходники aspell'а

З.ы. корректор раскладки я уже реализовал.
Нажмите для раскрытия...
Для каких языков?
Можешь рассказать алгоритм по которому он работает?
 

dimagolov

Новичок
phprus
где-то так:
PHP: 
$index= array();
foreach ($Words as $WordIndex => $word) {
   for($i= 0, $l= strlen($word), $ref= &$index; $i < $l; $i++) {
      $curchr= substr($word, $i, 1);
      if (!isset($ref[$curchr]))
          $ref[$curchr]= $WordIndex;
      $ref= &$ref[$curchr];
   }
}
 

Ermitazh

Новичок
phprus
это не тормоза, а нормальный классический алгоритм. По крайней мере лучшего ещё не видел. Вопрос - ответ по существу и я бы не сказал, если бы не знал и не использовал это. В словарях этот алгоритм как раз и используется.
 

dimagolov

Новичок
Ermitazh, алгоритм двоичного поиска это универсальный алгоритм, который наиболее эфективно пользовать при числовом сравнении. сравнение строк намного более ресурсоемкое. в случае словарей ввод происходит посимвольно, поэтому можно построить эфективные индексы для каждой длинны строки. А уже в поиске по хешам индексов бинарный поиск и будет использовать.
 
fixxxer

fixxxer

К.О.
Партнер клуба
ну первое что приходит в голову это aspell-словари + фонетический хэш наподобие soundex
еще надо разделить как-то, вроде того что корни слов искать по хэшу, окончания править по таблицам словоформ...
 

WP

^_^
phprus
Для каких языков?
Можешь рассказать алгоритм по которому он работает?
Нажмите для раскрытия...
Для ru/en. Элементарно, берешь для языка текст 50 кб (осмысленный, лучше всего худ. произведение), и записываешь все встречающиеся последовательности из 3 букв. Затем при проверке смотришь сколько в слове троек букв которых не было в том тексте, далее конвертируешь на другой язык, и проверяешь там. Если там результат лучше, то предлагаешь замену. Например 'the' встречается часто, а 'eht' не встречается вообще. Метод очень эффективен. (С)ам придумал.
 
phprus

phprus

Moderator
Команда форума
WP
Понятно. Я почти такой-же алгоритм использовал когда мне нужно было реализовать приблизительное распознавание языков текста (список был из ~15 языков и нужно было определить ~5 наиболее вероятных языка). Так как требуемая точность была относительно не велика, то на не коротких текстах такой алгоритм показывал хорошие результаты, правда я использовал в качестве текстов для генерации статистики википедию.
Кстати этот метод вроде-бы называется методом N-gram.
 

Rin

*
Меня эта тема тоже заинтересовала, безграмотность текстов напрягает.
Кто может поделиться базой слов (со всеми словоформами) для русского английского/языка?
Я в будущем планирую этим заняться.

Про Нигму: searchengines.ru/press-releases/archives/005377.html
 
fixxxer

fixxxer

К.О.
Партнер клуба
>>Кто может поделиться базой слов (со всеми словоформами) для русского английского/языка?

google aspell dictionaries
 

snark

Новичок
Автор оригинала: Rin
Кто может поделиться базой слов (со всеми словоформами) для русского английского/языка?
Нажмите для раскрытия...
могу поделиться базой около 110.000 слов (со словоформами, ~2.500.000 словоформ) $$
 

Rin

*
snark

Вы хотите предложить словарь Лебедева?

ftp://scon155.phys.msu.su/pub/russian/ispell/
 

snark

Новичок
Rin
честно говоря, не охото разбираться, с тем что вы прислали. Словарь собирался долго, у каждого слова есть все принадлежащие ему признаки (часть речи, пол, падеж, число и тд.). Формат файла SQL (>150Mb).

Если интересно, пишите: 213-879-360
 

Alexandre

PHPПенсионер
Ура WP нашелся, а мы думали, тебя в Армию забрали или что-то случилось серьездное. тебя два человека искало уже.

Ajax, сам алгоритм - сравнимаем посимвольно набронное слово и слово из БД, если один символ не соответсвует, то предлагаем варианты.
 
Войдите или зарегистрируйтесь для ответа.
Сверху