Sprawdzanie permutacji ciągu znaków w PostgreSQL

Permutacja w języku matematycznym to „wzajemnie jednoznaczne przekształcenie pewnego zbioru na siebie”. Używając języka mniej technicznego permutacje, na przykładzie liter w słowie, to wszystkie możliwe ustawienia literek w słowie, zatem dla słowa „marcin” permutacjami będą: „amrcin”, „mracin”, „mrcain” etc… w słowie 6 znakowym będzie ich łącznie 6!.

Problem

W bazie danych mamy pole tekstowe z zapisanymi pewnymi ciągami znaków, chcemy sprawdzić te dane pod kątem występowania w nich permutacji pewnego stringu. Czyli mając w danych wejściowych np. „mrcain” chcemy sprawdzić czy w bazie nie ma „marcin” lub innej permutacji.

Rozwiązanie

Normalizujemy tekst, normalizacja w naszym przypadku polegać będzie na posortowaniu liter w stringu w kolejności alfabetycznej, czyli „mrcain” przekształcimy do „acimnr”. Dzięki znormalizowaniu każda permutacja zostanie przekształcona do identycznej postaci, znormalizowane teksty będzie można porównać zwykłym operatorem = co jest bardzo szybkie.

Aby to zrealizować wykorzystujemy funkcję generate_series dzięki które możemy iterować po zbiorze liczb (w przykładzie od 0 do 40, 40 to maksymalna możliwa długość sprawdzanego stringu) – funkcję ta działa w tym wypadku podobnie jak zwykła pętla for, następnie w klauzuli SELECT korzystamy ze zmiennej i i wycinamy z wejściowego stringu literki znak po znaku, na koniec w klauzuli WHERE mamy ograniczenie sprawdzające czy aby jest jeszcze co wycinać.

Wynikiem działania tego zapytania będzie zestaw wierszy, w którym każdy wiersz będzie zawierał jeden znak ze stringu.

SELECT 
	substr(cast(slowo as text), i+1, 1) AS c  
FROM 
	generate_series(0,40) AS s(i), (SELECT 'mrcain' AS slowo) as sub
WHERE
	i < length(cast(slowo as text))

Tak przygotowane dane możemy posortować alfabetycznie w podzapytaniu, a następnie posortowane już znaki scalić w string funkcją string_agg. Jeżeli postgres jest poprawnie skonfigurowany to zapytanie to radzi sobie z polskimi znakami, polski znak powinien znaleźć się zaraz za jego odpowiednikiem z alfabetu czyli aą cć eę.

SELECT string_agg(c, '') from (
	SELECT c FROM
	 (
		SELECT 
			substr(cast(slowo as text), i+1, 1) AS c  
		FROM 
			generate_series(0,40) AS s(i), (SELECT 'mrcain' AS slowo) as sub
		WHERE
			i < length(cast(slowo as text))
		 ) AS string_to_row
	ORDER BY c asc
) as characters_sorted;

Tak przygotowane zapytanie opakowujemy w funkcje PL/pg_SQL i parametryzujemy.

CREATE OR REPLACE FUNCTION normalize(text) RETURNS TEXT AS $$
DECLARE
	input_text ALIAS FOR $1;
	normalized_text TEXT;
BEGIN
	SELECT INTO normalized_text string_agg(c, '') from (
	
		SELECT c FROM
		 (
			SELECT 
				substr(cast(slowo as text), i+1, 1) AS c  
			FROM 
				generate_series(0,40) AS s(i), (SELECT input_text AS slowo) as sub
			WHERE
				i < length(cast(slowo as text))
			 ) AS string_to_row
		ORDER BY c asc
	) as characters_sorted;

	RETURN normalized_text;
END;
$$ LANGUAGE plpgsql;

Przykłady użycia

Sortujemy string po literach alfabetu:

pgsql=> SELECT normalize('młarcóśćążin');
  normalize('młarcóśćążin')
-------------------------
  aącćiłmnórśż              
(1 row)

Sprawdzamy, czy 2 stringi są permutacjami jednego wyjściowego stringu.

pgsql> SELECT normalize('mracin') = normalize('marcin');
 ?column?
-------------------------
  t
(1 row )