Реклама

Посвящается памяти моего недавно ушедшего из жизни отца, Габриеля Бен-Гана. Он любил числа, логику и головоломки и обыкновенно находил свое­образные решения задач. В этой статье я предлагаю вашему вниманию одну очень интересную задачу и прежде всего хочу выразить благодарность Дэвиду Шипли, приславшему мне ее. Задача довольно проста, но для поиска решения необходим творческий подход.

В решении используется вспомогательная таблица с именем dbo.Nums, содержащая последовательность целых чисел, начиная с 1, в столбце с именем n. Вспомогательную таблицу можно найти в тестовой базе данных TSQLV3. Исходный текст для создания тестовой базы данных можно загрузить по адресу: tsql.solidq.com/books/source_code/TSQLV3.zip.

Задача

Задача заключается в копировании с опечатками ключевых слов, вводимых для поиска. Ввод состоит из трех строк:

  1. Ключевое слово, введенное пользователем для поиска (@keyword).
  2. Исходное слово (@src).
  3. Синоним исходного слова (@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. Перестановки
Перестановки

 

Шаг 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. Позиции вставки
Позиции вставки

 

И вновь я добавляю столбец с именем 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. Разбиение строки
Разбиение строки

 

Шаг 4. Объединение исходных элементов и вставляемых элементов

На четвертом шаге выполняется простое соединение результатов шага 2 (элементов замены для вставки) с результатами шага 3 (исходные элементы). Это действие реализовано в программном коде листинга 2.

Как прежде, обобщенное табличное выражение P представляет разрядные сетки для перестановок @keyword, которые нужно сформировать. Обобщенное табличное выражение P представляет исходные разбитые элементы (запрос, реализующий шаг 3). Внешний запрос использует оператор CROSS APPLY, который применяет логику для формирования вставляемых элементов, объединенных с исходными элементами из E. Вывод программного кода, представленного в листинге 2, примененного к нашим тестовым входным значениям, показан в таблице 4.

 

Таблица 4. Объединенные исходные элементы и элементы для вставки
Объединенные исходные элементы и элементы для вставки

 

Шаг 5. Сцепление элементов

На пятом шаге выполняется сцепление элементов каждой перестановки к строке на основе порядка pos. Я использовал классический метод FOR XML PATH для сцепления элементов. В листинге 3 представлено полное решение задачи. В таблице 5 показан вывод решения для тестовых входных значений.

 

Таблица 5. Желаемый результат
Желаемый результат

 

Мне кажется, это очень красивая задача. Для ее решения требуются знания некоторых классических методов T-SQL, в том числе для разбиения и сцепления строк, а также новые идеи. В ней есть и числа, и логика, и манипуляции с разрядами. Я надеюсь, что в будущем нас ждет еще немало столь же интересных задач.

Листинг 1. Шаг 2 — вычисление позиций вставки
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;
Листинг 2. Шаг 4 — объединение шагов 2 и 3
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;
Листинг 3. Полное решение
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);
Купить номер с этой статьей в PDF