Pchełki SQL, odcinek 3: literki

In Pchełki SQL by xpil0 Comments

Zajrzałem z ciekawości w historyczne wpisy na tym blogu i ze zgrozą stwierdziłem, że ostatnią pchełkę napisałem ponad trzy miesiące temu. Szmat czasu. Dziś więc czas na kolejną – pobawimy się w zliczanie liter w tekście.

Po co to komu?

Pytanie „Po co?” jest tu tak samo niewłaściwe jak pytanie „Po co ludzie włażą na szczyty górskie?”. Odpowiedź jest zawsze ta sama: bo się da.

Zadanie jakie sobie dziś stawiam to napisanie zapytania SQL, które mi wyszuka w słowniku języka polskiego wyrazy z największą ilością powtórzeń tej samej litery.

Ale o ssso chchchozzzi?

Proste: w słowie „kałamarz” litera „a” występuje trzykrotnie.

W słowie „sześciopokoleniowy” litera „o” występuje czterokrotnie.

A jaka jest maksymalna krotność dowolnej litery? Może sześć? a może dziewięć? A może tylko pięć?

Sprawdźmy.

Zaczniemy od zainstalowania SQL Servera oraz utworzenia bazy danych z polskimi słówkami. Szczegółowy opis krok po kroku jak to zrobić znajduje się tutaj.

Następnie piszemy takie oto zapytanie SQL:

with q as

(select convert(char(1), ‚a’) as litera

union all select

convert(char(1), char(ascii(litera)+1))

from q

where ascii(litera)<ascii(‚z’))

, litery as (

select litera from q

union all select ‚ż’

union all select ‚ź’

union all select ‚ć’

union all select ‚ń’

union all select ‚ą’

union all select ‚ś’

union all select ‚ł’

union all select ‚ę’

union all select ‚ó’

)

select top 1000

litera

, slowo

, len(slowo) len(replace(slowo, litera, )) as licznik

from

litery

, words

order by 3 desc

 

Tradycyjnie, kilka słów objaśnienia:

Na samym początku tworzymy listę wszystkich liter, od a do z. Można było to zrobić dużo prościej (identycznie jak polskie litery z ogonkami w dalszej części zapytania), czyli 35 linijek SELECT … UNION SELECT … – ale przy okazji mamy możliwość pobieżnego omówienia rekursywnych CTE, dlatego trochę to zapytanie skomplikowałem.

W pierwszej linijce tworzymy CTE o nazwie q, następnie – w linii drugiej – wypluwamy pierwszą literę (niespodzianka! jest nią litera „a”), a w kolejnych czterech linijkach generujemy pozostałe litery (czyli b-z). Używamy w tym celu rekursywnego CTE, czyli takiego podzapytania, które wybiera dane do dalszego przetwarzania ze swoich własnych wyników. Jak widać w piątej linii jest FROM q – tu właśnie pojawia się rekurencja. Żeby zapobiec nieskończonej pętli (która i tak nie byłaby możliwa – SQL Server zapobiega nieskończonym rekursywnym CTE, ustawiając domyślnie maksymalny poziom zagnieżdżenia na 32 oraz nie pozwalając na podanie większego poziomu zagnieżdżenia niż 1000), w szóstej linii ograniczamy rekordy wyjściowe do tych, których kod ASCII nie przekracza kodu ASCII litery „z”. Dzięki temu mamy wygenerowanych 26 liter alfabetu łacińskiego.

W kolejnym CTE, nazwanym „litery”, nie ma już rekurencji – dodajemy tutaj po prostu dziewięć polskich liter (żźćńąśłęó), w efekcie otrzymując pełny alfabet (w tym również litery x, q i v, których w polskim słowniku nie ma – ale nie szkodzi).

