Pchełki SQL, odcinek 12: Chłopstwo górą

https://xpil.eu/px4oZ 📋

Jakiś czas temu pokazywałem w jednej z Pchełek jak za pomocą SQL wyszukiwać piętnastoliterowe słowa języka polskiego, mając dane trzynaście liter i dwa blanki. Pokazywałem też podobny przykład dla słów siedmioliterowych (a więc: pięć liter i dwa blanki).

Dziś zamiast anagramowania pobawimy się w szukanie słów, które składają się z liter występujących w kolejności alfabetycznej.

Przykład takiego słowa: dno. D w alfabecie występuje przed N, a N przed O.
Inny przykład: koty. K jest w alfabecie przed O, O przed T, a T przed Y.

Pytanie: jakie są najdłuższe słowa spełniające ten warunek?
Pytanie pomocnicze: a co, jeżeli potraktujemy zagadnienie od tylca? Czyli poszukamy słów, w których wszystkie litery pojawiają się w odwrotnej kolejności alfabetycznej?

Zaczniemy, tradycyjnie, od pobrania listy słówek ze strony sjp.pl oraz zainstalowania testowej wersji SQL Servera i zaimportowaniu 2.7 mln słówek do tabeli o nazwie SLOWA. Pamiętajmy, żeby przy imporcie użyć kodowania win-1250. Pisałem o tym już wcześniej, więc bez wdawania się w szczegóły przechodzę do kolejnego kroku.

Napiszę sobie teraz funkcję, która dla zadanego ciągu tekstowego zwróci mi binarną informację: TAK lub NIE (TAK jeżeli litery w tekście wejściowym występują w kolejności alfabetycznej, NIE jeżeli tak nie jest).

Funkcja wygląda o, tak:

CREATE FUNCTION [dbo].[literki_po_kolei] (@s nvarchar(15))
RETURNS bit
AS
BEGIN
  declare @i int
  set @i=1
  while @i<=len(@s)-1
  begin
    if SUBSTRING(@s, @i, 1) >= substring(@s, @i+1, 1)
      return 0
    set @i=@i+1
  end
  return 1
END

Funkcja nazywa się literki_po_kolei i przyjmuje jeden parametr na wejściu - a zwraca jedynkę ("TAK") lub zero ("NIE").

Ponieważ będę również chciał odpowiedzieć na pytanie pomocnicze (odtylcowe), napiszę sobie zaraz drugą, bliźniaczą funkcję, która robi dokładnie to samo, tylko od tyłu:

CREATE FUNCTION [dbo].[literki_odwrotnie] (@s nvarchar(15))
RETURNS bit
AS
BEGIN
  declare @i int
  set @i=1
  while @i<=len(@s)-1
  begin
    if SUBSTRING(@s, @i, 1) <= substring(@s, @i+1, 1)
      return 0
    set @i=@i+1
  end
  return 1
END

Funkcja nazywa się literki_odwrotnie i różni się od poprzedniej tylko jednym znakiem. Stąd od razu nasuwa się pomysł, żeby te dwie funkcje scalić do jednej, a kierunek literek przekazywać w drugim parametrze, ale to może innym razem. Zostawiamy jak jest.

W następnej kolejności zapuszczamy zapytanie do bazy słówek:

select slowo, len(slowo) dlugosc
from slowa
where dbo.literki_po_kolei(slowo)=1
order by len(slowo) desc;

Wybieramy wszystkie słowa, dla których funkcja sprawdzająca kolejność liter zwraca jedynkę. Spośród ponad 2.7 milionów słów, tylko 724 spełniają ten warunek. Dwadzieścia słówek z samej góry listy:

chłopstw    8
chłosty    7
chinowy    7
dekortu    7
dekorty    7
filmowy    7
filmów    6
dekoru    6
dekory    6
dekowy    6
dekort    6
dosuwy    6
gilosz    6
gilowy    6
hikory    6
horstu    6
horsty    6
klopsu    6
klopsy    6
knopry    6

Jak widać tylko jedno słowo spełniające warunki zadania ma osiem liter: "chłopstw". To przy okazji tłumaczy tajemniczy dotąd tytuł dzisiejszego wpisu. Jak to zwykle bywa ze słówkami, wśród pozostalych jest mnóstwo takich, których znaczenia trzeba poszukać na sjp.pl. Ja na przykład nie mam pojęcia czym jest horst, knopr czy dekort.

A teraz poszukamy słów, które mają litery w porządku alfabetycznym malejącym. Kod identyczny jak powyżej, tylko użyjemy drugiej funkcji:

select slowo, len(slowo) dlugosc
from slowa
where dbo.literki_odwrotnie(slowo)=1
order by len(slowo) desc;

Trochę wyników:

utonięć    7
wroniec    7
żyronda    7
żyrondą    7
żywnica    7
żywnicą    7
żywnie    6
żywnic    6
żywica    6
żywicą    6
żywiec    6
żytnia    6
żytnią    6
żytnie    6
żyrond    6
wronię    6
wrońca    6
wonieć    6
wronia    6
wronią    6

Jak widać jest tu tylko sześć słówek siedmioliterowych (i żadne nie dorównuje długością "chłopstw" z poprzedniego przykładu, ha!), niektóre nawet znajome, inne całkiem dziwne. Taka żyronda na przykład brzmi jak krzyżówka genetyczna żyrafy z żyrandolem, albo może jak żyrafa, która utkwiła na rondzie...

Na koniec komentarz o wydajności takiej implementacji: ponieważ wykonujemy tutaj funkcję użytkownika na każdym z ponad 2.7 mln rekordów, nie używamy żadnych indeksów, a więc powinno to działać bardzo wolno. U mnie zapytanie wykonuje się w okolicach 6-7 sekund. Mogę sobie wyobrazić bardziej wysublimowane zapytanie, ale tu już wykraczamy poza ramy pojęcia "Pchełka". Zresztą, i tak się rozpisałem. Wracam na zmywak...

https://xpil.eu/px4oZ 📋