PHP Задача на выбор слов из базы по заданной комбинации букв

[cooler_ua]

PHP Задача на выбор слов из базы по заданной комбинации букв

Добрый день.

Есть такая задача:

Даётся определенная комбинация букв, например "аиоенбркв".
Есть таблица в MySQL words, в которой хранятся возможные слова.

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

Спасибо заранее.
Антон.

 

[FractalizeR]

Это что, задачка на собеседовании?

[SQL]CREATE TABLE `words` (
`wordid` int(10) unsigned NOT NULL auto_increment,
`word` varchar(100) NOT NULL,
PRIMARY KEY (`wordid`)
) ENGINE=MyISAM DEFAULT CHARSET=cp1251 AUTO_INCREMENT=1;

CREATE TABLE `letters` (
`id` int(10) unsigned NOT NULL auto_increment,
`wordid` int(10) unsigned NOT NULL,
`letter` char(1) NOT NULL,
PRIMARY KEY (`id`),
KEY `wordid` (`wordid`),
KEY `letter` (`letter`)
) ENGINE=MyISAM DEFAULT CHARSET=cp1251 AUTO_INCREMENT=1 ;

SELECT wordid, COUNT(wordid) AS num FROM letters WHERE letter IN ('a', 'b', 'c') GROUP BY wordid ORDER BY num DESC[/SQL]

Исходные данные есть? А то мне проверить не на чем.

 

[DiMA]

помнится в школе делал такую задачу на С++ (тогда еще под Вин 3.11 на 486 компе)
база слов была около 100 тыщ слов, метод - тупой перебор
и все быстро работало

 

[FractalizeR]

Я думаю, суть задачи как раз в том, чтобы избежать "тупых" решений. В любом случае, выглядит так, как если бы нами пользовались для решения задач на собеседованиях. Только не думаю, что работодатель настолько туп, что не проверяет форумы. А если и туп - сам виноват. Какой работодатель, такие и сотрудники....

 

[DiMA]

Можно SET заюзать, где 64 бита (букв - 33). Взводим у каждого слова соотв. биты, не обращая внимание на повторы букв. Дальше элементраный поиск по битмаске + отсеять варианты с повторами букв.

Либо, метод для чайников, заводим 33 колоночки у каждого словарного слова, где числом пишем колво соотв. букв. С запросом - думаю все понятно.

 

[Alexandre]

красиво...
я про int подумал использовать вместо битмаски...

 

[cooler_ua]

DiMA,

"С запросом думаю понятно".

Как раз с запросом и проблема. Нужно сделать не запрос, который найдет все слова, в которых есть эти буквы, а слова, которые можно составить из этих букв.

-~{}~ 08.09.09 12:21:

FractalizeR,

Нет, это задача для одного приложения ВКонтакте.

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

Всё, что Вы описали можно сделать намного проще. Запросиом типа: SELECT word_id, word FROM words WHERE word LIKE "%а%б%в%г%д%";

 

[Alexandre]

SELECT word_id, word FROM words WHERE word LIKE "%а%б%в%г%д%";

суперский запрос...
только не удивляйтесь, что потом Контакт начнет тормозить. Хотя для них нарастить мощность на пару десятков мускульных серверов не проблема.

 

[cooler_ua]

Alexandre,

Приложение пишется для ВКонтакте - это совсем не значит, что будет расположено на сервере ВКонтакте.

Проще всего пообсуждать ничего не предложив.

Такой звпросы выполняется очень быстро на поле с индексом.

 

[FractalizeR]

Автор оригинала: cooler_ua
Такой звпросы выполняется очень быстро на поле с индексом.

Индекс будет работать только в случае, если первый символ шаблона поиска - определен. А в вашем случае он "%".

 

[DiMA]

говнище с LIKE - забудьте (полный перебор на С++ будет быстрее в разы)

> Как раз с запросом и проблема.

Домохозяйки, включайте голову.

Пишем слово "TEST" в словарную базу:
insert... set id=..., cT=2, cE=1, cS=1

потом запросом ищем все слова из букв, типа EERTYS:
where cE>=2 && cR && cT && cS

