T-SQL - подсчет уникальных символов в переменной - PullRequest
0 голосов
/ 07 ноября 2019

Цель: подсчитать количество различных символов в переменной максимально быстрым способом.

DECLARE @String1 NVARCHAR(4000) = N'1A^' ; --> output = 3
DECLARE @String2 NVARCHAR(4000) = N'11' ; --> output = 1
DECLARE @String3 NVARCHAR(4000) = N'*' ; --> output = 1
DECLARE @String4 NVARCHAR(4000) = N'*A-zz' ; --> output = 4

Я нашел несколько сообщений относительно отдельных символов в столбце, сгруппированных по символам и т. Д.,но не один для этого сценария.

Ответы [ 5 ]

5 голосов
/ 07 ноября 2019

Используя NGrams8K в качестве базы, вы можете изменить входной параметр на nvarchar(4000) и настроить DATALENGTH, получив NGramsN4K. Затем вы можете использовать это, чтобы разбить строку на отдельные символы и сосчитать их:

SELECT COUNT(DISTINCT NG.token) AS DistinctCharacters
FROM dbo.NGramsN4k(@String1,1) NG;

Изменено NGrams8K:

IF OBJECT_ID('dbo.NGramsN4k','IF') IS NOT NULL DROP FUNCTION dbo.NGramsN4k;
GO
CREATE FUNCTION dbo.NGramsN4k
(
  @string nvarchar(4000), -- Input string 
  @N      int            -- requested token size
)
/****************************************************************************************
Purpose:
 A character-level N-Grams function that outputs a contiguous stream of @N-sized tokens 
 based on an input string (@string). Accepts strings up to 8000 varchar characters long.
 For more information about N-Grams see: http://en.wikipedia.org/wiki/N-gram. 

Compatibility: 
 SQL Server 2008+, Azure SQL Database

Syntax:
--===== Autonomous
 SELECT position, token FROM dbo.NGrams8k(@string,@N);

--===== Against a table using APPLY
 SELECT s.SomeID, ng.position, ng.token
 FROM dbo.SomeTable s
 CROSS APPLY dbo.NGrams8K(s.SomeValue,@N) ng;

Parameters:
 @string  = The input string to split into tokens.
 @N       = The size of each token returned.

Returns:
 Position = bigint; the position of the token in the input string
 token    = varchar(8000); a @N-sized character-level N-Gram token

Developer Notes:  
 1. NGrams8k is not case sensitive

 2. Many functions that use NGrams8k will see a huge performance gain when the optimizer
    creates a parallel execution plan. One way to get a parallel query plan (if the 
    optimizer does not chose one) is to use make_parallel by Adam Machanic which can be 
    found here:
 sqlblog.com/blogs/adam_machanic/archive/2013/07/11/next-level-parallel-plan-porcing.aspx

 3. When @N is less than 1 or greater than the datalength of the input string then no 
    tokens (rows) are returned. If either @string or @N are NULL no rows are returned.
    This is a debatable topic but the thinking behind this decision is that: because you
    can't split 'xxx' into 4-grams, you can't split a NULL value into unigrams and you 
    can't turn anything into NULL-grams, no rows should be returned.

    For people who would prefer that a NULL input forces the function to return a single
    NULL output you could add this code to the end of the function:

    UNION ALL 
    SELECT 1, NULL
    WHERE NOT(@N > 0 AND @N <= DATALENGTH(@string)) OR (@N IS NULL OR @string IS NULL)

 4. NGrams8k can also be used as a tally table with the position column being your "N" 
    row. To do so use REPLICATE to create an imaginary string, then use NGrams8k to split
    it into unigrams then only return the position column. NGrams8k will get you up to 
    8000 numbers. There will be no performance penalty for sorting by position in 
    ascending order but there is for sorting in descending order. To get the numbers in
    descending order without forcing a sort in the query plan use the following formula:
    N = <highest number>-position+1. 

 Pseudo Tally Table Examples:
    --===== (1) Get the numbers 1 to 100 in ascending order:
    SELECT N = position 
    FROM dbo.NGrams8k(REPLICATE(0,100),1);

    --===== (2) Get the numbers 1 to 100 in descending order:
    DECLARE @maxN int = 100;
    SELECT N = @maxN-position+1
    FROM dbo.NGrams8k(REPLICATE(0,@maxN),1)
    ORDER BY position;

 5. NGrams8k is deterministic. For more about deterministic functions see:
    https://msdn.microsoft.com/en-us/library/ms178091.aspx

Usage Examples:
--===== Turn the string, 'abcd' into unigrams, bigrams and trigrams
 SELECT position, token FROM dbo.NGrams8k('abcd',1); -- unigrams (@N=1)
 SELECT position, token FROM dbo.NGrams8k('abcd',2); -- bigrams  (@N=2)
 SELECT position, token FROM dbo.NGrams8k('abcd',3); -- trigrams (@N=3)

--===== How many times the substring "AB" appears in each record
 DECLARE @table TABLE(stringID int identity primary key, string varchar(100));
 INSERT @table(string) VALUES ('AB123AB'),('123ABABAB'),('!AB!AB!'),('AB-AB-AB-AB-AB');

 SELECT string, occurances = COUNT(*) 
 FROM @table t
 CROSS APPLY dbo.NGrams8k(t.string,2) ng
 WHERE ng.token = 'AB'
 GROUP BY string;

----------------------------------------------------------------------------------------
Revision History:
 Rev 00 - 20140310 - Initial Development - Alan Burstein
 Rev 01 - 20150522 - Removed DQS N-Grams functionality, improved iTally logic. Also Added
                     conversion to bigint in the TOP logic to remove implicit conversion
                     to bigint - Alan Burstein
 Rev 03 - 20150909 - Added logic to only return values if @N is greater than 0 and less 
                     than the length of @string. Updated comment section. - Alan Burstein
 Rev 04 - 20151029 - Added ISNULL logic to the TOP clause for the @string and @N 
                     parameters to prevent a NULL string or NULL @N from causing "an 
                     improper value" being passed to the TOP clause. - Alan Burstein
****************************************************************************************/
RETURNS TABLE WITH SCHEMABINDING AS RETURN
WITH 
L1(N) AS 
(
  SELECT 1
  FROM (VALUES    -- 90 NULL values used to create the CTE Tally table
        (NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
        (NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
        (NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
        (NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
        (NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
        (NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
        (NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
        (NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),
        (NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL),(NULL)
       ) t(N)
),
iTally(N) AS                                   -- my cte Tally table
(
  SELECT TOP(ABS(CONVERT(BIGINT,((DATALENGTH(ISNULL(@string,N''))/2)-(ISNULL(@N,1)-1)),0)))
    ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) -- Order by a constant to avoid a sort
  FROM L1 a CROSS JOIN L1 b                    -- cartesian product for 8100 rows (90^2)
)
SELECT
  position = N,                                -- position of the token in the string(s)
  token    = SUBSTRING(@string,CAST(N AS int),@N)  -- the @N-Sized token
FROM iTally
WHERE @N > 0 AND @N <= (DATALENGTH(@string)/2);    -- Protection against bad parameter values 
2 голосов
/ 07 ноября 2019

Вот еще одна альтернатива, использующая силу таблицы подсчета. Он был назван «Швейцарский армейский нож T-SQL». Я держу таблицу подсчета в качестве представления моей системы, что делает его безумно быстрым.

create View [dbo].[cteTally] as

WITH
    E1(N) AS (select 1 from (values (1),(1),(1),(1),(1),(1),(1),(1),(1),(1))dt(n)),
    E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows
    E4(N) AS (SELECT 1 FROM E2 a, E2 b), --10E+4 or 10,000 rows max
    cteTally(N) AS 
    (
        SELECT  ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E4
    )
select N from cteTally

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

declare @Something table
(
    String1 nvarchar(4000)
)

insert @Something values
(N'1A^')
, (N'11')
, (N'*')
, (N'*A-zz')

select count(distinct substring(s.String1, t.N, 1))
    , s.String1
from @Something s
join cteTally t on t.N <= len(s.String1)
group by s.String1

Если честно, я не знаю, будет ли это быстрее, чем использование NGrams Ларну, но тестирование на большом столе было бы интересно посмотреть.


---- РЕДАКТИРОВАТЬ -----

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

select count(distinct substring(s.String1, A.N, 1))
    , s.String1
from @Something s
CROSS APPLY (SELECT TOP(LEN(s.String1)) t.N FROM cteTally t) A(N)
group by s.String1

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

Если вы хотите узнать больше о треугольных соединениях и почему мы должны их избегать, у Джеффа Модена есть отличная статья на эту тему. https://www.sqlservercentral.com/articles/hidden-rbar-triangular-joins

2 голосов
/ 07 ноября 2019

Возьмите копию NGrams8k , и вы можете сделать это:

DECLARE @String1 NVARCHAR(4000) = N'1A^' ; --> output = 3
DECLARE @String2 NVARCHAR(4000) = N'11' ; --> output = 1
DECLARE @String3 NVARCHAR(4000) = N'*' ; --> output = 1
DECLARE @String4 NVARCHAR(4000) = N'*A-zz' ; --> output = 4

SELECT     s.String, Total = COUNT(DISTINCT ng.token)
FROM       (VALUES(@String1),(@String2),(@String3),(@String4)) AS s(String)
CROSS APPLY dbo.NGrams8k(s.String,1)                           AS ng
GROUP BY    s.String;

Возвраты:

String   Total
-------- -----------
*        1
*A-zz    4
11       1
1A^      3

ОБНОВЛЕНО Просто быстрое обновление на основе сообщений и комментариев @ Larnu. Я не заметил, что ОП имел дело с Unicode, например, NVARCHAR. Я создал версию NVARCHAR (4000) здесь - аналогично тому, что @Larnu опубликовал выше. Я только что обновил токен возврата, чтобы использовать сопоставление Latin1_General_BIN.

SUBSTRING(@string COLLATE Latin1_General_BIN,CAST(N AS int),@N)

Это возвращает правильный ответ:

DECLARE @String5 NVARCHAR(4000) = N'ᡣᓡ'; --> output = 2

SELECT   COUNT(DISTINCT ng.token)
FROM     dbo.NGramsN4k(@String5,1) AS ng;

Без сопоставления вы можете использовать то, что опубликовал Ларну, и получитьправильный ответ так:

DECLARE @String5 NVARCHAR(4000) = N'ᡣᓡ'; --> output = 2

SELECT    COUNT(DISTINCT UNICODE(ng.token))
FROM     dbo.NGramsN4k(@String5,1) AS ng;

Вот моя обновленная функция NGramsN4K:

ALTER FUNCTION dbo.NGramsN4K
(
  @string nvarchar(4000), -- Input string
  @N      int             -- requested token size
)
/****************************************************************************************
Purpose:
 A character-level N-Grams function that outputs a contiguous stream of @N-sized tokens 
 based on an input string (@string). Accepts strings up to 4000 nvarchar characters long.
 For more information about N-Grams see: http://en.wikipedia.org/wiki/N-gram. 

Compatibility: 
 SQL Server 2008+, Azure SQL Database

Syntax:
--===== Autonomous
 SELECT position, token FROM dbo.NGramsN4K(@string,@N);

--===== Against a table using APPLY
 SELECT s.SomeID, ng.position, ng.token
 FROM dbo.SomeTable s
 CROSS APPLY dbo.NGramsN4K(s.SomeValue,@N) ng;

Parameters:
 @string  = The input string to split into tokens.
 @N       = The size of each token returned.

Returns:
 Position = bigint; the position of the token in the input string
 token    = nvarchar(4000); a @N-sized character-level N-Gram token

Developer Notes:  
 1. NGramsN4K is not case sensitive

 2. Many functions that use NGramsN4K will see a huge performance gain when the optimizer
    creates a parallel execution plan. One way to get a parallel query plan (if the 
    optimizer does not chose one) is to use make_parallel by Adam Machanic which can be 
    found here:
 sqlblog.com/blogs/adam_machanic/archive/2013/07/11/next-level-parallel-plan-porcing.aspx

 3. When @N is less than 1 or greater than the datalength of the input string then no 
    tokens (rows) are returned. If either @string or @N are NULL no rows are returned.
    This is a debatable topic but the thinking behind this decision is that: because you
    can't split 'xxx' into 4-grams, you can't split a NULL value into unigrams and you 
    can't turn anything into NULL-grams, no rows should be returned.

    For people who would prefer that a NULL input forces the function to return a single
    NULL output you could add this code to the end of the function:

    UNION ALL 
    SELECT 1, NULL
    WHERE NOT(@N > 0 AND @N <= DATALENGTH(@string)) OR (@N IS NULL OR @string IS NULL);

 4. NGramsN4K is deterministic. For more about deterministic functions see:
    https://msdn.microsoft.com/en-us/library/ms178091.aspx

Usage Examples:
--===== Turn the string, 'abcd' into unigrams, bigrams and trigrams
 SELECT position, token FROM dbo.NGramsN4K('abcd',1); -- unigrams (@N=1)
 SELECT position, token FROM dbo.NGramsN4K('abcd',2); -- bigrams  (@N=2)
 SELECT position, token FROM dbo.NGramsN4K('abcd',3); -- trigrams (@N=3)

--===== How many times the substring "AB" appears in each record
 DECLARE @table TABLE(stringID int identity primary key, string nvarchar(100));
 INSERT @table(string) VALUES ('AB123AB'),('123ABABAB'),('!AB!AB!'),('AB-AB-AB-AB-AB');

 SELECT string, occurances = COUNT(*) 
 FROM @table t
 CROSS APPLY dbo.NGramsN4K(t.string,2) ng
 WHERE ng.token = 'AB'
 GROUP BY string;

------------------------------------------------------------------------------------------
Revision History:
 Rev 00 - 20170324 - Initial Development - Alan Burstein
 Rev 01 - 20191108 - Added Latin1_General_BIN collation to token output - Alan Burstein
*****************************************************************************************/
RETURNS TABLE WITH SCHEMABINDING AS RETURN
WITH
L1(N) AS
(
  SELECT 1 FROM (VALUES -- 64 dummy values to CROSS join for 4096 rows
        ($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),
        ($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),
        ($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),
        ($),($),($),($),($),($),($),($),($),($),($),($),($),($),($),($)) t(N)
),
iTally(N) AS 
(
  SELECT 
  TOP (ABS(CONVERT(BIGINT,((DATALENGTH(ISNULL(@string,''))/2)-(ISNULL(@N,1)-1)),0)))
    ROW_NUMBER() OVER (ORDER BY (SELECT NULL))    -- Order by a constant to avoid a sort
  FROM L1 a CROSS JOIN L1 b                       -- cartesian product for 4096 rows (16^2)
)
SELECT
  position = N,                                   -- position of the token in the string(s)
  token    = SUBSTRING(@string COLLATE Latin1_General_BIN,CAST(N AS int),@N) -- the @N-Sized token
FROM iTally
WHERE @N > 0  -- Protection against bad parameter values:
AND   @N <= (ABS(CONVERT(BIGINT,((DATALENGTH(ISNULL(@string,''))/2)-(ISNULL(@N,1)-1)),0)));
1 голос
/ 07 ноября 2019
CREATE TABLE #STRINGS(
    STRING1 NVARCHAR(4000)
)

INSERT INTO #STRINGS (
    STRING1
)
VALUES
(N'1A^'),(N'11'),(N'*'),(N'*A-zz')


;WITH CTE_T AS (
    SELECT DISTINCT
        S.STRING1
        ,SUBSTRING(S.STRING1, V.number + 1, 1) AS Val
    FROM
        #STRINGS S
    INNER JOIN
        [master]..spt_values V
        ON V.number < LEN(S.STRING1)
    WHERE
        V.[type] = 'P'
)
SELECT
    T.STRING1
    ,COUNT(1) AS CNT
FROM
    CTE_T T
GROUP BY
    T.STRING1
1 голос
/ 07 ноября 2019

Вы можете сделать это изначально в SQL Server, используя CTE и некоторые манипуляции со строками:

DECLARE @TestString NVARCHAR(4000);
SET @TestString = N'*A-zz';

WITH letters AS
(
    SELECT  1 AS Pos,
            @TestString AS Stri,
            MAX(LEN(@TestString)) AS MaxPos,
            SUBSTRING(@TestString, 1, 1) AS [Char]
    UNION ALL
    SELECT  Pos + 1,
            @TestString,
            MaxPos,
            SUBSTRING(@TestString, Pos + 1, 1) AS [Char]
      FROM  letters
      WHERE Pos + 1 <= MaxPos
)
SELECT  COUNT(*) AS LetterCount
  FROM  (
        SELECT  UPPER([Char]) AS [Char]
          FROM  letters
          GROUP BY [Char]
        ) a

Пример выходных данных:

SET @TestString = N'*A-zz';
{execute code}
LetterCount = 4

SET @TestString = N'1A^';
{execute code}
LetterCount = 3

SET @TestString = N'1';
{execute code}
LetterCount = 1

SET @TestString = N'*';
{execute code}
LetterCount = 1
...