Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Самый эффективный алгоритм поиска?

Автор: FiMa1 25.10.2006, 09:42

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

Автор: FiMa1 25.10.2006, 13:12

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

Автор: Alexeis 25.10.2006, 13:43

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

Автор: FiMa1 25.10.2006, 13:54

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

Автор: Rockie 25.10.2006, 14:13

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

Автор: FiMa1 25.10.2006, 14:17

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

Автор: Любитель 25.10.2006, 14:18

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

Автор: Alexeis 25.10.2006, 14:24

Цитата(FiMa1 @ 25.10.2006, 13:54

)

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

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

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

тогда

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

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

против 4.5 мб для 4-х мерного.

Автор: Rockie 25.10.2006, 14:27

Цитата

Узел состоит из поля данных, которое является открытым (public) элементом, т.е. к которому можно обращаться непосредственно. Это позволяет читать или обновлять данные во время прохождения дерева, а также допускает возвращение ссылки на данные. Последняя особенность используется более сложными структурами данных, например, словарями.

http://www.optim.su/CS/2000/3/trees/trees.asp

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

Автор: Любитель 25.10.2006, 14:44

std::map итак использует бинарные деревья smile

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

Автор: JackYF 25.10.2006, 15:26

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

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

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

Автор: FiMa1 25.10.2006, 15:31

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

Цитата

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

Однако же, alexeis1

Цитата

...размер его будет 150Мб

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

Добавлено @ 15:36
Тут вот нашел.. http://www.rsdn.ru/article/alg/textsearch.xml Мож кому интересно. А мне интересно ваше мнение по статье smile

Автор: Любитель 25.10.2006, 15:41

Цитата(JackYF @ 25.10.2006, 15:26

)

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

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

Автор: Alexeis 25.10.2006, 15:50

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

Автор: FiMa1 25.10.2006, 16:12

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

Автор: maxim1000 25.10.2006, 16:22

Цитата(alexeis1 @ 25.10.2006, 14:50

)

Да но для 4-х мерного это всего 4.5 мб.

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

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

Автор: SergeCpp 25.10.2006, 17:03

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

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

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

P.S. Очень быстро... В DOS-е работало на 386... Словарь и индексы не выложу... http://sergecpp.mylivepage.ru/file/245/11/ME_SPELL.RAR

Автор: sergejzr 25.10.2006, 17:12

Цитата(JackYF @ 25.10.2006, 14:26

)

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

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

Автор: JackYF 25.10.2006, 17:21

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

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

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

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

Автор: Dov 25.10.2006, 23:51

http://forum.sources.ru/index.php?showtopic=152611

Автор: FiMa1 26.10.2006, 09:16

Ребята, пасиб всем smile

! Не ожидал такой активности... Dov, забавный топик.. Вдвойне забавно, что там ссылка, которую я приводил выше http://www.rsdn.ru/article/alg/textsearch.xml. Думаю, однако, остальные их предложения не подходят для моего случая (объем слов более 100.000). Да они и сами признают:

Цитата

strstr() работает очень долго!
Когда большие массивы сравнения и это ещё и в теле вложенных циклов, strstr() - это просто гигантский тормоз.
Для таких задач мне пришлось писать собственную реализацию...

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

Добавлено @ 09:25
Ребята, тем кто заинтересовался сабжем загляните по ссылкам, не пожалеете:
http://algolist.manual.ru/search/esearch/
http://program.rin.ru/cgi-bin/print.pl?id=830

Автор: SergeCpp 26.10.2006, 09:32

http://rsdn.ru/res/book/prog/stringalgs.xml

Автор: Dov 27.10.2006, 13:53

Цитата(FiMa1 @ 26.10.2006, 09:16)

Думаю, однако, остальные их предложения не подходят для моего случая (объем слов более 100.000).

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

Автор: FiMa1 27.10.2006, 16:02

Сорри, Dov! Ступил... smile

Топик супер. Thanks!