volmir 30 янв 2018 в 12:36

Опыт веб-разработки при создании игры «Составь слова»

7 мин

9.5K

PHP*Алгоритмы*Математика*Веб-разработка*Разработка игр*

Комментарии 29

volmir 30 янв 2018 в 12:40

Пример запроса из 20-ти букв (на сайтах в сети, которые предоставляют похожие сервисы):

1) поискслов.рф/anagram/search?query=абвгдежзиклмнорпстуф
Найдено: 155 страниц слов (размещения с повторениями).
Время ответа сервера: менее одной секунды на страницу.

2) wordhelp.ru/comb/абвгдежзиклмнорпстуф
Найдено: 9736 слов.
Время ответа сервера: 4 секунды.

Вопрос: Как можно обработать 4,180,411,311,071,440,000 комбинаций за 1-4 секунды? И по всем этим словосочетаниям сделать поиск по словарю?
Конечно, вопросы сложные и нетривиальные, простых ответов не будет. Но, возможно, хотя бы получится узнать направления того куда «смотреть», что «копать»…

arandomic 30 янв 2018 в 13:22

Смотрите.
Как вам уже сказали и пару раз скажут, построить 4*10^18 комбинаций и искать их в наборе 65000 слов — контрпродуктивно.
Значит нужно как-то отсеивать нужные слова из 65000
Отсеивать — по какому признаку? По наличию нужных букв и отсутствию тех, которых в запросе нет.

Берем словарь и для каждого слова строим вектор из 33 чисел. каждое число — количество повторений соответствующей буквы.

Эти вектора можно сохранить в базу и построить по ним индексы.
И потом select woridId from vectors where 'A' <= 1, 'Б' <=1 итп
Это если «влоб» и не пытаться написать более эффективной реализации.

volmir 30 янв 2018 в 13:38

Сама сложная задача (как это я вижу сейчас) — сгенерировать эти самые 4.1804 E+18 комбинаций (за разумное время и минимально возможными ресурсами процессора).
А как их проверить — можно будет потом уже придумать (алгоритм составить или закешировать).
А если на Си (или ином языке программирования, каком?) написать перебор комбинаций, быстрее будет работать? Насколько быстрее, нежели на PHP? Не сталкивался с такими задачами раньше, хочется посоветоваться.

arandomic 30 янв 2018 в 14:12

Вы неправильно разбили задачу на подзадачи.
Не нужно генерировать комбинации.
Вообще.
Никак.

Нам не важен порядок букв в словах.
Нам важны множества букв и именно множества букв мы будем сравнивать.

Словарь необходимо хранить в предобработанном виде. (см мой комментарий)
Введенное пользователем слово преобразуем в описание множества букв.
Вот пример ваш со словом «мартенсит»:
мартенсит = {аеимнрстт}
Весь наш словарь уже представлен в таком виде (в виде множества букв)
И нам не нужно искать среди слов сгенерированные слова — нам нужно найти все множества которые являются подмножеством множества {аеимнрстт}

Как хранить множества в памяти и как их сравнивать — вопрос реализации, да

volmir 30 янв 2018 в 14:21

Это именно то, что я искал.
О таком направлении я не думал вообще.
Спасибо вам огромное за идею и участие!
Буду пробовать реализовать подобный алгоритм.

MisterX 30 янв 2018 в 17:06

У меня таким образом работает разгадывание анаграм. База sqllite ~ 220 тыс слов. Поиск занимает 0,01 — 0,2 секунды.

volmir 31 янв 2018 в 12:56

Переделал систему по предложенной вами схеме (ищем слово в индексе из 65000 слов словаря). Теперь все летает!
Запрос из 20-ти символов выполняется с следующими результатами:
Память: 12.02 megabytes
Время: 0.500537 сек.

Сам запрос:

SELECT v.vocabulary_id, v.vocab 
FROM vocabulary v 
LEFT JOIN vector vkt ON v.vocabulary_id = vkt.id 
WHERE `vkt`.`ye` = 0 AND `vkt`.`y` = 0 AND `vkt`.`kh` = 0 AND `vkt`.`ts` = 0 AND `vkt`.`ch` = 0 AND `vkt`.`sh` = 0 AND `vkt`.`shch` = 0 AND `vkt`.`mgk` = 0 AND `vkt`.`yi` = 0 AND `vkt`.`tvd` = 0 AND `vkt`.`ee` = 0 AND `vkt`.`yu` = 0 AND `vkt`.`ya` = 0

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

Структура таблицы vector:


