Посвящается памяти моего недавно ушедшего из жизни отца, Габриеля Бен-Гана. Он любил числа, логику и головоломки и обыкновенно находил своеобразные решения задач. В этой статье я предлагаю вашему вниманию одну очень интересную задачу и прежде всего хочу выразить благодарность Дэвиду Шипли, приславшему мне ее. Задача довольно проста, но для поиска решения необходим творческий подход.
В решении используется вспомогательная таблица с именем dbo.Nums, содержащая последовательность целых чисел, начиная с 1, в столбце с именем n. Вспомогательную таблицу можно найти в тестовой базе данных TSQLV3. Исходный текст для создания тестовой базы данных можно загрузить по адресу: tsql.solidq.com/books/source_code/TSQLV3.zip.
Задача
Задача заключается в копировании с опечатками ключевых слов, вводимых для поиска. Ввод состоит из трех строк:
- Ключевое слово, введенное пользователем для поиска (@keyword).
- Исходное слово (@src).
- Синоним исходного слова (@synonym).
Ниже приведен пример возможных входных значений:
DECLARE @keyword AS NVARCHAR (1000) = N'wwAMxxAMyyAMzz', @src AS NVARCHAR (1000) = N'AM', @synonym AS NVARCHAR (1000) = N'AN';
Необходимо сформировать все возможные перестановки входного @keyword, где каждый экземпляр @src заменяется на @synonym или не заменяется. Например, для приведенных выше входных значений желательный вывод имеет следующий вид:
wwAMxxAMyyAMzz wwANxxAMyyAMzz wwAMxxANyyAMzz wwANxxANyyAMzz wwAMxxAMyyANzz wwANxxAMyyANzz wwAMxxANyyANzz wwANxxANyyANzz
Итак, за дело.
Шаг 1. Формирование перестановок
Решение этой задачи можно разбить на пять этапов.
Первый шаг — получить последовательность целых чисел в диапазоне от 0 до num_permutations- 1, где num_permutations представляет число перестановок @keyword, которые нужно сформировать. Значение num_permutations может быть вычислено как 2^num_ocurrences, где num_occurrences — число экземпляров @src в @keyword. Для наших тестовых входных значений @src — AM, а @keyword — wwAMxxAMyyAMzz, поэтому num_ocurrences = 3, и, следовательно, num_permutations = 8.
Если вас интересует логика вычисления количества перестановок, то рассматривайте шаблон для перестановок как имеющий местозаполнитель для всех экземпляров @src в @keyword: ww? xx? yy? zz. Каждый местозаполнитель подобен разряду в целочисленной разрядной сетке. Если разряд не установлен, то местозаполнитель заменяется на @src; если он установлен, то местозаполнитель заменяется на @synonym. При трех разрядах возможные целые числа попадают в диапазон от 0 до 7 (2^3-1). Разрядные сетки целых чисел в этом диапазоне представляют перестановки упомянутого выше шаблона, который нужно сформировать.
Следующее выражение вычисляет num_ocurrences:
(LEN (@keyword) — LEN (REPLACE (@keyword, @src, N'')))/LEN (@src)
Приведенный ниже запрос формирует целые числа; разрядная сетка этих чисел представляет перестановки, которые нужно получить:
SELECT n-1 AS permutation FROM TSQLV3.dbo.Nums WHERE n <= POWER (2, (LEN (@keyword) — LEN (REPLACE (@keyword, @src, N'')))/LEN (@src));
В таблице 1 показаны выходные данные этого запроса с разрядным представлением целых чисел.
| Таблица 1. Перестановки |
.jpg) |
Шаг 2. Вычисление позиций вставки
Назовем результат первого этапа P. На втором этапе формируется строка для каждой комбинации перестановки в P и числа n в диапазоне от 1 до num_ocurrences. Каждому экземпляру элемента @src в @keyword может предшествовать какой-нибудь элемент, отличный от @src, и за ним может следовать элемент, отличный от @src. Поэтому для каждого n в диапазоне от 1 до num_ocurrences можно считать позиции элементов @src среди элементов @src и отличных от @src равными 2×n. Например, в нашем входном @keyword имеются следующие элементы:
1 — ww 2 — AM 3 — xx 4 — AM 5 — yy 6 — AM 7 — zz
Как мы видим, три экземпляра @src находятся в позициях 2, 4 и 6. Если элемент, отличный от -@src, отсутствует в позиции до или после элемента @src, то можно рассматривать его как существующий, но представленный пустой строкой.
Как уже отмечалось, на втором этапе нашего решения формируется строка для каждой перестановки в P и экземпляра n элемента @src в @keyword. Вычисляется позиция заменяющего элемента (назовем ее pos) как 2×n. Затем, в зависимости от состояния n-го разряда в перестановке, заменяющий элемент представляет собой @src (разряд не установлен) или @synonym (разряд установлен). Второй шаг вычислений реализован в программном коде листинга 1.
Программный код в листинге 1 определяет обобщенное табличное выражение (CTE), именуемое P на основе запроса, реализующего первый шаг в решении. Внешний запрос к P использует оператор CROSS APPLY, чтобы создать элементы замены для каждой перестановки и экземпляра @src в @keyword. Оператор APPLY применяет запрос к Nums (назовем его N). Как отмечалось выше, для экземпляра N.n позиция целевого элемента (pos) — N.n×2. Чтобы выяснить, следует ли использовать @src или @sysnonym в качестве целевого элемента, необходимо проверить, установлен ли n-й разряд. Это делается с помощью следующего выражения:
permutation & POWER (2, N.n-1)
Затем выражение CASE возвращает @src или @synonym в зависимости от результата данного выражения.
Вывод программного кода в листинге 2 для наших тестовых входных значений показан в таблице 2 в сокращенном виде.
| Таблица 2. Позиции вставки |
.jpg) |
И вновь я добавляю столбец с именем binperm, который дает поразрядное представление значения перестановки.
Шаг 3. Разбиение исходных элементов
На третьем шаге формируется набор элементов, предшествующий или следующий за элементами @src в @keyword. Также вычисляются соответствующие позиции элементов с выделением места для вставляемых элементов замены. Для этого используется классическая логика разбиения строк на основе вспомогательной таблицы чисел (описание решений по разбиению строк можно найти по адресу: http://sqlmag.com/t-sql/handling-arrays-inputs и на сайте http://www.sommarskog.se/arrays-in-sql-2005.html#tblnum). В этом случае производится разбиение строки, сохраненной в @keyword, с использованием @src в качестве разделителя. Третий шаг решения реализован в следующем программном коде:
SELECT (ROW_NUMBER () OVER (ORDER BY n) — 1) * 2 + 1 AS pos, SUBSTRING (@keyword, n, CHARINDEX (@src, @keyword + @src, n) — n) AS element FROM TSQLV3.dbo.Nums WHERE n <= LEN (@keyword) + 1 AND SUBSTRING (@src + @keyword, n, LEN (@src)) = @src;
Этот код, примененный к нашим тестовым входным значениям, формирует вывод, показанный в таблице 3.
| Таблица 3. Разбиение строки |
.jpg) |
Шаг 4. Объединение исходных элементов и вставляемых элементов
На четвертом шаге выполняется простое соединение результатов шага 2 (элементов замены для вставки) с результатами шага 3 (исходные элементы). Это действие реализовано в программном коде листинга 2.
Как прежде, обобщенное табличное выражение P представляет разрядные сетки для перестановок @keyword, которые нужно сформировать. Обобщенное табличное выражение P представляет исходные разбитые элементы (запрос, реализующий шаг 3). Внешний запрос использует оператор CROSS APPLY, который применяет логику для формирования вставляемых элементов, объединенных с исходными элементами из E. Вывод программного кода, представленного в листинге 2, примененного к нашим тестовым входным значениям, показан в таблице 4.
| Таблица 4. Объединенные исходные элементы и элементы для вставки |
.jpg) |
Шаг 5. Сцепление элементов
На пятом шаге выполняется сцепление элементов каждой перестановки к строке на основе порядка pos. Я использовал классический метод FOR XML PATH для сцепления элементов. В листинге 3 представлено полное решение задачи. В таблице 5 показан вывод решения для тестовых входных значений.
| Таблица 5. Желаемый результат |
.jpg) |
Мне кажется, это очень красивая задача. Для ее решения требуются знания некоторых классических методов T-SQL, в том числе для разбиения и сцепления строк, а также новые идеи. В ней есть и числа, и логика, и манипуляции с разрядами. Я надеюсь, что в будущем нас ждет еще немало столь же интересных задач.
WITH P AS ( SELECT n-1 AS permutation FROM TSQLV3.dbo.Nums WHERE n <= POWER(2, (LEN(@keyword) - LEN(REPLACE(@keyword, @src, N''))) / LEN(@src)) ) SELECT * FROM P CROSS APPLY ( SELECT N.n, N.n * 2 AS pos, -- * 2 to account for a preceeding element CASE permutation & POWER(2, N.n - 1) WHEN 0 THEN @src ELSE @synonym END AS element FROM TSQLV3.dbo.Nums AS N WHERE N.n <= (LEN(@keyword) - LEN(REPLACE(@keyword, @src, N''))) / LEN(@src) ) AS A ORDER BY permutation, pos, element;
WITH P AS - Перестановки ( SELECT n-1 AS permutation FROM TSQLV3.dbo.Nums WHERE n < = POWER(2, (LEN(@keyword) - LEN(REPLACE(@keyword, @src, N''))) / LEN(@src)) ), E AS -- Исходные разбитые элементы без экземпляров @src ( SELECT (ROW_NUMBER() OVER(ORDER BY n) - 1) * 2 + 1 AS pos, SUBSTRING(@keyword, n, CHARINDEX(@src, @keyword + @src, n) - n) AS element FROM TSQLV3.dbo.Nums WHERE n <= LEN(@keyword) + 1 AND SUBSTRING(@src + @keyword, n, LEN(@src)) = @src ) SELECT * FROM P CROSS APPLY ( -- Вставляемые элементы SELECT N.n * 2 AS pos, CASE permutation & POWER(2, N.n - 1) WHEN 0 THEN @src ELSE @synonym END AS element FROM TSQLV3.dbo.Nums AS N WHERE N.n < = (LEN(@keyword) - LEN(REPLACE(@keyword, @src, N''))) / LEN(@src) UNION ALL -- Исходные элементы SELECT pos, element FROM E) AS A ORDER BY permutation, pos, element;
WITH P AS - Перестановки
(
SELECT n-1 AS permutation
FROM TSQLV3.dbo.Nums
WHERE n <=
POWER(2,
(LEN(@keyword)
- LEN(REPLACE(@keyword, @src, N'')))
/ LEN(@src))
),
E AS -- Исходные разбитые элементы без экземпляров @src
(
SELECT (ROW_NUMBER() OVER(ORDER BY n) - 1) * 2 + 1 AS pos,
SUBSTRING(@keyword, n,
CHARINDEX(@src, @keyword + @src, n) - n) AS element
FROM TSQLV3.dbo.Nums
WHERE n <= LEN(@keyword) + 1
AND SUBSTRING(@src + @keyword, n, LEN(@src)) = @src
)
SELECT result FROM P
CROSS APPLY
(
SELECT element AS [text()]
FROM
(
SELECT N.n * 2 AS pos,
CASE permutation & POWER(2, N.n - 1)
WHEN 0 THEN @src
ELSE @synonym
END AS element
FROM TSQLV3.dbo.Nums AS N
WHERE N.n <=
(LEN(@keyword)
- LEN(REPLACE(@keyword, @src, N'')))
/ LEN(@src)
UNION ALL
SELECT pos, element
FROM E
) AS D
ORDER BY pos
FOR XML PATH('')
) AS A(result);