image

Хочу поделиться своим опытом работы над веб-проектом: реализацией игры «Составь слова». Игра представляет собой известную головоломку, в которой нужно составлять разные слова из одного длинного слова.

Суть статьи — в том, как именно и что конкретно пришлось сделать, чтобы довести всю задумку от идеи до реализации.

Введение


Время от времени я играл в «бумажный» вариант этой игры: мы загадывали длинное слово (например: «Трицераптос» или «Спасо-Преображенский») и за 7-10 минут старались составить как можно больше слов из имеющихся букв. Затем — по очереди называли свои слова, повторяющиеся у соперников вычеркивали. У кого последнего оставались слова — тот и выиграл.

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

Требования к проекту были такими:

  • не сложный, но и не легкий (по применяемым навыкам и технологиям);
  • со сроком реализации примерно в месяц (± две недели, чтобы не затянулся надолго, но и не успел надоесть)
  • с применением современных технологий и знаний, которые мне не известны (профессиональное развитие)
  • интересный по сути
  • общественно-полезный

При всей кажущейся простоте, придумать такую идею сходу у меня долго не получалось. Я обдумывал различные варианты, откладывал, прикидывал — и наконец идея полностью «созрела», обрела четкость и конкретные рамки. Начался этап активных действий, раздумывания остались позади.

План работ, задумки, идеи, архитектура


Общая идея выглядела следующим образом: система будет состоять из бекэнда и фронтэнда (одного или нескольких). На бекэнд возлагается основная нагрузка по расчетам, реализации логики и математики. В виде входных данных на него приходит длинное слово (для разгадывания), результат работы — данные об возможных существующих в русском языке вариантах комбинаций слов. Данные отдаются в формате JSON, бекэнд работает в виде REST-сервиса.

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

На данный момент реализованы два метода АПИ на бекэнде:

http://api.combination.cf/web/words/портал
http://api.combination.cf/web/description/механизм


Первый метод отдает возможные комбинации слов, второй — предназначен для толкования значения конкретного слова.

1. Бекэнд


1.1. Словарь, база слов


Чтобы какие-то слова пользователю выдавать, надо их сначала знать и где-то хранить. Изначально собирался парсить какой-то большой онлайн-словарь или базу знаний (БСЭ, Википедия и т. п.). Но, поискав в Сети, нашел уже собранные и готовые толковые словари в виде отдельных файлов (в текстовом формате). Парсить их, конечно же было намного проще, нежели выкачивать в несколько потоков и разбирать десятки тысяч страниц с сырыми данными. Не говоря уже о том, что список страниц для парсинга так же надо было подготовить.

Базой для игрового словаря послужили следующие источники:

  1. Ожегов С. И. Словарь русского языка. Ок. 65 000 слов / 16-е изд., — М.: 1984.
  2. Ефремова Т. Ф. Толковый словарь. — М.: Рус. яз., 1996.

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

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

Если удастся использовать все буквы исходного слова — то получится анаграмма (Анаграмма — литературный приём, состоящий в перестановке букв или звуков определённого слова, что в результате даёт другое слово или словосочетание).
Пример: австралопитек — ватерполистка.

1.2. Размещения без повторений


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

Из длинного выражения можно составлять короткие слова различной длины. Значит, нам нужна комбинаторика, раздел «Размещения без повторений». Будем искать слова длиной от 2-х до («длина слова» — 1) символов.

Рассчитаем, сколько вариантов нам надо будет перебрать при различной длине исходного слова. Применим следующую формулу:

image

Некоторые основы комбинаторики под спойлером

Сочетания, размещения, перестановки.


