[Tonny_Bennet]

1. Дан набор слов русского языка и текст, который следует проверить. Требуется написать список неправильных слов и предложить до 10 вариантов исправления. »

Можно текст разбить на слова и пословно делать сравнение с словарём. Правда если словарь будет большой то по-моему код будет не очень быстро работать. Как пример можно воспользоваться таким сравнением. Но его функционал без примера мне пока не сильно понятен.

Я думаю вам стоит начать писать программу для проверки орфографии по словарю и если будут вопросы задавать их здесь.

[PhilB]

Вот неплохой обзорчик: http://habrahabr.ru/post/114997/
И еще алогоритм Ландау-Вишкина: http://algolist.ru/search/fsearch/index.php

[Beyound]

возможно есть смысл подумать о использовании свойств русского языка. скажем придумать как выделять в слове корень и искать в словаре корни слов, а по найденому корню проверять допустимое словообразование от этого корня. тут правда есть загвоздка - слова с 2-мя корнями. вообще русский язык слишком сложный чтобы влоб его так делать, английский бы прокатил влегкую.
незнаю нормальная ли идея, но стоит проверить. так мы просто создадим гиперсловарь (а-ля гипертекст) и ясное дело верхушка намного меньше чем полное содержание словаря и ищется там быстрее, вопрос в том компенсирует ли время, затраченное на разбор текста по корням и т.п.
можно сделать так - есть очень большой словарь исключительно правильных слов и делается предположение, что допустить с неким нелинейным % относительно длинны слов ошибок реально, и если в словаре нет написанного слова - то показывать все возможные, отличающиеся на это число букв.
но опять же - все эти наборы будут как у англичанина с русским словарем - слова те, но связи между ними просто 0.

[pva]

Tonny_Bennet,
Делаем шаг первый: тупо проверяем правильность слова, но не предлагаем варианты.
словарь взят отсюда: http://files.speakrus.ru/dict/pldf-win.zip
проверяем фрагмент книги братьев Стругацких "Обитаемый остров".

Правда если словарь будет большой то по-моему код будет не очень быстро работать »

На машине i3-2350M 2.30 GHz, 4G RAM, без оптимизации кода, с использованием хеш-таблицы поиск занял 45 мс - это вполне приемлимо.

Код:

#include <hash_map>
#include <string>
#include <cstring>
#include <list>
#include <fstream>
#include <iostream>
#include <ctime>
using namespace std;

// слова храним в обычном списке,
// индексируем список хеш-таблицей указателей

struct hash_fun {
	size_t operator()(const char* str) const {
		return __gnu_cxx::__stl_hash_string(str);
	}
};

struct hash_cmp {
	bool operator()(const char* a, const char* b) const {
		return strcmp(a,b)==0;
	}
};

// контейнер для слов
typedef list<string> wlist_type;
typedef __gnu_cxx::hash_map<const char*, int, hash_fun, hash_cmp> windex_type;

// проверка на русский символ
inline bool is_ru_alpha(int c) {
	return unsigned(c - 0xc0) < 0x40 || c=='ё' || c=='Ё';
}

// проверка на нерусский символ
inline bool is_not_ru_alpha(int c) {
	return 0<c && !is_ru_alpha(c);
}

// Загрузить слово в нижнем регистре.
bool get_word(streambuf& stm, string& str) {
	str.clear();

	while(is_not_ru_alpha(stm.sgetc())) {
		stm.sbumpc();
	}

	while(is_ru_alpha(stm.sgetc())) {
		str.push_back(stm.sbumpc() | 32);
	}

	return !str.empty();
}

// загрузить русский словарь.
void load_dict(streambuf *file, wlist_type& dict, windex_type& index)
{
	if (file) {
		string word;

		dict.clear();
		while(get_word(*file, word)) {
			dict.insert(dict.end(), word);
		}

		index.resize(dict.size());
		for(wlist_type::iterator a1=dict.begin(), a2=dict.end(); a1!=a2; ++a1) {
			index[a1->c_str()];
		}

		clog << "indexed " << index.size() << " words\n";
	}
}

// проверить файл
void check_file(streambuf* file, windex_type& index)
{
	static int const max_errors = 25;

	if (file) {
		string word;
		int cnt_errors = 0,
			cnt_total = 0;

		while(get_word(*file, word)) {
			++cnt_total;
			if (index.find(word.c_str())==index.end()) {
				if (++cnt_errors < max_errors) {
					cout << "spell: " << word << "\n";
				}
			}
		}

		if (max_errors <= cnt_errors) {
			cout << "   ...\n";
			clog << "showing only first " << max_errors << " errors\n";
		}

		cout << "misspelled " << cnt_errors << " of " << cnt_total << " words\n";
	}
}

int main(int argc, char** argv) {
	clock_t start_time;
	int duration;
	filebuf fbuf;

	#define BENCHMARK(name, foo) \
		start_time = clock();\
		foo; \
		duration = clock() - start_time;\
		clog << name " spent " << double(duration)/CLOCKS_PER_SEC << " secs\n";\

	wlist_type dict;
	windex_type index;

	BENCHMARK("load dictionary", load_dict(fbuf.open("pldf-win.txt", ios_base::in), dict, index));
	fbuf.close();

	BENCHMARK("spell check", check_file(fbuf.open("strugackie_ostrov.txt", ios_base::in), index));
	fbuf.close();

	return 0;
}

Вывод:

Код:

