Hi, all! Сразу говорю, в форуме читал все топики по данной теме... Собственно, есть словарь (>100.000 слов). Необходимо проверять орфографическую правильность введенного пользователем слова. Т.е., если слово присутствует в словаре, значит все правильно. Посоветуйте самый быстрый и эффективный алгоритм поиска слова в файле. Наподобие алгоритма Бойера-Мура, что ли...

Просмотров 21, Ответов 0   

FiMa1, самый эффективный по скорости или по занимаемой памяти?
Чем меньше жалеешь памяти тем быстрее можно искать, так что вопрос неоднозначный и наоборот.

Самый эффективный по скорости...

FiMa1, полагаю для этого уже есть готовые решения. map из STL не подойдет? Как вариант - упорядоченное(отсортированное) дерево. imho поиск в этом случае будет очень быстрым.

Спасибо, Rockie. Сейчас загляну в STL. Однако хотелось бы написать самому. Мне бы вот только теорию какого-нибудь алгоритма...

На вскидку, к сожалению, не отвечу.
Могу лишь посоветовать отправить это в раздел алгоритмов, т. к. здесь речь вроде не о реализации алгоритма на плюсах, а о самом алгоритме.

Тогда создаем многомерный массив, например
char data[33][33][33][33]; - каждое измерение - одна буква - 
1е измерение - 1ый символ
2е измерение - 2й символ

А в последнем будет массив строк начинающихся на первые 4 буквы.
Первая часть поиска вообще будет прямое индексирование
Пусть строка у нас
char s[]="строка";

тогда 

data[s[0]-'а'][s[1]-'а'][s[2]-'а'][s[3]-'а'] - даст список слов начинающихся на "стро", дальше 
можно классическим бинарным поиском найти в указанном списке нужное слово.

Можно еще ускорить поиск сделав массив 5-ти мерным, но при этом размер его будет 150Мб  
против 4.5 мб для 4-х мерного.

Бинарные деревья

p.s.: однако imho не факт что при таком объеме данных есть необходимость в таких структурах, stl ведь тоже очень быстрый

std::map итак использует бинарные деревья   В некоторых версиях STL (расширенных) есть ещё более быстрые hash_map, также это чуда есть в бусте.

Кстати, недавно столкнулся с тем, что std::hash_map ( реализация Dinkumware, С++ Builder 2006 ) работает во многих случаях медленнее, чем std::map.

Юзал конкретизацию std::(map/hash_map)< unsigned long, unsigned short>...

Количество объектов приблизительно 1000-10000...

Пасиб всем за ответы... Я, конечно, писал 

Однако же, alexeis1

Это жесть, ИМХО.. Все равно пасиб. Тема не закрыта. Даешь САМЫЙ быстрый алгоритм поиска в массы!?

Добавлено @ 15:36 
Тут вот нашел.. Алгоритмы поиска в тексте Мож кому интересно. А мне интересно ваше мнение по статье  .

В каких? Добавление/удаление должно быть по идее медленней, но поиск не в коем случае. Хотя это по идее - лично гарантировать не могу. Надо бы в очередной раз пожалуй устроить тестирование скорости и занимаемой различных контейнеров в различных версиях STL для различных библиотеках. Захотелось мне собрать отчёты по этой теме. Постараюсь подготовить.

Да но для 4-х мерного это всего 4.5 мб. 
Хотел же самый быстрый! - быстрее индексирования ничего нет. Это же прямое обращение без поиска! Любые известные алгоритмы типа хеша будут заведомо медленнее. В идеале, конечно, для каждого слова должен сразу вычисляться индекс в массиве и поиска как такового быть не должно. 
Можно объединить индексирование и хеш.

Ok. Надо подумкать... Предложения принимаются...