Но лучше попробовать тоже самое на SET. Хоть и получится полный перебор, но умный - база один раз просканирует таблицу, где строки занимают 8 байт: 4 байта на id слова и 4 байта на битмаску букв. Это будет сделано намного оптимальнее, чем своя поделка таким же перебором на С++.

 

[cooler_ua]

И всё же, вернемся к сути вопроса. В Вашем методе я получаю все слова, которые содержат такие буквы, а не те, которые состоят из этих букв. А это совсем разные вещи.

 

[DiMA]

нда, так не выйдет... надо думать

-~{}~ 08.09.09 18:12:

зато через SET и бит маски все работает
тока отдельно фильтровать слова с дублями букв

-~{}~ 08.09.09 18:14:

к примеру, для поиска по 100 тыщ слов нужно завести таблицу размером 800 Кб, что умещается в память и работает мгновенно

словарная таблица - отдельно

 

[FractalizeR]

Автор оригинала: cooler_ua
FractalizeR,
Нет, это задача для одного приложения ВКонтакте.
Решение Ваше не верное, т.к. по данному запросу будут отобраны все слова, в которых всьтречаются заданные буквы, но не факт, что не встречаются другие.

Да, вы правы. Но ведь можно легко фильтр наложить.

words
--------
wordid
wordtext

letters
--------
letterid
lettercount


[SQL]SELECT wordid, SUM(lettercount) AS num FROM letters WHERE letterid IN("<letters of word>") AND wordid NOT IN (SELECT DISTINCT wordid FROM letters WHERE letterid IN ("<letters, which are not in word>")) GROUP BY wordid ORDER BY num DESC[/SQL]

У вас есть набор исходных данных для теста?

 

[Mols]

Да вроде и предложение с 33 столбцами должно работать.
Просто в условии запроса надо писать все столбцы. И условие сравнения немного не то.
для EERTYS: будет что-то вроде.
where 2 >= cE && 1 >= cR && 1>=cT && 1 >= cS && 1>= cY && 0>=cA && 0 >= cB..... и т.д.

 

[antson]

cooler_ua
две колонки
слово,нормализованное_слово

где нормализованное_слово
полученно перестановкой букв по алфавиту
СЛОВО = ВЛООС
таким способом легко найти все слова получаемые перестановкой букв
остается еще задача найти слова в которых использованы
не все буквы.
select word from ... where nword='ВЛООС' or nword='ЛООС'
or nword='ВЛОС' or nword='ВЛОО' и т.д
при составлении списка можно учитывать эвристические
правила, типа если при убирание буквы получается
уже проверяемая комбинация - пропустить, если в наборе
не осталось гласных - пропустить

-~{}~ 09.09.09 09:01:

для эстетов where nword in ('ВЛООС', ....)

-~{}~ 09.09.09 09:13:

после чего можно смело участвовать в ТВ шоу угадай
что за слово можно составить из "Х Л О"

 

[zerkms]

antson
это если задача состоит в поиске анаграмм. а у него:

чтобы максимально быстро и с минимальной нагрузкой отобрать все те слова, которые можно составить из этих букв. Не обязательно использовать все буквы из изначальной комбинации.

 

[antson]

zerkms
поэтому скрипт в запросе должен еще добавить комбинации
из n-1 n-2 и т.д. букв . В зависимости от потребности не короче X (где
X=2 (реальные слова типа река Уя)
3= типовое ограничение для поисков на сайте
или что-то типа 7-8 в играх такого плана
)

вспоминая моменты когда я переключая каналы попадал на такое, там квадрат 4на4 5на5 и слово 7-8 позиций

-~{}~ 09.09.09 09:45:

количество комбинаций менее (n+1)*n/2
т.е. для 15 букв это меньше 120

explain запроса легче некуда
simple ; use where , use index

 

[DiMA]

> после чего можно смело участвовать в ТВ шоу угадай

ага, это шоу для наивных лошар
там же все подстановочное и идет в записи... пипец детский сад в неокрепшем мозгу

 

[antson]

СОРРИ . ОШИБСЯ В КОМБИНАТОРИКЕ.
вариантов слишком много получается
после 10 букв метод работать не будет.
применимо если нужно найти анаграмы
для комбинаций полной длины или короче на 1-2 буквы.

-~{}~ 09.09.09 10:20:

для 15 букв (комбинаций из15,14,13 букв) уже 2516