Szybkie piętnastki

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.

Dodaj komentarz

4 komentarzy do "Szybkie piętnastki"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
butter
Gość

;D. Czyli tak, jak proponowałem – join na lajku. HA

xpil
Gość

dżojn a nie join, nie kalecz mi tu angielszczyzny :]

Maciek
Gość

Co do "zbioru", to lista bylaby tutaj bardziej poprawnym okresleniem. 😉

Ponadto kopsnales sie przy kombinacjach: powinno byc "__aabcdeiilnowy" (15 znakow) zamiast "__aabcdeiilnośwyz" (17 znakow).

Generalnie nie sadzilem, ze sqla mozna wykorzystac do takich celow, gratuluje pomyslowosci. Mimo wszystko wydajnosc pozostawia wiele do zyczenia, a sam jezyk wydaje sie byc zbyt ograniczonym do takiego zadania. Az z ciekawosci sprawdzilem jakby to wygladalo w moim ulubionym jezyku i o dziwo to samo wyszukanie zajmuje mniej niz sekunde, bez tworzenia zadnych tabel, a dopasowania znajdowane sa w trakcie odczytywaniu pliku.

xpil
Gość

Słuszna uwaga – poprawione (wywaliłem Z i Ś).

Co do SQL – to jest w końcu język deklaracyjny. Mówisz mu CO ma zrobić, natomiast niewielki masz wpływ na to JAK to będzie zrobione. Jakby się uprzeć, można by przy użyciu CLR dopisać rozszerzenie do anagramowania, w jakimś C# czy innym VB.NET – może kiedyś mi się zachce.

wpDiscuz