Алгоритм быстрого поиска слов в игре балда

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


    Из нестандартных правил выделяется довольно интересный режим «узелки», в котором составлять слово можно, используя одну букву до 2-х раз (например, на скриншоте сверху можно составить слово ШАЛАШ, буквы Ш и А использованы 2 раза). Как потом выяснилось, в одной и той же позиции алгоритм ищет все слова в режиме узелки почти ровно в 1.5 раз дольше, чем в классическом режиме без узелков (это и не удивительно, т.к. вариантов составления слов больше и найденные слова длиннее). В конце статьи описанный алгоритм будет протестирован в тестовой позиции в режиме узелки.

    Словарь


    Для того чтобы ещё больше затруднить жизнь алгоритму будет использоваться один из самых больших словарей в подобных программах. Он насчитывает примерно 110000 слов.
    Важную роль в алгоритме играет способ хранения словаря в памяти программы. При загрузке каждое слово записывается в структуру в виде дерева. Каждый узел этого дерева означает конкретную букву слова и ссылается на не более чем 32 поддерева (по количеству букв в алфавите). Узел дерева в программе выглядит так:
    typedef TREE *NEXT;     //указатель на следующую букву 
    struct TREE 
    { 
        NEXT *next;         //массив указателей на все возможные следующие буквы 
        char *str;          //строка со всеми возможными следующими буквами 
        char *wrd;          //если не NULL, то это слово из словаря 
    }; 

    В поле str содержится строка со всеми буквами, которые выходят из данного узла, размер массива next[] равен длине этой строки.
    Поле str используется для нахождения конкретного узла среди массива узлов next[] для данной буквы. Для этого введена функция ind(), основанная на strchr():
    int k=ind('и',str);         //возвращает индекс (позицию) буквы ‘и’ в строке str 

    Если k<0, то данной буквы нет в str, иначе next[k] указывает на узел, соответствующий этой букве. Например, если str содержит строку "аоикт", то из этого узла идут ровно 5 поддеревьев, причем next[2] ссылается на букву 'и', т.к. str[2]== 'и', то же самое и с другими буквами.
    Для иллюстрации всего вышеописанного приведу пример дерева на специально подготовленном словаре, состоящем из слов:
    балда, банка, бар, манка, барсук
    


    Если поле str==NULL, то данный узел является листом и в нём содержится словарное слово wrd. Узел, соответствующий букве 'р', содержит слово "бар", и при этом он не является листом, потому что в данном словаре есть ещё одно слово, начинающееся на бар-. Поле wrd содержит строку, которая получается, если идти от корня к соответствующему узлу, но если эта строка не является словарным словом, то wrd содержит NULL.
    Назовём это дерево словарным, в нём содержатся все слова из словаря. Помимо словарного дерева необходимо подготовить ещё одно, в котором содержатся все возможные инвертированные префиксы слов для каждого слова (назовём это дерево инвертированным). К примеру, для слова "балда" в инвертированное дерево попадут следующие строки: "адлаб", "длаб", "лаб", "аб", "б". Даже для тестового словаря с пятью словами такое дерево будет громоздким, поэтому приведу упрощенный вариант:

    Слова Префиксы словарных слов в этом дереве расположены задом-наперед. Узел в красном кружочке соответствует последней букве инвертированного префикса словарного слова, т.е. соответствует первой букве этого слова. Чтобы прочитать начало словарного слова нужно двигаться от красного узла к корню. Единственное отличие инвертированного дерева от словарного – это то, что wrd выполняет роль флага (NULL/не NULL). Т.е. в нем хранится не строка с инвертированным префиксом слова, а:

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

    Это сделано для экономии места. Для всех красных узлов wrd!=NULL, для остальных wrd==NULL. К примеру:
    root_inv->str == ”адлбкнрусм”; 
    root_inv->next[0]->str == ”бдкм”; 
    root_inv->next[5]->next[0]->wrd == NULL; //АН не является префиксом словарного слова 
    root_inv->next[5]->next[0]->next[1]->wrd != NULL; //МАН является префиксом словарного слова
    


    Оба дерева занимают в памяти 33М, и непосредственно из словаря они строятся примерно за 5 секунд на i5, поэтому было принято решение сохранить образ деревьев в файл и в дальнейшем грузить именно его. Так скорость загрузки составила всего 300 миллисекунд.

    Алгоритм поиска


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

    Затем нужно составить слово, используя поставленную букву. Данная буква может быть как первой буквой в слове, так и не первой буквой (хоть и капитанство, но это важно). Если бы в правилах было сказано, что поставленная буква должна быть точно первой, то просто используем словарное дерево, двигаясь по полю от поставленной буквы одновременно спускаясь вниз по дереву. Но т.к. поставленная буква может и не быть первой, словарное дерево использовать нельзя, потому что не известно с какого именно узла начинать поиск. Но у нас ещё есть инвертированное дерево.
    Идея такая: из клетки с поставленной буквой движемся по полю, спускаясь по инвертированному дереву. Если находим узел, у которого wrd!=NULL (красный узел), значит это валидный инвертированный префикс слова. Имея префикс слова, можно в словарном дереве найти узел, соответствующий поставленной букве, и далее просто «донайти» оставшийся кусок слова уже в словарном дереве, начиная с этого узла.
    Для того чтобы алгоритм не заходил в клетки, которые ранее для данного слова уже прошёл, в каждой клетке имеется счетчик использования count. Перед началом поиска этот счетчик инициализируется числом 2 (для режима узелки) или 1 (для классического режима) – это единственное отличие режимов с точки зрения алгоритма.
    Более подробный алгоритм:
    • 1) Перебираем все пустые смежные клетки
    • 2) Для каждой клетки перебираем все буквы алфавита (32 буквы)
    • 3) Заносим в текущую клетку (пусть её координаты будут [x, y]) текущую букву s. Так получаем 32*n разных позиций, где n – число смежных клеток в исходной позиции
    • 4) Занесенную букву считаем первой буквой для инвертированных префиксов.
      Поэтому среди root_inv->next[] находим узел t_inv, соответствующий текущий букве, т.е. t_inv – поддерево, начинающееся с текущей буквы:
      int k = ind(s, root_inv->str);	//s – текущая буква
      if(k<0) continue;		//вдруг инвертированный префикс не может начинаться с этой буквы
      TREE * t_inv = root_inv->next[k];
      
    • 5) Уменьшаем count[x, y] и вызываем функцию поиска в поддереве find (о которой ниже) для t_inv и клетки [x, y]
    • 6) Конец цикла по буквам
    • 7) Конец цикла по смежным клеткам

    Естественно после цикла по буквам очищаем текущую смежную клетку.
    Функция поиска в поддереве find принимает игровое поле, узел дерева (tree) и координаты клетки (i, j), с которой необходимо начать двигаться по полу, спускаясь по дереву tree:
    • 1) Если tree->wrd!=NULL, то найдена валидная подстрока
      • a. Если этот узел принадлежал словарному дереву, то эта подстрока вообще словарное слово, добавляем tree->wrd в массив найденных слов.
      • b. Если узел принадлежал инвертированному дереву, то эта подстрока является инвертированным префиксом слова. В словарном дереве находим узел t, соответствующий этому префиксу, и вызываем функцию find для t и клетки [x, y] (внимание! Не та клетка, которую передали в эту функцию, а клетка, в которую алгоритм сходил на шаге 3):
        TREE *t=root;			//корень словарного дерева
        loopi(strlen(prefix))		//prefix содержит найденный инвертированный префикс
        {
        	int k=ind(prefix[i],t->str);
        	t=t->next[k];
        }
        find(t,x,y);
        
    • 2) Независимо от значения tree->wrd продолжаем
    • 3) Перебираем клетки, смежные с [i, j] (от 2-х в углу до 4-х в центре поля)
    • 4) Анализируем содержимое текущей смежной клетки [i1, j1]
      • a. Если она пустая, то переходим на шаг (3)
      • b. Если буква, находящаяся в этой клетке, не имеется в tree->str, то переходим на шаг (3)
      • c. Если count[i1, j1]==0, то переходим на шаг (3)
      • d. Иначе переходим на шаг (5)
    • 5) Среди tree->next[] находим узел tnext, соответствующий букве в [i1, j1]
    • 6) Уменьшаем счетчик использования count[i1, j1] и вызываем find для tnext и клетки [i1, j1]
    • 7) Конец цикла по смежным буквам

    Рассмотрим работу алгоритма для центральной клетки на примере следующей позиции:

    Заносим в эту клетку каждую букву из строки ”адлбкнрусм” (остальные буквы алфавита просто не существуют в root_inv->str и алгоритм для них быстро завершится, даже не начавшись). Для каждой буквы вызываем find. Для буквы А функция быстро завершится, потому что в инвертированном дереве нет веток, начинающихся на АА-, АС- и АКУ-, то же самое и для Д, К, У, С.

    Для остальных букв в инвертированном дереве будут найдены валидные префиксы:
    Л – лаб, Б – б, Н – наб, Р – раб, М – м. Для каждого префикса находим узел в словарном дереве (как описано в п.1.b) и вызываем для него функцию find.
    Префиксу “бал” соответствует узел root->next[0]->next[0]->next[0]:

    Следующей смежной буквой может быть С или К, но в поле str этого узла содержится “д”, поэтому сразу завершаем функцию find, т.е. в дереве нет веток, начинающихся на БАЛС- и БАЛК-. Для префикса “б” в словарном дереве нет веток, начинающихся на БК-, БС-, БАБ-, БАЪ-, то же самое и для префиксов “бан” и “м”.

    Префиксу “бар” соответствует узел root->next[0]->next[0]->next[2].
    Т.к. поле wrd!=NULL, заносим строку wrd (БАР) в массив найденных слов и продолжаем поиск дальше. Для строк БАРК и БАРСЪ нет веток, завершаем для них функцию find, а вот строка БАРСУК содержится в дереве, помещаем её в массив найденных слов.

    Результаты


    Алгоритм тестировался на следующем поле (естественно уже не на тестовом словаре, а на словаре из 110000 слов):
    Скрытый текст

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

    • 1) Mac mini i7 – 7 миллисекунд (не нативное приложение, а в эмуляторе iPhone)
    • 2) Комп. с i5 – 12 миллисекунд
    • 3) iPad 4 – 30 миллисекунд
    • 4) Samsung Galaxy Ace (железо трёхлетней давности) – 50 миллисекунд (с использованием NDK)

    Для других позиций время поиска еще меньше.

    Приложение


    Данный алгоритм применен в приложениях для iOS (доступно в app store) и Android. Помимо поиска всех слов реализованы ещё два вида поиска:

    • 1) Локальный поиск – если пользователю позарез нужно занять какую-либо определённую пустую клетку (например, призовая клетка, или прикрыть своим ходом клетку, в которой слишком много длинных слов), тогда он делает двойной тап по этой клетке и программа ищет только те слова, которые можно сходить в неё
    • 2) Проверка подстав – двойной тап по букве заставит программу найти все слова, проходящие через эту букву. Применение: сразу после хода соперника проверить его букву (вдруг он жестко подставился), перед своим ходом следует проверить предполагаемый ход на предмет подстав

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

    Похожие публикации

    Комментарии 22
      +2
      За статью спасибо!

      Вопросы:
      1) доступен ли код?
      2) при чем тут C++?
        +4
        1) если кому-то интересен код, могу его добавить
        2) ну некоторые вставки на плюсах же, и опять же вдруг таки код добавлю (а он на С++)
          +8
          1) Github, bitbucket — конечно добавляйте!
          2) Ну все, что в статье, выглядит как код С. Тот же NULL, например.
        +2
        Если я вас правильно понял, вы ошиблись: не в узле хранится буква слова, а в ребре дерева; узлу соответствует строка, которую можно восстановить, возвращаясь вверх по дереву. На сколько я помню, такое дерево называется бором, или префиксным деревом.
          +2
          ну естественно физически в узле никакая буква не хранится, я так писал для понятности
          0
          Можно radix tree сделать (всмысле объединить узлы с одним чайлдом) — будет меньше места есть.
            +2
            Не факт — в словаре из слов русского языка узлов с одним чайлдом не так много. При этом, чтоб узлы объединять, нужно объединенные строки хранить. Т.е. видимо, это дополнительный указатель + байт-другой для длины на каждый узел.

            Radix tree может память сэкономить, когда строк немного, или когда они длинные.
              +1
              А у меня как минимум для первого дерева из статьи (если я всё правильно понял и не накосячил с тупой реализацией) получилось что одиночных чайлдов в районе 67% (такой код и такой словарь). Для префиксного возможно чуть похуже будет.
                +1
                Хотя это не сильно много, да.
            0
            А где же сами приложения? Интересует Android версия.
              0
              ios-версия в app store называется «помощник для балды», андроид-версия сделана, но никуда не выложена
                0
                Планирует выложить?
                  0
                  я бы выложил, но у меня пока нет аккаунта разработчика гугл-плей, как появится — сразу выложу
              +1
              Понятно, что пройти путь самостоятельно интересно, но существуют уже готовые продвинутые решения.

              Описанное в топике — это нечто похожее на конечный автомат. А вот, превратив его в конечный детерминированный автомат, можно получить предельно эффективное решение. Конечный детерминированный автомат используется во многих лингвистических продуктах: морфология, проверка орфографии, словари и пр. Различных реализаций детерминированного конечного автомата огромное множество на любых языках. Самое сложная часть — это «построитель» такого автомата (существует несколько алгоритмов), а та часть, которая использует уже готовый автомат, вообще состоит из 2 страниц кода, которую можно реализовать на любом языке за минимальное время.

              Для примера, файл детерминированного конечного автомата, который состоит из 5 млн. русских слов (для использования проверки орфографии), занимает, как бы это было не удивительно, всего 2 МБ. Автомат можно загружать в память целиком, а можно «мэпить» в памяти. Второй случай идеально подходит для устройств с быстрым доступом к системе хранение (флеш память, например, телефоны и смартфоны) — он практически не требователен к ресурсам, а скорость для пользователя остаётся очень высокой. Это особенно актуально, когда нужно подключать несколько автоматов сразу (например, несколько языков).
                0
                А как вы предлагаете решать эту задачу с помощью DFA?
                  0
                  Так решение фактически ничем не отличается от того, что предложил автор, только основа более продвинутая. Автомат состоит из слов, каждая буква — это переход между состояниями. Для работы с автоматом используется лишь одна базовая функция — поиск слов по шаблону со спецсимволом, например, "*". Т.е. на входе подаётся что-то типа "*п*ар***ур", а на выходе получаем все состояния автомата (слова), которые удовлетворяют этому шаблону.
                    +1
                    на входе подаётся что-то типа "*п*ар***ур"

                    не много не понял, откуда берется такой шаблон? Ну т.е. как он формируется?

                    А вы бы могли реализовать эту задачу на основе таких автоматов, потом сравнили бы скорость поиска с моим алгоритмом (этакий челендж)
                0
                Интересно, когда человек проходит какую-то нетривиальную алгоритмическую задачу от начала и до конца.
                  0
                  Несколько лет назад тоже писал аналогичную программу, потому что надо было решать N на N, а найденные решения работали только в поле 5 на 5. Но у меня был совсем топорный и медленный алгоритм. С Вашим по скорости не сравнить! Но с поставленной задачей справлялся великолепно.

                  Я помню самое сложное было найти словарь именно существительных. Откуда у Вас словарь на 110 000 слов? И есть ли где-нибудь в открытом доступе специальные коллекции словарей?
                    0
                    Откуда у Вас словарь на 110 000 слов?

                    Я его взял из приложения балды в одной социальной сети, точнее из группы этого приложения.
                    И есть ли где-нибудь в открытом доступе специальные коллекции словарей?

                    Вот этого не знаю
                    0
                    Мне кажется логичным искать в AppStore по запросу «Балда»(буквально пару недель назад как раз искал решатель для айфона), но я не нахожу потому что у Вас в заголовке "… балды". Точнее нахожу Ваших конкурентов.
                    Может быть Вы теряете часть аудитории такой же как и я.
                      0
                      действительно, я и сам это заметил после публикации. Так-то в ключевых словах я указывал именно «балда».

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое