Kuidas kasutada udust stringi sobitamist Postgresql-iga

See on tõsiasi - inimesed teevad kirjavigu või kasutavad sageli õigekirjavigu.

Olenemata põhjusest, võivad praktilisest vaatenurgast lähtudes sarnaste stringide erinevad variandid tarkvaraarendajatele väljakutseid esitada. Teie rakendus peab olema võimeline nende vältimatute servajuhtumitega hakkama saama.

Võtame näiteks nimed. Ma lähen mõnes kohas Peterist, mõnes Pete. Muude variantide hulgas võib minu nime esindada:

  • "Pete Gleeson"
  • "Peter J Gleeson"
  • "Hr P Gleeson"
  • "Gleeson, Peter"

Ja see ei pea mainimata mu perekonnanime alternatiivseid õigekirju, näiteks "Gleason". Kõik need erinevad variatsioonid ainult ühe stringi jaoks - nende programmiline üksteisega sobitamine ei pruugi tunduda ilmne.

Õnneks on seal lahendusi.

Nende lahenduste üldnimetus on „fuzzy string matching”. „Fuzzy” viitab asjaolule, et lahendus ei otsi kahe stringi võrdlemisel täiuslikku positsioonipositsiooni. Selle asemel võimaldavad nad teatud määral mittevastavust (või „hägusust”).

Saadaval on lahendusi paljudes erinevates programmeerimiskeeltes. Täna uurime mõningaid võimalusi, mis on saadaval Postgresqlis (või 'Postgres') - laialt levinud avatud lähtekoodiga SQL-murdes, millel on mõned tõsiselt kasulikud lisafunktsioonid.

Seadistan

Kõigepealt veenduge, et teie arvutisse oleks installitud Postgres.

Seejärel looge oma andmebaasis uus andmebaas (võite seda nimetada mis iganes soovite, siin ma nimetasin seda "fuzz-demo"). Käsurealt:

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

Selle demo jaoks kasutasin moodsa kunsti muuseumis asuvat tabelit kunstnike kohta. Faili Artists.csv saate alla laadida Kaggle'ist.

Järgmisena võite käivitada psql (Postgresqli terminalipõhine kasutajaliides):

$ psql fuzz-demo

Nüüd looge tabel nimega artists:

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

Lõpuks saate artist.csv sisu tabelisse kopeerimiseks kasutada funktsiooni COPY Postgresql.

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

Kui kõik on seni toiminud, peaksite saama hakata esitajate tabelit pärima.

SELECT * FROM artists LIMIT 10;

Metamärgifiltrid

Oletame, et mäletate Barbara nimelise kunstniku eesnime, kuid ei mäleta päris täpselt tema teist nime. See algas sõnaga "Hep ...", kuid te pole kindel, kuidas see lõppes.

Siin saate kasutada filtrit ja SQL-i metamärki %. See sümbol tähistab mis tahes arvu täpsustamata märke.

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

Filtri esimene osa leiab artistid, kelle nimi algab tähega „Barbara” ja lõpeb mis tahes tähemärkide kombinatsiooniga.

Filtri teine ​​osa leiab esitajad, kelle nimi võib alata ja lõppeda mis tahes tähemärkide kombinatsiooniga, kuid peab selles järjekorras sisaldama tähti „Hep”.

Aga mis siis, kui te pole mõlema nime õigekirjas kindel? Filtrid ja metamärgid viivad teid siiani.

Trigrammide kasutamine

Õnneks on Postgresil kasulik laiendus meeldejääva nimega pg_trgm. Selle saate lubada psql-ist, kasutades järgmist käsku:

CREATE EXTENSION pg_trgm;

See laiendus toob endaga kaasa häid stringide sobitamise abistavaid funktsioone. Aluspõhimõte on trigrammide kasutamine (mis kõlab nagu midagi Harry Potterist välja).

Trigrammid moodustatakse stringi jagamisel kolme järjestikuse tähega rühmadeks. Näiteks string "tere" tähistatakse järgmise trigrammide komplektiga:

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

Võrreldes seda, kui sarnased on trigrammide kogumid kahe stringi vahel, on võimalik hinnata, kui sarnased nad on skaalal 0–1. See võimaldab hägusat sobitamist, määrates sarnasuse künnise, mille kohal stringe vastavaks peetakse.

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

Võib-olla soovite näha viit parimat vastet?

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

Vaikimisi künnis on 0,3. Sellisel juhul saate %operaatorit kasutada ebamääraste sobitavate nimede potentsiaalse vaste lühenumbrina:

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

Võib-olla on teil aimu ainult ühest nimeosast. %Operaator saab võrrelda vastu massiivi elemente, nii et sa ei sobi igasuguse osa nimest. Järgmine päring kasutab STRING_TO_ARRAYfunktsiooni Postgres, et jagada artistide täisnimed eraldi nimede massiivideks.

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

Foneetilised algoritmid

Teine ebamäärase stringi sobitamise lähenemisviis tuleneb algoritmide rühmast, mida nimetatakse foneetilisteks algoritmideks.

Need on algoritmid, mis kasutavad reeglikomplekte stringi esindamiseks lühikoodi abil. Kood sisaldab põhiteavet selle kohta, kuidas string kõlama peaks, kui seda ette lugeda. Nende lühendatud koodide võrdlemisel on võimalik summutada sobivaid stringe, mis on kirjutatud erinevalt, kuid kõlavad sarnaselt.

Postgresil on laiendus, mis võimaldab teil kasutada mõnda neist algoritmidest. Selle saate lubada järgmise käsuga:

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.

Näiteks kui kasutate Pythoni, vaadake fuzzywuzzy paketti. Või kui eelistate R-i, võite kasutada sisseehitatud agrep()funktsiooni või proovida stringdist-paketti.