CREATE TABLE `vector` (
  `id` int(11) NOT NULL,
  `a` tinyint(1) NOT NULL DEFAULT '0',
  `b` tinyint(1) NOT NULL DEFAULT '0',
  `v` tinyint(1) NOT NULL DEFAULT '0',
  `g` tinyint(1) NOT NULL DEFAULT '0',
  `d` tinyint(1) NOT NULL DEFAULT '0',
  `e` tinyint(1) NOT NULL DEFAULT '0',
  `ye` tinyint(1) NOT NULL DEFAULT '0',
  `zh` tinyint(1) NOT NULL DEFAULT '0',
  `z` tinyint(1) NOT NULL DEFAULT '0',
  `i` tinyint(1) NOT NULL DEFAULT '0',
  `y` tinyint(1) NOT NULL DEFAULT '0',
  `k` tinyint(1) NOT NULL DEFAULT '0',
  `l` tinyint(1) NOT NULL DEFAULT '0',
  `m` tinyint(1) NOT NULL DEFAULT '0',
  `n` tinyint(1) NOT NULL DEFAULT '0',
  `o` tinyint(1) NOT NULL DEFAULT '0',
  `p` tinyint(1) NOT NULL DEFAULT '0',
  `r` tinyint(1) NOT NULL DEFAULT '0',
  `s` tinyint(1) NOT NULL DEFAULT '0',
  `t` tinyint(1) NOT NULL DEFAULT '0',
  `u` tinyint(1) NOT NULL DEFAULT '0',
  `f` tinyint(1) NOT NULL DEFAULT '0',
  `kh` tinyint(1) NOT NULL DEFAULT '0',
  `ts` tinyint(1) NOT NULL DEFAULT '0',
  `ch` tinyint(1) NOT NULL DEFAULT '0',
  `sh` tinyint(1) NOT NULL DEFAULT '0',
  `shch` tinyint(1) NOT NULL DEFAULT '0',
  `mgk` tinyint(1) NOT NULL DEFAULT '0',
  `yi` tinyint(1) NOT NULL DEFAULT '0',
  `tvd` tinyint(1) NOT NULL DEFAULT '0',
  `ee` tinyint(1) NOT NULL DEFAULT '0',
  `yu` tinyint(1) NOT NULL DEFAULT '0',
  `ya` tinyint(1) NOT NULL DEFAULT '0'
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

andreyvlv 30 янв 2018 в 21:28

Однажды делал такую же игру. Также начинал с генерации комбинаций. На 12-и или 13-и буквах программа искала слова около часа, что неприемлемо. Оказалось, что достаточно отсекать от словаря все неподходящие слова. Вот пример похожего поиска: bit.ly/2FuZT8G. Написан на C# (с PHP не сильно знаком), но в комментариях к коду постарался описать принцип работы.

volmir 30 янв 2018 в 21:46

Спасибо, сейчас читаю код. В принципе, все понятно (алгоритм), осталось разобраться в деталях :)

volmir 30 янв 2018 в 13:49

Сейчас алгоритм работает следующим образом:
1) Генерируются блоки комбинаций (размер блока: 50000-100000 слов) (66% времени на итерацию).
2) Этот блок проверяется на наличие в словаре (34% времени на итерацию).
Далее цикл повторяется…

Т.е. оптимизировать надо и первый шаг и второй.

ShakhnoDV 30 янв 2018 в 13:12

С таким количеством возможных комбинаций легче просматривать все 65000 слов и проверять подходят ли они под введенное слово.

volmir 30 янв 2018 в 13:16

Все равно, потребуется сравнить 65000 слов и 4.1804 E+18 вариантов.
Базу из 65000 слов можно полностью закешировать.
Задача разлагается на две подзадачи:
1) Сгенерировать 4.1804 E+18 комбинаций.
2) Проверить сгенерированные комбинации в словаре из 65000 слов.

ShakhnoDV 30 янв 2018 в 15:28

Потребуется только сравнить 65000 слов и одно введенное слово. Нет необходимости генерировать все возможные варианты

doctorpepper608 30 янв 2018 в 14:22

некоторые слова некоректны и нужно отбрасывать. Например, при наборе api.combination.cf/web/words/%D0%90%D0%91%D0%92%D0%93%D0%94%D0%95%D0%96%D0%97%D0%98:

1. api.combination.cf/web/description?word=%D0%B1%D0%B5
2. е и ё — одинаковы api.combination.cf/web/description?word=%D0%B5%D0%B6

volmir 30 янв 2018 в 14:30

Да, конечно. Когда наберется достаточная статистика и пропарсятся все доступные словари (например, сейчас в базе не хватает современных слов, вошедших в язык за последнее десятилетие) — можно будет «ручками» или автоматически пройтись по словам, откорректировать их.

