Pchełki SQL: rzadkie dwójki, ciąg dalszy

https://xpil.eu/625

Ostatnio szukaliśmy w polskim słowniku rzadkich kombinacji dwuliterowych. Zastosowana metoda była prawdopodobnie jedną z możliwie najgorszych, dlatego dziś nadgryziemy zagadnienie z nieco innej strony, przy okazji odświeżając sobie składnię polecenia CROSS APPLY.

Przy kombinacjach dwuliterowych teoretycznych kombinacji było ledwie tysiąc z kawałkiem. Przy większej liczbie znaków mamy wykładniczy wzrost ilości danych do przemielenia, dlatego podejście z wygenerowaniem wszystkich możliwych kombinacji, a następnie wyszukiwanie ich w słowniku, mija się z celem.

Zamiast tego wygenerujemy sobie po prostu listę wszystkich sekwencji n-znakowych, które faktycznie istnieją w słowniku, a następnie je zdeduplikujemy i zapiszemy do osobnej tabelki, żeby się im potem bezwstydnie przyglądać.

Zaczniemy od napisania funkcji, która dla zadanego tekstu wejściowego oraz wartości n wygeneruje wszystkie unikalne n-literowe sekwencje, które w tym tekście są:

create function getNComb(@txt nvarchar(15), @n tinyint)
returns @t table(s nvarchar(15) not null)
as begin
	declare @s nvarchar(15), @i tinyint = 1, @seg nvarchar(15)
	while @i <= len(@txt) - @n + 1 begin
		SET @seg = substring(@txt, @i, @n)
		if not exists(select * from @t where s = @seg)
			insert @t select @seg
		set @i += 1
	end
	return 
end

Sprawdźmy, czy działa:

select * from getNComb('tartak', 2)

Wynik:

s
--
ta
ar
rt
ak

Jak widać ciąg 'ta' pojawił się tylko raz, chociaż w słowie 'tartak' występuje dwukrotnie.

Skoro działa, wygenerujmy teraz wszystkie segmenty dwuliterowe z całego słownika:

select s, count(*) c 
into seg2
from slowa sl
cross apply dbo.getNComb(sl.slowo, 2)
group by s

Tym razem zapytanie wymieszało się w czasie "tylko" około czterech minut, czyli kilkakrotnie szybciej, niż poprzednim razem.

Powtórzmy operację dla segmentów trzy- i czteroliterowych:

select s, count(*) c 
into seg3
from slowa sl
cross apply dbo.getNComb(sl.slowo, 3)
group by s
select s, count(*) c 
into seg4
from slowa sl
cross apply dbo.getNComb(sl.slowo, 4)
group by s

Mamy teraz kompletne zestawienia wszystkich występujących w słowniku podciągów 2-, 3- oraz 4-literowych wraz z ich popularnością w kolumnie c.

Ich analizę być może przeprowadzę w osobnym wpisie, teraz natomiast omówię operator CROSS APPLY.

Jest to tak naprawdę odpowiednik operatora INNER JOIN (lub w skrócie JOIN), tylko zamiast tabeli na drugim końcu połączenia mamy funkcję tabelaryczną (czyli taką funkcję, która zwraca rekordy)

Funkcja ta zostanie wywołana dokładnie jeden raz dla każdego rekordu z tabeli głównej. Jeżeli funkcja nie zwróci żadnego rekordu (odpowiednik sytuacji, w której JOIN nie znajduje dopasowania), operator CROSS APPLY wyeliminuje cały rekord z wyników. Jeżeli natomiast funkcja zwróci więcej niż jeden rekord, wówczas operator ten odpowiednio zwielokrotni rekord z tabeli głównej. Jedyna istotna różnica w składni między operatorami JOIN oraz CROSS APPLY jest taka, że przy JOIN musimy podać warunek dopasowania ("ON ..."), a przy CROSS APPLY - nie.

https://xpil.eu/625

3 komentarze

    1. Obawiam się, że faktycznie to zrobię; ostatnio trochę gonię w piętkę z nowymi tematami, a takie “analizy” to doskonały zapychacz 😉

  1. oj późno trafiłem na taką stronę.
    A może bardziej elegancko i wydajniej?

    create function getNComb2 (@txt nvarchar(15), @n tinyint)
    returns table
    as
       return
          (with
             qr as (select x = 1 union all select x+1 from qr where x<len(@txt)- @n + 1)
          select distinct
             s = substring(@txt, x, @n)
          from qr
       )

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.