|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.05.2013, 23:04 | #1 |
Форумчанин
Регистрация: 27.01.2010
Сообщений: 330
|
Скрипт поиска слов по буквам
Нужно сделать аналог:
http://4maf.ru/anagram.php Вводим допустим: приветкакдела Выбираем: все слова Жмем поиск и получаем: Где взять русский словарь в .sql И как сделать запрос к базе, что бы сложило слово? |
28.05.2013, 23:30 | #2 |
Старожил
Регистрация: 25.02.2007
Сообщений: 4,177
|
Насчет словаря не знаю, а делается думаю перебором в цикле... Типа - а, аа, аб,ав, аг итд получившиеся же слова сверяются с бд слов, если успех то выводим
|
29.05.2013, 01:51 | #3 |
Antimoderаtoris
Участник клуба
Регистрация: 08.02.2008
Сообщений: 1,251
|
ADSoft
При количестве введённых символов более 10 там начинается нехилая такая прогрессия. Формула: f(n) = n(f(n-1) + 1) Для десяти букв нужно будет сделать 9 864 100 проверок в базе. Для 11 букв уже 108 505 111 проверок. Имхо неразумно, при общем количестве слов в языке около 162 тысяч. Мой вариант решения (не претендует на истину в последней инстанции) Словарь: http://speakrus.ru/dict/index.htm Рекомендую "Словарь русской литературы" 162т слов. Парсим в базу данных. При парсинге сразу генерируем "сумму слова". То есть присваиваем каждой букве "вес". Например: Код:
Ещё лучше использовать такую систему, чтобы самые частоиспользуемые буквы алфавита имели наименьший вес, а самые редкоиспользуемые - наибольший. Далее просто при парсинге каждого слова в БД - считаем сумму букв в слове через наш вес и сохраняем эту сумму. Итого, у всех слов получится свой вес. У анаграмм вес будет одинаков. Цифра может получиться очень большая, но BIGINT со всем справится. Теперь, получаем входной набор букв. Генерируем вес для каждого уникального буквосочетания. Например слово "свет" при словах от трёх букв: Код:
Код:
Нам остаётся только найти все слова в базе с такими цифрами, это и будут наши слова, состоящие из таких же букв. Здесь есть одно упущение - повторение букв. Фактически буква "б" весит как две буквы "а". Для этого можно будет задать отдельную проверку на соответствие введённым буквам, когда уже выбраны все слова. Алгоритм придумал на коленке. Его ещё можно доработать.
98% из тысячи моих постов сделаны в профильном подфоруме. Я не накручиваю свои посты болтанием в "курилке", а ты?
Последний раз редактировалось Johnatan; 29.05.2013 в 01:55. |
29.05.2013, 11:03 | #4 |
Старожил
Регистрация: 31.05.2010
Сообщений: 3,301
|
Я бы сделал совсем просто, по классическому алгоритму "Сортировки и последовательности".
Главный момент – правильно сформировать базу слов. Базу слов для тестов я брал из того же источника, который предложил Johnatan – только я для пробы взял словарь поменьше, на 93392 слова. Парсим словарь в БД, при этом для каждого слова формируем его ключ – который состоит из всех букв этого слова, расставленных в алфавитном порядке: служба => абжлсу дружба => абджру катакомба => ааабккмот ... и т.д. Поле с этими ключами индексируем для ускорения работы. Дальше всё совсем просто: – приходит из формы набор букв для поиска анаграмм – этот набор букв мы также расставляем в алфавитном порядке (формируем ключ для этого слова) – затем просто ищем в БД все слова, имеющие точно такой же ключ – всё, все анаграммы к данному набору букв найдены Примеры: Поиск: мопбал Ключ: аблмоп Рез-ты: пломба, апломб Поиск: забаврить Ключ: аабвзирть Рез-ты: разбивать, забривать, разбавить Поиск: ротипость Ключ: иоопрстть Рез-ты: построить, стопорить, поострить, отпросить, опростить Работает всё очень быстро. Готовая таблица на 93392 слова (UTF-8): |
29.05.2013, 11:24 | #5 |
Старожил
Регистрация: 25.02.2007
Сообщений: 4,177
|
ну это только для случая равенства длинны слов
а как быть с составлением более коротких слов, чем исходное? опять перебор (вернее всевозможные перестановки) ...? |
29.05.2013, 12:56 | #6 | |
Старожил
Регистрация: 31.05.2010
Сообщений: 3,301
|
Цитата:
Формируем ключи из этих комбинаций (буквы в строке в алфавитном порядке). Удаляем повторяющиеся ключи – ибо они неизбежны. А дальше всё тоже самое – по ключам в таблице находим соответствующие им слова-анаграммы, и выводим результаты. По слову из 1-го поста "приветкакдела", варианту поиска "все слова" и ограничении минимальной длины слова в 3 буквы: В приведенной выше таблице из 93392 слов находит 384 слова за 0.5807 сек. |
|
30.05.2013, 17:05 | #7 | |
Форумчанин
Регистрация: 27.01.2010
Сообщений: 330
|
Цитата:
Метод поиска классный. Вопрос в том, как же составить базу из нормальных слов, в виде анаграмм. Написать цикл и пусть переберет все 100к позиций? |
|
30.05.2013, 18:13 | #8 |
Старожил
Регистрация: 31.05.2010
Сообщений: 3,301
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Макрос для поиска и выделения слов | Angry_Kitty | Microsoft Office Word | 11 | 07.10.2014 22:01 |
Алгоритм поиска слов в игре Балда? | Tronix | Gamedev - cоздание игр: Unity, OpenGL, DirectX | 2 | 11.01.2012 00:02 |
программа ассоциативного поиска вхождений слов | Тант Зин | Помощь студентам | 0 | 26.05.2010 14:37 |
программа ассоциативного поиска вхождений слов | Тант Зин | Помощь студентам | 0 | 11.05.2010 12:18 |
помогите с организацией поиска слов в richedit | BuT@JL | Общие вопросы Delphi | 1 | 30.04.2009 15:23 |