Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Скриптовые языки программирования > PHP
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.05.2013, 23:04   #1
Abuhamed
Форумчанин
 
Аватар для Abuhamed
 
Регистрация: 27.01.2010
Сообщений: 330
По умолчанию Скрипт поиска слов по буквам

Нужно сделать аналог:

http://4maf.ru/anagram.php

Вводим допустим: приветкакдела
Выбираем: все слова

Жмем поиск и получаем:



Где взять русский словарь в .sql

И как сделать запрос к базе, что бы сложило слово?
Abuhamed вне форума Ответить с цитированием
Старый 28.05.2013, 23:30   #2
ADSoft
Старожил
 
Регистрация: 25.02.2007
Сообщений: 4,150
По умолчанию

Насчет словаря не знаю, а делается думаю перебором в цикле... Типа - а, аа, аб,ав, аг итд получившиеся же слова сверяются с бд слов, если успех то выводим
ADSoft вне форума Ответить с цитированием
Старый 29.05.2013, 01:51   #3
Johnatan
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т слов.
Парсим в базу данных. При парсинге сразу генерируем "сумму слова".
То есть присваиваем каждой букве "вес".
Например:
Код:
а = 1
б = 2
в = 4
г = 8
д = 16
е = 32
и так далее
Ещё лучше использовать такую систему, чтобы самые частоиспользуемые буквы алфавита имели наименьший вес, а самые редкоиспользуемые - наибольший.

Далее просто при парсинге каждого слова в БД - считаем сумму букв в слове через наш вес и сохраняем эту сумму. Итого, у всех слов получится свой вес. У анаграмм вес будет одинаков. Цифра может получиться очень большая, но BIGINT со всем справится.

Теперь, получаем входной набор букв.
Генерируем вес для каждого уникального буквосочетания.
Например слово "свет" при словах от трёх букв:
Код:
с 262144
в 4
е 32
т 524288
Генерируем уникальные сочетания с тремя буквами и более:
Код:
све 262180
свт 786436
сет 524288
евт 786500
свет 786468
Как видно, нет смысла проверять сочетания типа "вет, тес, етс" и другие, так как вес у них будет одинаков с уже сгенерированными.
Нам остаётся только найти все слова в базе с такими цифрами, это и будут наши слова, состоящие из таких же букв.

Здесь есть одно упущение - повторение букв. Фактически буква "б" весит как две буквы "а". Для этого можно будет задать отдельную проверку на соответствие введённым буквам, когда уже выбраны все слова.

Алгоритм придумал на коленке. Его ещё можно доработать.
98% из тысячи моих постов сделаны в профильном подфоруме. Я не накручиваю свои посты болтанием в "курилке", а ты?

Последний раз редактировалось Johnatan; 29.05.2013 в 01:55.
Johnatan вне форума Ответить с цитированием
Старый 29.05.2013, 11:03   #4
Andkorol
Старожил
 
Регистрация: 31.05.2010
Сообщений: 3,301
По умолчанию

Я бы сделал совсем просто, по классическому алгоритму "Сортировки и последовательности".
Главный момент – правильно сформировать базу слов.

Базу слов для тестов я брал из того же источника, который предложил Johnatan – только я для пробы взял словарь поменьше, на 93392 слова.
Парсим словарь в БД, при этом для каждого слова формируем его ключ – который состоит из всех букв этого слова, расставленных в алфавитном порядке:
служба => абжлсу
дружба => абджру
катакомба => ааабккмот
... и т.д.

Поле с этими ключами индексируем для ускорения работы.

Дальше всё совсем просто:
– приходит из формы набор букв для поиска анаграмм
– этот набор букв мы также расставляем в алфавитном порядке (формируем ключ для этого слова)
– затем просто ищем в БД все слова, имеющие точно такой же ключ
– всё, все анаграммы к данному набору букв найдены

Примеры:
Поиск: мопбал
Ключ: аблмоп
Рез-ты: пломба, апломб

Поиск: забаврить
Ключ: аабвзирть
Рез-ты: разбивать, забривать, разбавить

Поиск: ротипость
Ключ: иоопрстть
Рез-ты: построить, стопорить, поострить, отпросить, опростить

Работает всё очень быстро.
Готовая таблица на 93392 слова (UTF-8):
Вложения
Тип файла: zip anagramm.sql.zip (974.9 Кб, 26 просмотров)
Andkorol вне форума Ответить с цитированием
Старый 29.05.2013, 11:24   #5
ADSoft
Старожил
 
Регистрация: 25.02.2007
Сообщений: 4,150
По умолчанию

ну это только для случая равенства длинны слов
а как быть с составлением более коротких слов, чем исходное?
опять перебор (вернее всевозможные перестановки) ...?
ADSoft вне форума Ответить с цитированием
Старый 29.05.2013, 12:56   #6
Andkorol
Старожил
 
Регистрация: 31.05.2010
Сообщений: 3,301
По умолчанию

Цитата:
Сообщение от ADSoft Посмотреть сообщение
ну это только для случая равенства длинны слов
а как быть с составлением более коротких слов, чем исходное?
опять перебор (вернее всевозможные перестановки) ...?
Применив комбинаторику – получаем массив вариантов комбинаций букв из заданного слова, при необходимости ограничив минимальное число букв в слове (как в примере на скриншоте).
Формируем ключи из этих комбинаций (буквы в строке в алфавитном порядке).
Удаляем повторяющиеся ключи – ибо они неизбежны.
А дальше всё тоже самое – по ключам в таблице находим соответствующие им слова-анаграммы, и выводим результаты.

По слову из 1-го поста "приветкакдела", варианту поиска "все слова" и ограничении минимальной длины слова в 3 буквы:
В приведенной выше таблице из 93392 слов находит 384 слова за 0.5807 сек.
Andkorol вне форума Ответить с цитированием
Старый 30.05.2013, 17:05   #7
Abuhamed
Форумчанин
 
Аватар для Abuhamed
 
Регистрация: 27.01.2010
Сообщений: 330
По умолчанию

Цитата:
Сообщение от Andkorol Посмотреть сообщение
Применив комбинаторику – получаем массив вариантов комбинаций букв из заданного слова, при необходимости ограничив минимальное число букв в слове (как в примере на скриншоте).
Формируем ключи из этих комбинаций (буквы в строке в алфавитном порядке).
Удаляем повторяющиеся ключи – ибо они неизбежны.
А дальше всё тоже самое – по ключам в таблице находим соответствующие им слова-анаграммы, и выводим результаты.

По слову из 1-го поста "приветкакдела", варианту поиска "все слова" и ограничении минимальной длины слова в 3 буквы:
В приведенной выше таблице из 93392 слов находит 384 слова за 0.5807 сек.

Метод поиска классный. Вопрос в том, как же составить базу из нормальных слов, в виде анаграмм. Написать цикл и пусть переберет все 100к позиций?
Abuhamed вне форума Ответить с цитированием
Старый 30.05.2013, 18:13   #8
Andkorol
Старожил
 
Регистрация: 31.05.2010
Сообщений: 3,301
По умолчанию

Цитата:
Сообщение от Abuhamed Посмотреть сообщение
Вопрос в том, как же составить базу из нормальных слов, в виде анаграмм. Написать цикл и пусть переберет все 100к позиций?
Да, именно так я и сделал для таблицы во вложении выше.
Andkorol вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Макрос для поиска и выделения слов 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