В комбинаторике размещением (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.

Элементами множества могут быть числа, буквы и вообще любые объекты. Главное, чтобы эти элементы были различными. Т. к. любому объекту можно сопоставить число, то обычно используют конечное множество целых чисел, например, {1; 2; 3; 4; 5}. Хотя множества из букв также можно часто встретить в литературе.

Пример: некоторые размещения элементов множества {А, Б, В, Г, Д}:
по два элемента: {А, Б}, {Б, Д}, {Г, А}
по три элемента: {Д, А, Б}, {А, Б, Д}, {Г, Б, В}
по четыре элемента: {Д, А, Б, Г}, {А, Б, Д, В}

В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например наборы {А, Б, В} и {В, Б, А} являются различными, хотя и состоят из одних и тех же элементов {А, Б, В} (то есть совпадают как сочетания).

Число размещений без повторений из десяти элементов по K:
К
Количество размещений
1 10
2 90
3 720
4 5040
5 30240
6 151200
7 604800
8 1814400
9 3628800
Всего: 6235300

Число вариантов для проверки слова длиной N символов:
(суммируем все варианты размещений для слова данной длины)
N Количество вариантов для проверки
2 2
3 9
4 40
5 205
6 1236
7 8659
8 69280
9 623529
10 6235300
11 68588311
12 823059744
15 2246953104075
20 4180411311071440000
25 2.6652630354867E+25

1.3. Бекэнд, YII2


Бекэнд реализован на PHP (YII2), в качестве БД выбран MySQL, кеширование — Memcached. Здесь все просто: создаем отдельный модуль для API, пишем необходимые выборки из базы. Данные отдаем в формате JSON.

1.4. Оптимизация


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

Изначально оптимизировал работу с памятью. При передаче слова длиной в восемь символов скрипт падал с ошибкой:

PHP Fatal error: Out of memory (allocated 128545216) (tried to allocate 77824 bytes) in /home/xxxxx/public_html

Этот вопрос удалось решить с использованием генераторов в PHP-коде. Функция стала отдавать данные частями, а не накапливать весь результат в себе. Так же помогло использование функции mysql_free_result($result) для высвобождения всей памяти, занимаемой результатом запроса к БД. Использование памяти теперь не превышало 12-14 Мб.

Использование процессора. Изначально нагрузка на ЦП составляла 100% во все время работы скрипта. Путем оптимизации кода и разбиения запросов на большее количество мелких (вместо небольшого количества больших) запросов удалось снизить нагрузку до 60-80%.

Оптимизация времени работы скрипта была достигнута путем использования
Memcached для хранения списка всех слов из словаря. Таким образом удалось убрать нагрузку на MySQL и ускорить время получения результата. Как альтернативу я перепроверил так же и файловый кеш FileCache, но здесь результаты были хуже, нежели Memcached.

Результаты оптимизации


На локальном сервере (четырехядерный процессор) время перебора всех комбинаций для слова из 10-ти букв составляет около 22 секунд. При этом два ядра загружены на 60% — 80% постоянно. Eщё 10-11 секунд требуется на проверку всех этих комбинаций в словаре (при использовании Memcached).

Итого (для слова из 10 символов): 22 сек. (генерация вариантов) + 10 секунд (проверка слов) = 32 секунды (общее время работы).

Рост времени линейный: 9 символьное слово проверяется примерно за 3 секунды, 10 символов — за 32 секунды, 11 символов — 350 секунд.

Т.е. слова из 11-ти букв уже недоступны (за разумное время) для перебора вариантов (для данного алгоритма, при данном железе); 10 символов — более-менее терпимо, предел; 9 и менее — достаточно быстро, незаметно для пользователя.

2. Фронтэнд


Я решил написать два фронтенда (исходя из поставленных целей). Один на PHP (YII2) — основной рабочий вариант игры «Угадай слова» с полным пользовательским функционалом; второй на React JS — то же самое клиентское приложение, но с сокращенным функционалом (учебный проект для изучения JS).

Реализовывать функционал игры на PHP (YII2) + верстка Bootstrap было просто, быстро и приятно. Программирование в удовольствие, творческое занятие: создавай (и придумывай, дорабатывай на ходу) интерфейсы взаимодействия с пользователем, диалоговые окна, элементы меню, кнопки; наполняй страницы контентом, выводи информационные сообщения; делай для всего этого дизайн; продумывай редиректы и т. п.

А вот с React JS у меня было все не так просто. Вылезли пробелы в знаниях, пришлось заново повторять и проходить основы JavaScript (помимо изучения особенностей самой библиотеки React JS). Иногда приходилось по несколько часов искать как сделать простейшее действие: скачать файл, вывести блок текста. Но так и планировалось изначально: знаниями HTML + Jquery сейчас уже не отделаешься. В результате получился собранный билд статического сайта для выгрузки на хостинг.

Пользователю игры доступны следующие варианты взаимодействия:

  1. Игра в слова — загадывается большое длинное слово, можно придумывать варианты и проверять их. Найденные слова сохраняются, ведется подсчет статистики, выдаются информационные сообщения (слово найдено/не найдено, ошибка, комбинация уже отгадана и т. п.). Игру можно отложить и продолжить в другое время. Игру можно завершить или начать заново.
  2. Поиск слов — просто показываются все возможные комбинации слов, которые можно составить из исходных букв. Некий вариант «подсказки» для игры или отдельный сервис.
  3. Значение слова — показывается толкование отгаданного или сгенерированного слова. Онлайн вариант электронного словаря.

image

3. Хостинг


Ничего особо нового здесь не напишу, надо подбирать хостинг под конкретный проект, исходя из требований и возможностей. Из того что удивило — почти у всех компаний качественная техподдержка: отвечают быстро и по сути, помогают решить возникшие затруднения. На собственном опыте убедился, что работа сисадмина и девопса нужна и важна.

Возможные доработки и идеи


Можно двинуться в двух направлениях: оптимизировать бекэнд (сделать работу АПИ более быстрой) и фронтэнд (расширять и «шлифовать» интерфейсы работы с пользователями). Оба варианта являются перспективными.

Бекэнд — наверное, здесь возможностей PHP для быстрой обработки большого объема цифровых данных будет недостаточно. Возможно подойдет написание некого отдельного быстрого модуля или скрипта на ином языке программирования, который бы быстро делал все расчеты. Может, что-то из результатов можно закешировать!? Для быстрой переборки словаря скорее всего стоит посмотреть в сторону NoSQL баз данных. Так же уместным видится увеличение сервисов (возможностей) системы.

По пользовательскому интерфейсу — здесь уместным будет привлечение специалистов по игровому дизайну в качестве консультантов (или сесть самому и пару вечеров подумать, что можно быстро и просто реализовать, все мы играли за свою жизнь в сотни разных компьютерных игр): продумывание игровых интерфейсов, расширение сервисов, добавление регистрации пользователя, сбор статистики, таблицы рекордов, сохраненные игры и т. п.

Не лишним будет, наверное, покрытие кода тестами (приемочными на фронтэнде и юнит-тестами на бекенде). Чтобы не тестировать все вручную снова и снова при обновлениях и расширении функционала.

Заключение


Вообще лингвистика и филология, оказывается, это очень интересно само по себе. Узнал много нового об русском языке в процессе работы над проектом.

Приведу ссылки на исходные коды в репозиториях и ссылки на рабочий сайт (хостинг — базовый VPS, возможно «падение» сайта под «Хабраэффектом»).

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

Сайт с игрой
Репозиторий с бекэндом (АПИ) и фронтэндом (PHP)
Репозиторий с фронтендом на React JS

Комментарии (26)


  1. volmir Автор
    30.01.2018 12:40

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

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

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

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


    1. arandomic
      30.01.2018 13:22

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

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

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


      1. volmir Автор
        30.01.2018 13:38

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


        1. arandomic
          30.01.2018 14:12

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

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

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

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


          1. volmir Автор
            30.01.2018 14:21

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


            1. MisterX
              30.01.2018 17:06

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


          1. volmir Автор
            31.01.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;
            


        1. andreyvlv
          30.01.2018 21:28

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


          1. volmir Автор
            30.01.2018 21:46

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


      1. volmir Автор
        30.01.2018 13:49

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

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


  1. ShakhnoDV
    30.01.2018 13:12

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


    1. volmir Автор
      30.01.2018 13:16

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


      1. ShakhnoDV
        30.01.2018 15:28

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


  1. doctorpepper608
    30.01.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. volmir Автор
      30.01.2018 14:30

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


      1. boilroom
        30.01.2018 14:35

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

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


        1. volmir Автор
          30.01.2018 14:48

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


      1. JuniorNoobie
        30.01.2018 14:57

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

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


        1. volmir Автор
          30.01.2018 15:00

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

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


        1. volmir Автор
          30.01.2018 15:05

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


          1. volmir Автор
            30.01.2018 15:14

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


  1. bi0w0rm
    30.01.2018 16:00

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


    1. IhorL
      31.01.2018 09:03

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


      1. volmir Автор
        31.01.2018 09:54

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


  1. basakov_new
    30.01.2018 17:07

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


    1. volmir Автор
      30.01.2018 17:08

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