SQL HowTo: делаем из мухи слона (алгоритм Ли)

Правила игры очень просты: надо построить цепочку слов от начального (МУХА) до конечного (СЛОН), на каждом шаге меняя только одну букву. При этом могут использоваться только русские 4-буквенные нарицательные существительные в начальной форме: например, слова БАЗА, НОЧЬ, САНИ допускаются, а слова ЛИТЬ, ХОТЯ, РУКУ, НОЧИ, САНЯ, ОСЛО, АБВГ, ФЦНМ — нет.

Эта игра под названием «Дублеты» приобрела известность благодаря Льюису Кэрроллу — не только автору книг про Алису, но ещё и замечательному математику. В марте 1879 года он начал раз в неделю публиковать в журнале «Ярмарка тщеславия» по три задания в форме броских фраз: «Turn POOR into RICH» — «Преврати бедного в богатого», «Evolve MAN from APE» — «Выведи человека из обезьяны», «Make TEA HOT» — «Сделай чай горячим». В том же году он выпустил брошюру «Дублеты», подробно описал в ней правила и предложил читателям попрактиковаться на нескольких десятках примеров.

Александр Пиперски, "Из мухи — слона", «Квантик» №2, 2019 и №3, 2019

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

Загружаем словарь

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

CREATE TABLE dict AS
SELECT
  btrim(word) word    -- зачищаем пробелы с обеих сторон
FROM
  regexp_split_to_table($$
абажур
абажурчик
абаз
абазин
-- ...
  $$, E'[\r\n]') word -- делим текст на строки
WHERE
  word !~ '^\s*$';    -- загружаем только непустые строки

Формируем пары

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

Для этого нам понадобится проиндексировать словарь для быстрого поиска по LIKE:

CREATE EXTENSION pg_trgm;
CREATE EXTENSION btree_gin;

CREATE INDEX ON dict USING gin(
  length(word)      -- для этого - btree_gin
, word gin_trgm_ops -- для этого - pg_trgm
);

Здесь мы использовали расширение pg_trgm для поддержки индексного поиска по триграммам (что, в том числе, дает быстрый поиск по шаблонам и регулярным выражениям) и btree_gin для использования скаляров в gin-индексах:

CREATE TABLE pair AS
WITH src AS (
  SELECT
    word
  , array_agg( -- 'муха' -> {'_уха','м_ха','му_а','мух_'}
      substr(word, 1, i - 1) || '_' || substr(word, i + 1)
    ) patterns -- массив всех возможных LIKE-шаблонов замены одной буквы
  FROM
    dict
  , LATERAL
      generate_series(1, length(word)) i -- перебираем номера букв слова
  GROUP BY
    1
)
SELECT
  src.word src
, dst.word dst
FROM
  src
, LATERAL (
    SELECT
      word
    FROM
      dict
    WHERE
      length(dict.word) = length(src.word) AND -- ищем только в той же длине
      dict.word LIKE ANY(src.patterns) AND     -- одновременно по набору шаблонов
      dict.word <> src.word                    -- исключая исходное слово
  ) dst;

Правильный индекс позволил нам сформировать все пары возможных переходов для 51 тысячи слов всего лишь чуть дольше, чем за минуту [посмотреть план на explain.tensor.ru].

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

CREATE UNIQUE INDEX ON pair(src, dst);

Запускаем "волны"

Сначала запомним в CTE, что во что нам надо превратить:

WITH RECURSIVE param(src, dst) AS (
  VALUES('муха', 'слон')
)

Запускаем "волну" от источника к цели:

, s2d AS (
  SELECT
    0 i             -- счетчик шага
  , ARRAY[src] path -- уже пройденный волной путь
  , ARRAY[src] diff -- "прирост" на новом шаге
  FROM
    param
UNION ALL
  SELECT
    i + 1
  , T.path || dst$
  , dst$
  FROM
    s2d T
  , LATERAL (
    SELECT
      array_agg(dst) dst$
    FROM
      pair
    WHERE
      src = ANY(T.path) AND -- для всех слов-оснований добавляем слова-следствия
      dst <> ALL(T.path)    -- которые еще не принадлежат пути
  ) X
  WHERE
    (SELECT dst FROM param) <> ALL(path) AND -- останавливаемся, дойдя до цели
    i < 100                                  -- не более чем за 100 шагов
)

Теперь в обратную сторону - от цели к источнику:

, d2s AS (
  SELECT
    (SELECT max(i) FROM s2d) i -- мы уже знаем, сколько шагов понадобится
  , ARRAY[dst] path
  , ARRAY[dst] diff
  FROM
    param
UNION ALL
  SELECT
    i - 1 -- счетчик теперь идет "вниз"
  , T.path || dst$
  , dst$
  FROM
    d2s T
  , LATERAL (
    SELECT
      array_agg(dst) dst$
    FROM
      pair
    WHERE
      src = ANY(T.path) AND
      dst <> ALL(T.path)
  ) X
  WHERE
    (SELECT src FROM param) <> ALL(path) AND
    i > 0
)

Заметим, что элементы нашего искомого пути должны входить в diff'ы с одинаковыми номерами шагов и "от мухи" и "от слона" - иначе мы могли бы сократить такой путь. То есть нам достаточно всего лишь найти пересечения diff-массивов:

SELECT
  ARRAY( -- свернули обратно в массив
    SELECT unnest(X.diff) -- развернули первый массив
  INTERSECT ALL           -- нашли пересечение
    SELECT unnest(Y.diff) -- развернули второй массив
  ) path
FROM
  s2d X
JOIN
  d2s Y
    USING(i);

В результате, получаем нашу итоговую цепочку всего за полсекунды:

муха - мура - фура - фара - фарт - фаут - паут - плут - плот - клот - клон - слон

WITH RECURSIVE param(src, dst) AS (
  VALUES('муха', 'слон')
)
, s2d AS (
  SELECT
    0 i
  , ARRAY[src] path
  , ARRAY[src] diff
  FROM
    param
UNION ALL
  SELECT
    i + 1
  , T.path || dst$
  , dst$
  FROM
    s2d T
  , LATERAL (
    SELECT
      array_agg(dst) dst$
    FROM
      pair
    WHERE
      src = ANY(T.path) AND
      dst <> ALL(T.path)
  ) X
  WHERE
    (SELECT dst FROM param) <> ALL(path) AND
    i < 100
)
, d2s AS (
  SELECT
    (SELECT max(i) FROM s2d) i
  , ARRAY[dst] path
  , ARRAY[dst] diff
  FROM
    param
UNION ALL
  SELECT
    i - 1
  , T.path || dst$
  , dst$
  FROM
    d2s T
  , LATERAL (
    SELECT
      array_agg(dst) dst$
    FROM
      pair
    WHERE
      src = ANY(T.path) AND
      dst <> ALL(T.path)
  ) X
  WHERE
    (SELECT src FROM param) <> ALL(path) AND
    i > 0
)
SELECT
  ARRAY(
    SELECT
      unnest(X.diff)
  INTERSECT ALL
    SELECT
      unnest(Y.diff)
  ) path
FROM
  s2d X
JOIN
  d2s Y
    USING(i);