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

Возник вопрос: как это реализовать, если весь словарь хранится в БД? На каждую введеную пользователем букву "в лоб" искать введеное слово в базе данных? В упор не понимаю как это работает в поисковиках, при этом с огромной скоростью.

Добрый вечер. Во-первых хотелось бы посоветовать книжку C. Manning  "Introduction to information retrieval"   - в ней есть целая глава посвященная исправлению опечаток и разработке тезаурусов.

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

другой вариант - использовать для хранения словаря файловую систему ( каталоги и файлы ) , и организовать его в виде дерева.
Банальный пример:  

root
  |      \
a-m     n-z
  |    \        \          
a-hu hu-m  \
                    \
                   n-sh    si-z

- простейший пример струкутуры папок, где хранятся файлы словарей.  Рекомендую прочитать еще про B-деревья.




Редактирвоание опечаток  опирается на понятие "расстояние между 2мя словами ( термами)" - минимальное количество операций редактирования, с помощью которых строку s1 можно трансформировать в s2.
операции редактирвоания:
- вставка символа
- удаление символа из строки
- замена символа в строке


В целом задача сводится к поиску в словаре множества строк s(i)  для строки  str, для которых это расстояние минимально.
Выбор наиболее вероятного исправления  уже зависит от конкретной задачи.
Есть спец. алгоритмы динамического программирования и др. для вычисления расстояние редактирования + всегда можно придумать что-то свое, не менее эффективное

почитайте книги по поиску, в них очень подробно рассматриваются эти задачи.




Это сообщение отредактировал(а) sandland - 5.2.2011, 20:43

См. на расстояние Левенштейна - это иное название упомянутого sandland'ом "расстояния редактирования". Вдруг интернет-поиск именно на по такому термину даст лучшие результаты.