Wreszcie końcowe zapytanie wybiera tysiąc słówek z największą ilością powtórzeń dowolnej litery alfabetu. Uzyskujemy to tworząc iloczyn kartezjański rekordów z cte „litery” z rekordami ze słownika, następnie dla każdej kombinacji słowo-litera wyliczając różnicę długości tego słowa oraz długości tego samego słowa, z którego usunięto tę literę. Weźmy słowo „abrakadabra” – jeżeli bieżąca litera to „a”, funkcja replace(…) zwróci „brkdbr”, skoro więc długość oryginalnego słowa to 11 liter, a długość „brkdbr” to sześć znaków, oznacza to, że w słowie „abrakadabra” jest 11 – 6 = 5 powtórzeń litery „a”. I tak dalej.

Na samym końcu wybieramy tylko tysiąc pierwszych rekordów, posortowanych malejąco według trzeciej kolumny (a więc, według ilości powtórzeń danej litery w słowie).

Przyjrzyjmy się teraz efektywności tego zapytania: nieco ponad dwa i pół miliona słówek oraz 35 liter dają łącznie prawie sto milionów kombinacji (przypominam, iloczyn kartezjański oznacza „każdy z każdym”). Ponieważ trzeba te sto milionów rekordów posortować (w rzeczywistości jest ich około 97 milionów) w celu wybrania pierwszego tysiąca, zadanie jest dość żmudne obliczeniowo. Na moim starym (ponad czteroletnim) pececie liczyło się to trochę powyżej trzech minut i podniosło zużycie pamięci serwera do około 470 megabajtów. Chętnie posłucham pomysłów Czytelników na zoptymalizowanie tego zapytania (poza trywialnym „wywalić rzadkie literki”).

Jeżeli ktoś jest ciekaw efektów, oto one:

Na pierwszym miejscu, z wynikiem SIEDEM, mamy tylko jedno słówko. Jest nim „okołoporodowego”. Siedem razy literka „o”.

Następnie mamy 72 słówka z wynikiem SZEŚĆ, są to: borowodorowałom, borowodorowałoś, borowodorowało, borowodorowano, azotowodorowego, fosforowodorowa, okołoporodowa, antropozoonozom, antropozoonozo, okołoporodowej, okołoporodowe, okołoporodowemu, fosforowodorowi, fosforowodorom, fosforowodorowy, okołoporodowymi, okołoporodowi, okołoporodowym, okołoporodowy, ortofosforowego, ośmiopokojowego, protozoologowie, kolonoskopowego, zoosocjologowie, zoosocjologowi, zoosocjologio, zoosocjologiom, zoosocjologom, jodowodorowego, odpodmiotowiono, fosforowodorowe, fosforowodorową, okołoporodową, drobnoowocowego, osobowościowego, osobowościowo, bromowodorowego, ośmioosobowego, wolnoobrotowego, podoczodołowego, okołoporodowych, protozoologiom, protozoologowi, protozoologio, protozoologom, motorowozownio, motorowozowniom, zbezczeszczasz, zabałaganiająca, zabałaganiałaby, zabałaganiania, zabałaganiałam, zabałaganiałaś, zabałaganiała, zabałaganiana, zaambarasowania, zaambarasowałam, zaambarasowałaś, zaambarasowała, zaambarasowana, taramasalatach, taramasalatami, taramasalata, nieceregielenie, niekisielickimi, nieimielińskimi, niefilipińskimi, wysypywałybyśmy, wypytywałybyśmy, wybyczyłybyśmy, wytyczyłybyśmy, wywyższyłybyśmy.

Proszę zwrócić uwagę, że wśród wyrazów z wynikiem SZEŚĆ jest tylko jeden wyraz, w którym tych sześć powtórzeń dotyczy spółgłoski – i jest to o dziwo litera „z”, wcale nie najpopularniejsza w polskim słowniku.

Dalej idą piątki, których listowania jednak oszczędzę znudzonemu Czytelnikowi.

I to by było na tyle.

Dodaj komentarz

Bądź pierwszy!

Powiadom o
avatar
wpDiscuz