Hogyan használjuk a fuzzy karakterlánc-illesztést a Postgresql-lel

Tény: az emberek elgépelnek hibákat, vagy egyszerűen gyakran használnak alternatív helyesírást.

Bármi is legyen az ok, gyakorlati szempontból a hasonló karakterláncok különböző változatai kihívásokat jelenthetnek a szoftverfejlesztők számára. Alkalmazásodnak képesnek kell lennie ezen elkerülhetetlen éles esetek kezelésére.

Vegyünk például neveket. Néhol Peter mellett megyek, máshol Pete mellett. A nevem a többi változat mellett a következőkkel ábrázolható:

  • "Pete Gleeson"
  • "Peter J Gleeson"
  • "P Gleeson úr"
  • - Gleeson, Peter

És nem is beszélve a vezetéknevem alternatív írásmódjairól, például a "Gleason" -ról. Ezek a különböző variációk csak egy karaktersorozathoz - programszerűen egymáshoz illesztés nem tűnhet kézenfekvőnek.

Szerencsére vannak megoldások odakinn.

Ezeknek a megoldásoknak az általános neve „fuzzy string matching”. A „fuzzy” arra a tényre utal, hogy a megoldás két húr összehasonlításakor nem keres tökéletes, pozíciónkénti egyezést. Ehelyett lehetővé teszik bizonyos mértékű eltérést (vagy „homályosságot”).

Számos programozási nyelven állnak rendelkezésre megoldások. Ma megvizsgáljuk a Postgresql (vagy „Postgres”) elérhető opcióit - egy széles körben használt nyílt forráskódú SQL-dialektust, néhány komolyan hasznos kiegészítő funkcióval.

Felállítása

Először ellenőrizze, hogy a Postgres telepítve van-e a gépére.

Ezután hozzon létre egy új adatbázist a saját könyvtárában (nevezheti tetszőlegesnek, itt én fuzz-demónak hívtam). A parancssorból:

$ mkdir fuzz-demo && cd fuzz-demo $ initdb . $ pg_ctl -D . start $ createdb fuzz-demo

Ehhez a bemutatóhoz egy táblázatot használtam a Modern Művészetek Múzeumának művészeiről. Letöltheti az Artists.csv fájlt a Kaggle oldalról.

Ezután elindíthatja a psql-t (a Postgresql terminálalapú kezelőfelülete):

$ psql fuzz-demo

Most hozzon létre egy táblázatot artists:

CREATE TABLE artists ( artist_id INT, name VARCHAR, nationality VARCHAR, gender VARCHAR, birth_year INT, death_year INT);

Végül a Postgresql MÁSOLÁS funkciójával átmásolhatja az artist.csv tartalmát a táblázatba:

COPY artists FROM '~/Downloads/artists.csv' DELIMTER ',' CSV HEADER;

Ha eddig minden működött, akkor el kell tudni kezdeni az előadók táblázatának lekérdezését.

SELECT * FROM artists LIMIT 10;

Helyettesítő karakter szűrők

Mondja, hogy emlékszik egy Barbara nevű művész keresztnevére, de nem emlékszik egészen a második nevére. A "Hep ..." szóval kezdődött, de nem biztos benne, hogy végződött.

Itt használhat szűrőt és az SQL helyettesítő karakter operátorát %. Ez a szimbólum tetszőleges számú meg nem határozott karaktert jelent.

SELECT * FROM artists WHERE name LIKE 'Barbara%' AND name LIKE '%Hep%';

A szűrő első része olyan előadókat talál, akiknek neve Barbara betűvel kezdődik, és bármilyen karakterkombinációval végződik.

A szűrő második része megtalálja azokat az előadókat, akiknek neve bármilyen karakterkombinációval kezdődhet és véget vehet, de a 'Hep' betűket ebben a sorrendben tartalmaznia kell.

De mi van akkor, ha nem vagy biztos egyik név helyesírásában sem? A szűrők és a helyettesítő karakterek csak eddig jutnak el hozzád.

Trigrammák használata

Szerencsére a Postgres hasznos kiterjesztéssel rendelkezik a fülbemászó pg_trgm névvel. Engedélyezheti a psql-ről az alábbi paranccsal:

CREATE EXTENSION pg_trgm;

Ez a kiterjesztés néhány hasznos funkciót tartalmaz a fuzzy string illesztéshez. Az alapelv a trigrammák használata (amelyek úgy hangzanak, mint valami Harry Potterből).

A trigrammak egy húr három egymást követő betűből álló csoportokra bontásával jönnek létre. Például a "hello" karakterláncot a következő trigrammok képviselik:

  • "h", "he", "hel", "ell", "llo", "lo"

Összehasonlítva, hogy a trigrammkészlet mennyire hasonlít két sztringre, meg lehet becsülni, hogy mennyire hasonlítanak egymásra a 0 és 1 közötti skálán. Ez lehetővé teszi a fuzzy egyezést, beállítva egy hasonlósági küszöböt, amely felett a húrok egyezőnek tekinthetők.

SELECT * FROM artists WHERE SIMILARITY(name,'Claud Monay') > 0.4 ;