spell: ладошек
spell: ладошки
spell: солнцу
spell: карманные
spell: компьютеры
spell: стругацкие
spell: первая
spell: приоткрыл
spell: высунулся
spell: поглядел
spell: было
spell: низкое
spell: какое
spell: твердое
spell: этой
spell: легкомысленной
spell: прозрачности
spell: намекающей
spell: космоса
spell: обитаемых
spell: миров
spell: настоящая
spell: библейская
spell: гладкая
   ...
misspelled 41216 of 93652 words
indexed 125140 words
load dictionary spent 0.272 secs
showing only first 25 errors
spell check spent 0.045 secs

PhilB, статью на хабре читал, но ума понять расстояние Ливенштейна не хватило (суть понятна, как считать - непонятно). Можель объяснить его для тупых?

Beyound, судя по "ошибкам", которые выдаёт программа на основании словаря из 120К слов, двигаться нужно в твоём направлении. Типа метод триграмм, только разбивать по частям слова. Но тогда нужно добавлять ограничение на применимость частей слова друг к другу?

[yurfed]

скажем придумать как выделять в слове корень и искать в словаре корни »

Вы хотите переписать словари Даля и Ожёгова? Задача вроде вся из себя, чтобы по корням угадывать правописание любого слова.
Других альтернатив для подобных целей не имеется?

[ferget]

расстояние Ливенштейна не хватило (суть понятна, как считать - непонятно) »

можно исходник посмотреть
тут

[yurfed]

расстояние Ливенштейна не хватило »

Ну хоть что то у него хватает?

[pva]

yurfed, к сожалению, не понял суть ваших советов.
ferget, а есть ссылка на теорию, а не реализацию?

[pva]

После нескольких итераций чтения предложенных ссылок до меня допёрло, как сделать. Получилось вот что (расстояние Левенштейна):

Код:

spell: ладошек
   1. ладоше (1)
   2. ладоней (2)
   3. ладоши (2)
   4. ладошку (2)
   5. людишек (2)
spell: компьютеры
   1. компьютерный (2)
   2. комитеты (4)
   3. компота (5)
   4. копьев (5)
   5. копаются (5)
spell: стругацкие
   1. чумацкие (4)
   2. рыбацкие (4)
   3. дурацкие (4)
   4. стругать (4)
   5. стрюцких (4)
spell: робинзон
   1. робенок (3)
   2. родиной (3)
   3. родинок (3)
   4. рубикон (3)
   5. родион (3)
spell: люк
   1. лак (1)
   2. люд (1)
   3. лек (1)
   4. лю (1)
   5. лют (1)
spell: намекающей
   1. намекающий (1)
   2. намекающая (2)
   3. замирающей (3)
   4. заменяющей (3)
   5. вытекающей (3)
spell: бездонность
   1. бездарность (2)
   2. бездонном (3)
   3. бездонной (3)
   4. бездонное (3)
   5. безличность (3)
spell: космоса
   1. комода (2)
   2. космой (2)
   3. тоскова (3)
   4. козлова (3)
   5. косятся (3)
spell: множественность
   1. мужественность (2)
   2. божественность (2)
   3. мужественности (3)
   4. множественное (3)
   5. торжественность (3)
spell: твердь
   1. тверда (1)
   2. тверд (1)
   3. твердо (1)
   4. твердя (1)
   5. тверь (1)
spell: твердь
   1. тверда (1)
   2. тверд (1)
   3. твердо (1)
   4. твердя (1)
   5. тверь (1)
spell: атланта
   1. таланта (2)
   2. атлета (2)
   3. танта (2)
   4. атласа (2)
   5. атласная (3)
spell: фосфоресцировала
   1. сформировал (6)
   2. восторжествовала (6)
   3. лорнировала (7)
   4. откомандировала (7)
   5. отретировалс (7)
spell: пробитую
   1. побитую (1)
   2. пролитую (1)
   3. прибитую (1)
   4. пробита (2)
   5. пробитая (2)
spell: расплывались
   1. расплевались (1)
   2. расписывались (2)
   3. раскрывались (2)
   4. расплылись (2)
   5. раскалывались (2)
spell: кляксы
   1. классы (2)
   2. клятвы (2)
   3. лясы (2)
   4. клялся (2)
   5. клюквы (2)
spell: туши
   1. тушки (1)
   2. тужи (1)
   3. тучи (1)
   4. тушь (1)
   5. туш (1)
spell: люк
   1. лак (1)
   2. люд (1)
   3. лек (1)
   4. лю (1)
   5. лют (1)
spell: раздавленной
   1. раздавленног (1)
   2. раздавленное (1)
   3. раздавленный (1)
   4. раздавленно (1)
   5. раздавленная (2)
spell: кривоватые
   1. кривоглазые (3)
   2. кроватке (3)
   3. розоватые (3)
   4. хриповатым (3)
   5. провожатые (3)
spell: голубизны
   1. голубизну (1)
   2. голубине (2)
   3. глубины (2)
   4. голубиных (2)
   5. голубятня (3)
spell: пологими
   1. полонили (2)
   2. положили (2)
   3. порогами (2)
   4. положим (2)
   5. плохими (2)
spell: склонами
   1. склонам (1)
   2. клоками (2)
   3. склянками (2)
   4. словами (2)
   5. склонах (2)
spell: размытому
   1. размытом (1)
   2. разлитому (2)
   3. развитому (2)
   4. разбитому (2)
   5. накрытому (3)
   ...
misspelled 8619 of 93652 words
indexed 162163 words
load dictionary spent 0.519 secs
showing only first 25 errors
spell check spent 9.292 secs

Среднее время поиска вариантов - 0.371 сек. Что-то долго мне кажется.