Szybkie piętnastki

https://xpil.eu/OIdoy 📋

Dziś kolejna odsłona niekończącej się opowieści o anagramowaniu. Tym razem pokażę jak w wydajny sposób znaleźć wszystkie piętnastoliterowe słowa języka polskiego, mając danych trzynaście liter i dwa blanki.

W odróżnieniu od poprzednio prezentowanej metody, dziś ugryzę zagadnienie od dupy strony.

Przypomnę: poprzednio szukałem słów siedmioliterowych z pięciu liter i dwóch blanków, generując pięć milionów (z hakiem!) permutacji tych pięciu liter skombinowanych ze wszystkimi możliwymi pozycjami dwóch blanków, z których każdy reprezentuje jedną z 32 liter polskiego alfabetu. Końcowe zapytanie szukało dopasowań między tym pięciomilionowym zbiorem permutacji a ponaddwuipółmilionowym zbiorem polskich słówek.

Tym razem, ponieważ przy piętnastu literach (i dwóch blankach) ilość permutacji / kombinacji idzie w tryliony, powyższa metoda się nie sprawdzi i trzeba zakombinować inaczej.

Po pierwsze zauważamy, że słowa "doznawalibyście" oraz "nazdobywaliście" składają się z tych samych liter (a,a,b,c,d,e,i,i,l,n,o,ś,w,y,z). ZBIÓR liter jest więc identyczny w obydwu przypadkach, jedyna różnica polega na innym uporządkowaniu liter w wyrazie. Bazując na tym fakcie, zaczynamy od tego, że dla każdego słowa w słowniku generujemy odpowiadający mu, posortowany alfabetycznie ciąg liter, i zapisujemy go w osobnej kolumnie słownika.

Dodatkową kolumnę nazwałem [litery]. Po wypełnieniu jej wartościami należy na niej założyć indeks (z powtórzeniami, oczywiście) celem przyspieszenia późniejszych zapytań.

Do wypełnienia tej nowej kolumny wartościami użyłem poniższej funkcji:

CREATE FUNCTION [dbo].[LiterySlowa] (@Slowo varchar(100)) RETURNS varchar(100) AS
BEGIN;
 DECLARE @ResultVar varchar(100)='';
 DECLARE @t table(s varchar(100));
 DECLARE @i int=1;
 WHILE @i<=len(@Slowo) BEGIN
 INSERT @t SELECT substring(@Slowo, @i, 1)
 SELECT @i = @i + 1;
 END;

SELECT @ResultVar=@ResultVar+s from @t order by s;

RETURN @ResultVar
END

Funkcja wykonuje się około 540 mikrosekund, więc wyliczenie wszystkich posortowanych zbiorów liter dla słownika z ponad 2.7 mln rekordów zajęło około 26 minut.

Przy okazji ktoś upierdliwy mógłby zauważyć, że bezczelnie używam słowa "zbiór" w odniesieniu do grupy elementów z powtórzeniami, jak również używam pojęcia "zbiór posortowany", które jest niepoprawne z matematycznego punktu widzenia. No i fajnie.

Następnie stworzyłem sobie tabelę, w której zamierzam zapisać wszystkie kombinacje dwóch blanków w słowie piętnastoliterowym. Jest ich dokładnie 105: pierwszy blank może pojawić się na piętnastu różnych pozycjach, drugi na czternastu pozostałych, ale trzeba jeszcze wyeliminować duble, czyli: 15 * 14 / 2 = 105.

CREATE TABLE kombinacje(s char(15));

Niezbędny będzie też zestaw liter, które mamy anagramować. Na tapetę biorę słówko "doznawalibyście", zastępując Z i Ś blankami:

DECLARE @s char(13)='donawalibycie';
SELECT @s = dbo.LiterySlowa(@s);

Wypełniamy tabelę kombinacjami:

DECLARE @i1 int=1, @i2 int=2;

WHILE @i1 <= 15 BEGIN;
 WHILE @i2<=15 BEGIN
  INSERT kombinacje SELECT left(@s, @i1-1) + '_' + substring(@s, @i1, @i2-@i1-1) + '_' + right(@s, 15-@i2);
  SET @i2=@i2+1;
 END;
 SET @i1=@i1+1;
 SET @i2=@i1+1;
END;

W tym momencie tabela [kombinacje] zawiera 105 rekordów, zaczynających się od:

__aabcdeiilnowy
_a_abcdeiilnowy
_aa_bcdeiilnowy
_aab_cdeiilnowy

...

i tak dalej aż do:

...

aabcdeiilno_wy_
aabcdeiilnow_y_
aabcdeiilnowy__
aabcdeiilnowy__

W ostatnim kroku wykonujemy zapytanie na tabeli słownikowej, znajdując dopasowania na naszej dodatkowej, świeżo utworzonej kolumnie, i zwracając odpowiadające im słowa:

SELECT DISTINCT slowo
FROM words w JOIN kombinacje k ON w.litery like k.s
WHERE len(w.slowo) = 15;

W efekcie, po około 10 sekundach, dostajemy listę dziewięciu słówek:

niedyblowaniach
odnawialibyście
odwanialibyście
doznawalibyście
nazdobywaliście
anodowalibyście
niedryblasowaci
dansowalibyście
niebaldachimowy

Całość wykonuje się około 13 sekund (z czego 3 sekundy to wygenerowanie stu pięciu kombinacji blanków - głowę dam, że można szybciej, ale za leniwy jestem).

Jeżeli ktoś ma jakieś propozycje ulepszenia powyższego rozwiązania (głównie w zakresie szybkości działania), zapraszam do komentowania.

https://xpil.eu/OIdoy 📋