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. Надо подумкать... Предложения принимаются...

кстати, будет поменьше:
ведь некоторые буквосочетания в тексте встречаться не будут
например, если нет слов, начинающихся на "рл", то и соответствующий массив будет пустой

да и вообще можно выделить первые 4 символа в unsigned int (его уж точно хватит, пока разных используемых символов будет меньше 256) и сделать map (ну или hash_map) по нему...

Вот, посмотрите...

Язык очень близок к C

Писал сам, на вопросы отвечу (сейчас тороплюсь...)

P.S. Очень быстро... В DOS-е работало на 386... Словарь и индексы не выложу... Есть на сайте...


Присоединённый файл ( Кол-во скачиваний: 7 )
 SPELL.RAR 24,70 Kb

Скорее всего величина при инициализации/росте внутреннего массива разница у них. А так - поиск по хэшу ессно самое быстрое будет.

Не знаю... Я тоже думал так.

В моей функции большинство операций( на 2 порядка больше всего остального ) вызывается поиск по ключу и запись данных по найденному ключу... 

Возможно, реализация такая...

Лады, спасибо за ответы, подвопрос закрыт.

Тута пачитай, должно помочь.

Ребята, пасиб всем   ! Не ожидал такой активности... Dov, забавный топик.. Вдвойне забавно, что там ссылка, которую я приводил выше Алгоритмы поиска в тексте. Думаю, однако, остальные их предложения  не подходят для моего случая (объем слов более 100.000). Да они и сами признают:

Отдельная благодарность SergeCpp. Есть чему поучиться. Ковыряю сорец...

Добавлено @ 09:25 
Ребята, тем кто заинтересовался сабжем загляните по ссылкам, не пожалеете:
Точный поиск подстроки в строке
Краткий обзор алгоритмов

Методы и алгоритмы вычислений на строках

FiMa1. ты видать до конца не дочитал, там народ > 1 000 000 (миллион) слов юзает, даже класс написали свой.

Сорри, Dov! Ступил...   Топик супер. Thanks!