Talán szeretné látni az első öt mérkőzést?

SELECT * FROM artists ORDER BY SIMILARITY(name,'Lee Casner') DESC LIMIT 5;

Az alapértelmezett küszöbérték 0,3. Ebben %az esetben az operátort rövidítésként használhatja a homályos illesztési nevek esetleges egyezéssel szemben:

SELECT * FROM artists WHERE name % 'Andrey Deran';

Talán csak a név egy részéről van ötlete. Az %operátor lehetővé teszi, hogy összehasonlítson egy tömb elemeivel, így egyezhet a név bármely részével. A következő lekérdezés a Postgres STRING_TO_ARRAYfüggvény segítségével osztja fel az előadók teljes nevét külön nevek tömbjeire.

SELECT * FROM artists WHERE 'Cadinsky' % ANY(STRING_TO_ARRAY(name,' '));

Fonetikus algoritmusok

A fuzzy string illesztés másik megközelítése a fonetikus algoritmusoknak nevezett algoritmusok csoportjából származik.

Ezek olyan algoritmusok, amelyek szabálykészleteket használnak a karakterlánc rövid kóddal történő ábrázolására. A kód tartalmazza a legfontosabb információkat arról, hogy a karakterláncnak hogyan kell szólnia, ha felolvassa. Ezeknek a rövidített kódoknak az összehasonlításával lehet homályosítani azokat a karakterláncokat, amelyek másképp vannak írva, de egyformán hangzanak.

A Postgres egy kiterjesztéssel rendelkezik, amely lehetővé teszi ezeknek az algoritmusoknak a használatát. A következő paranccsal engedélyezheti:

CREATE EXTENSION fuzzystrmatch;

One example is an algorithm called Soundex. Its origins go back over 100 years - it was first patented in 1918 and was used in the 20th century for analysing US census data.

Soundex works by converting strings into four letter codes which describe how they sound. For example, the Soundex representations of 'flower' and 'flour' are both F460.

The query below finds the record which sounds like the name 'Damian Hurst'.

SELECT * FROM artists WHERE nationality IN ('American', 'British') AND SOUNDEX(name) = SOUNDEX('Damian Hurst');

Another algorithm is one called metaphone. This works on a similar basis to Soundex, in that it converts strings into a code representation using a set of rules.

The metaphone algorithm will return codes of different lengths (unlike Soundex, which always returns four characters). You can pass an argument to the METAPHONE function indicating the maximum length code you want it to return.

SELECT artist_id, name, METAPHONE(name,10) FROM artists WHERE nationality = 'American' LIMIT 5;

Because both metaphone and Soundex return strings as outputs, you can use them in other fuzzy string matching functions. This combined approach can yield powerful results. The example below finds the five closest matches for the name Si Tomlee.

SELECT * FROM artists WHERE nationality = 'American' ORDER BY SIMILARITY( METAPHONE(name,10), METAPHONE('Si Tomlee',10) ) DESC LIMIT 5;

Here, a trigram-only approach would not have helped much, as there is little overlap between 'Cy Twombly' and 'Si Tomlee'. In fact, these only have a SIMILARITY score of 0.05, even though they sound similar when read aloud.

Due to their historical origins, neither of these algorithms works well with names or words of non-English language origin. However, there are more internationally-focused versions.

One example is the double metaphone algorithm. This uses a more sophisticated set of rules for producing metaphones. It can provide alternative encodings for English and non-English origin strings.

As an example, see the query below. It compares the double metaphone outputs for different spellings of Spanish artist Joan Miró:

SELECT 'Joan Miró' AS name, DMETAPHONE('Joan Miró'), DMETAPHONE_ALT('Joan Miró') UNION SELECT 'Juan Mero' AS name, DMETAPHONE('Juan Mero'), DMETAPHONE_ALT('Juan Mero');

Going the distance

Finally, another approach to fuzzy string matching in Postgres is to calculate the 'distance' between strings. There are several ways to do this. Postgres provides functionality to calculate the Levenshtein distance.

At a high level, the Levenshtein distance between two strings is the minimum number of edits required to transform one string into the other. Edits are considered at the character level, and can include:

  • substitutions,
  • deletions, and
  • insertions

For example, the Levenshtein distance between the words 'bigger' and 'better' is 3, because you can transform 'bigger' into 'better' by substituting 'igg' for 'ett'.

Meanwhile, the Levenshtein distance between 'biggest' and 'best' is also 3, because you can transform 'biggest' into 'best' by deleting the letters 'igg'.

See below for a query which finds the artists with the smallest Levenshtein distances from the name 'Freda Kallo'.

SELECT *, LEVENSHTEIN(name, 'Freda Kallo') FROM artists ORDER BY LEVENSHTEIN(name, 'Freda Kallo') ASC LIMIT 5

Thanks for reading!

Hopefully this overview of fuzzy string matching in Postgresql has given you some new insights and ideas for your next project.

There are of course other methods for fuzzy string matching not covered here, and in other programming languages.

For example, if you use Python, take a look at the fuzzywuzzy package. Or if you prefer R, you can use the inbuilt agrep() function, or try out the stringdist package.