boilroom 30 янв 2018 в 14:35

Кстати, у вас на страницах «Значения слова» неправильно написан page title. Сейчас там «еж — значание слова».

Ссылка: api.combination.cf/web/description?word=%D0%B1%D0%B5

volmir 30 янв 2018 в 14:48

Спасибо, исправил.

JuniorNoobie 30 янв 2018 в 14:57

Думаю, что в сети уже должны быть словари, в которых у слова можно выбрать следующие параметры: имя нарицательное, существительное, именительный падеж, единственное число. Затем этот словарь загружаем в свою базу данных, ибо читать с файлика каждый раз слова… ну это так себе. Затем строим индексы по количеству букв. Затем пишем запрос и вуаля: готова выдача всех возможных комбинаций слов.

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

volmir 30 янв 2018 в 15:00

Спасибо за идеи.
Над пользовательским интерфейсом ещё работать и работать.

Ещё одна интересная фишка (увидел её в аналогичных сервисах): «получить подсказку».
Т.е. при нажатии на кнопку выводится в модальном окне толкование одного или нескольких неразгаданных слов.

volmir 30 янв 2018 в 15:05

В Сети есть словари русского языка в текстовом формате:
www.speakrus.ru/dict

volmir 30 янв 2018 в 15:14

И ещё один источник:
www.knigitxt.com/category/diction/1

bi0w0rm 30 янв 2018 в 16:00

Сейчас после успешного или неуспешного набора слова фокус уходит из поля ввода. Чтобы начать вводить следующее слово, приходится либо табом фокус листать, либо мышь брать. А хочется: ввести слово — нажать Enter, ввести слово — нажать Enter и т.д. Было бы очень приятно, если бы фокус оставался в поле ввода.

IhorL 31 янв 2018 в 09:03

В дизайне UI заложена проблема изначально. Видимо из-за попытки попробовать React и получилось, что-то вроде (зато работает). Ушел от Jquery как писал в статье, но все равно добавил в проект. И даже имея Jquery, создал статические страницы с submit всей страницы саму на себя. За попытку молодец. Но… в погоне за React делаем откат лет на 10 назад.
Говорим об оптимизации и вместо чистого запроса нового слова, перегружаем каждый раз страницу на POST снова генерим ее клиенту. В итоге чтобы побороть неудобство фокуса, добавим костыль с установкой фокуса после отрисовки страницы. И так далее, с ростом UI, костыли будут только рости.
Напоминает попытку, перфоратором закручивать шурупы… да это возможно, но вроде и глупо.

volmir 31 янв 2018 в 09:54

На React JS написан отдельный сайт: js.combination.cf
Но там функционал обрезанный (по сравнению с полной версией api.combination.cf/web), есть ряд особенностей связанных с хостингом (локально работает — на хостинге «нет»).
Разрабатывать удобный, современный и функциональный UI — мне этому ещё учиться и учиться. Пока в приоритете бекэнд (60-70% усилий), на фронтенд — оставшиеся 30-40%.

volmir 7 фев 2018 в 19:20

Сделал ряд доработок по интерфейсу:
1) Фокус автоматически ставится в поле ввода (после загрузки страницы).
2) Добавил на гл. страницу форму с случайными словами, в которые можно поиграть, перейдя одним кликом по кнопке.
3) Описание отгаданного слова в игре теперь выводится в модальном окне (без перезагрузки страницы).
4) Почищена база слов (от глаголов, прилагательных, наречий, союзов и т.п.)
5) Добавлен функционал «Получить подсказку».
6) Разные мелкие правки текстов, описаний, подсказок, заголовков и т.п.

bi0w0rm 7 фев 2018 в 23:26

Поиграл немного, с фокусом стало очень приятно. Выбрал предложенное слово «Каменистость» и принес вам новых фактов насчет словаря:
1) В словаре отсутствуют: оттиск, насест, тост, кастет, тать, нить, темнота.
2) Наречия и глаголы все еще присутствуют в словаре: мести, намести, никто, таки, есть.
3) Подсказки иногда показывают слово в другом падеже, например, подсказка для слова «намек» содержит пример «ни намека на...». Для слова кистень — «разбойник с кистенем». Еще сок, сонет, сан.

Еще поддержу мысль, что выше изложил JuniorNoobie: сортировка отгаданных слов была бы очень уместна. Успехов вам!

volmir 8 фев 2018 в 00:01

Спасибо за бета-тест и отзыв :)

basakov_new 30 янв 2018 в 17:07

Начал тестировать — залип)
Спасибо, давно не играл!

volmir 30 янв 2018 в 17:08

Я рад, что игра вам понравилась.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий