Este un fapt – oamenii fac greșeli de scriere sau pur și simplu folosesc ortografii alternative frecvent.

Oricare ar fi cauza, din punct de vedere practic, diferite variante de șiruri similare pot pune provocări dezvoltatorilor de software. Aplicația dvs. trebuie să fie capabilă să gestioneze aceste cazuri marginale inevitabile.

Luați nume, de exemplu. Merg pe lângă Peter în unele locuri, Pete în altele. Printre alte variante, numele meu poate fi reprezentat de:

  • „Pete Gleeson”
  • „Peter J Gleeson”
  • „Domnul P Gleeson”
  • „Gleeson, Peter”

Și asta nu mai vorbim de ortografiile alternative ale numelui meu de familie, cum ar fi „Gleason”. Toate aceste variații diferite pentru un singur șir – potrivirea lor una cu alta programatic ar putea să nu pară evidentă.

Din fericire, există soluții acolo.

Numele generic pentru aceste soluții este „potrivirea șirului fuzzy”. „Fuzzy” se referă la faptul că soluția nu caută o potrivire perfectă poziție cu poziție atunci când se compară două șiruri. În schimb, acestea permit un anumit grad de nepotrivire (sau „neclaritate”).

Există soluții disponibile în multe limbaje de programare diferite. Astăzi, vom explora câteva opțiuni disponibile în Postgresql (sau „Postgres”) – un dialect SQL open source utilizat pe scară largă, cu câteva caracteristici suplimentare foarte utile.

Configurare

Mai întâi, asigurați-vă că au instalat Postgres pe aparatul dvs..

Apoi, creați o nouă bază de date în propriul director (îl puteți numi oricum doriți, aici l-am numit „fuzz-demo”). Din linia de comandă:

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

Pentru această demonstrație, am folosit un tabel cu detalii despre artiști în Muzeul de Artă Modernă. Poti descărcați fișierul artists.csv din Kaggle.

Apoi, puteți începe psql (un front-end bazat pe terminal pentru Postgresql):

$ psql fuzz-demo

Acum, creați un tabel numit artists:

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

În cele din urmă, puteți utiliza funcția COPIERE a Postgresql pentru a copia conținutul artistului.csv în tabel:

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

Dacă totul a funcționat până acum, ar trebui să puteți începe să interogați tabelul artiștilor.

SELECT * FROM artists LIMIT 10;

Filtre wildcard

Spuneți că vă amintiți prenumele unei artiste numite Barbara, dar nu vă amintiți cu siguranță al doilea nume. A început cu „Hep …”, dar nu sunteți sigur cum s-a încheiat.

Aici puteți utiliza un filtru și operatorul wildcard SQL %. Acest simbol reprezintă orice număr de caractere nespecificate.

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

Prima parte a filtrului găsește artiști al căror nume începe cu „Barbara” și se termină prin orice combinație de personaje.

A doua parte a filtrului găsește artiști al căror nume poate începe și se poate încheia cu orice combinație de caractere, dar trebuie să conțină literele „Hep” în această ordine.

Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Producția o dă artistului britanic Barbara Hepworth

Dar dacă nu sunteți sigur de ortografia oricărui nume? Filtrele și wildcard-urile te vor duce până acum.

Folosind trigrame

Din fericire, Postgres are o extensie utilă cu numele atrăgător pg_trgm. O puteți activa din psql folosind comanda de mai jos:

CREATE EXTENSION pg_trgm;

Această extensie aduce cu sine câteva funcții utile pentru potrivirea șirului neclar. Principiul de bază este utilizarea trigramelor (care sună ca ceva din Harry Potter).

Trigramele se formează prin ruperea unui șir în grupuri de trei litere consecutive. De exemplu, șirul „salut” ar fi reprezentat de următorul set de trigrame:

  • „h”, „el”, „hel”, „ell”, „llo”, „lo”

Comparând cât de asemănătoare sunt setul de trigrame între două șiruri, este posibil să se estimeze cât de asemănătoare sunt pe o scară între 0 și 1. Acest lucru permite o potrivire fuzzy, prin stabilirea unui prag de similaritate peste care se consideră că șirurile se potrivesc.

SELECT
	*
FROM artists
WHERE SIMILARITY(name,'Claud Monay') > 0.4 ;
1612021208 575 Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Ieșirea este Claude Monet (cu ortografia corectă!)

Poate doriți să vedeți primele cinci meciuri?

SELECT 
	*
FROM artists
ORDER BY SIMILARITY(name,'Lee Casner') DESC
LIMIT 5;
1612021208 87 Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Cel mai apropiat meci este Lee Krasner, urmat de Lee Chesney

Pragul implicit este 0,3. Puteți utiliza % operator în acest caz ca prescurtare pentru nume de potrivire fuzzy cu o potrivire potențială:

SELECT
	*
FROM artists
WHERE name % 'Andrey Deran';
1612021208 727 Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Producția oferă doi artiști, inclusiv unul Andre Derain

Poate că aveți doar o idee despre o parte a numelui. % operatorul vă permite să comparați cu elementele unui tablou, astfel încât să puteți compara cu orice parte a numelui. Următoarea interogare folosește Postgres ‘ STRING_TO_ARRAY funcția de a împărți numele complete ale artiștilor în matrice de nume separate.

SELECT
	*
FROM artists
WHERE 'Cadinsky' % ANY(STRING_TO_ARRAY(name,' '));
1612021208 184 Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Ieșirea dă două rânduri, inclusiv Vasily Kandinsky

Algoritmi fonetici

O altă abordare a potrivirii șirurilor fuzzy provine dintr-un grup de algoritmi numiți algoritmi fonetici.

Acestea sunt algoritmi care utilizează seturi de reguli pentru a reprezenta un șir folosind un cod scurt. Codul conține informațiile cheie despre cum ar trebui să sune șirul dacă este citit cu voce tare. Prin compararea acestor coduri scurtate, este posibil să se potrivească șiruri de caractere care sunt scrise diferit, dar sună la fel.

Postgres vine cu o extensie care vă permite să utilizați unii dintre acești algoritmi. O puteți activa cu următoarea comandă:

CREATE EXTENSION fuzzystrmatch;

Un exemplu este un algoritm numit Soundex. Originile sale datează de peste 100 de ani – a fost brevetat pentru prima dată în 1918 și a fost folosit în secolul al XX-lea pentru analiza datelor recensământului SUA.

Soundex funcționează prin conversia șirurilor în patru coduri de litere care descriu cum sună. De exemplu, reprezentările Soundex ale „florii” și „făinii” sunt ambele F460.

Interogarea de mai jos găsește înregistrarea care sună ca numele „Damian Hurst”.

SELECT
	*
FROM artists
WHERE nationality IN ('American', 'British')
AND SOUNDEX(name) = SOUNDEX('Damian Hurst');
1612021208 709 Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Rezultatul include artistul britanic Damien Hirst (cu ortografia corectă)

Un alt algoritm este cel numit metafon. Acest lucru funcționează pe o bază similară cu Soundex, prin faptul că convertește șirurile într-o reprezentare de cod folosind un set de reguli.

Algoritmul metafonului va returna coduri de diferite lungimi (spre deosebire de Soundex, care returnează întotdeauna patru caractere). Puteți transmite un argument către METAPHONE funcție care indică codul de lungime maximă pe care doriți să îl returneze.

SELECT
	artist_id,
    name,
    METAPHONE(name,10)
FROM artists
WHERE nationality = 'American'
LIMIT 5;
1612021208 394 Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Se produce metafonul fiecărui artist.

Deoarece atât metafonul cât și Soundex returnează șiruri ca ieșiri, le puteți folosi în alte funcții de potrivire a șirurilor fuzzy. Această abordare combinată poate produce rezultate puternice. Exemplul de mai jos găsește cele mai apropiate cinci potriviri pentru numele Si Tomlee.

SELECT
	*
FROM artists
WHERE nationality = 'American'
ORDER BY SIMILARITY(
	METAPHONE(name,10),
    METAPHONE('Si Tomlee',10)
    ) DESC
LIMIT 5;
1612021208 67 Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Rezultatul de top este artistul american Cy Twombly.

Aici, o abordare numai cu trigramă nu ar fi ajutat prea mult, deoarece există puține suprapuneri între „Cy Twombly” și „Si Tomlee”. De fapt, acestea au doar un SIMILARITY scor de 0,05, chiar dacă sună similar atunci când sunt citite cu voce tare.

Datorită originilor lor istorice, niciunul dintre acești algoritmi nu funcționează bine cu nume sau cuvinte de origine non-engleză. Cu toate acestea, există mai multe versiuni axate pe plan internațional.

Un exemplu este algoritmul dublu metafon. Aceasta folosește un set mai sofisticat de reguli pentru producerea metafonelor. Poate oferi codificări alternative pentru șirurile de origine engleză și non-engleză.

De exemplu, consultați interogarea de mai jos. Compară ieșirile duble de metafon pentru diferite ortografii ale artistului spaniol 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');
1612021208 673 Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Atât ortografia corectă, cât și greșeala de ortografie produc JNMR și ANMR ca metafone

Parcurgând distanța

În cele din urmă, o altă abordare a potrivirii șirurilor fuzzy în Postgres este calcularea „distanței” dintre șiruri. Există mai multe modalități de a face acest lucru. Postgres oferă funcționalitate pentru calcularea distanței Levenshtein.

La un nivel ridicat, distanța Levenshtein dintre două șiruri este numărul minim de editări necesare pentru a transforma un șir în celălalt. Editările sunt luate în considerare la nivel de personaje și pot include:

  • substituții,
  • ștergeri și
  • inserții

De exemplu, distanța Levenshtein dintre cuvintele „mai mare” și „mai bun” este 3, deoarece puteți transforma „mai mare” în „mai bine” prin înlocuirea „igg” cu „ett”.

Între timp, distanța Levenshtein între „cel mai mare” și „cel mai bun” este, de asemenea, 3, deoarece puteți transforma „cel mai mare” în „cel mai bun” ștergând literele „igg”.

Vedeți mai jos pentru o interogare care găsește artiștii cu cele mai mici distanțe Levenshtein de la numele „Freda Kallo”.

SELECT
	*,
    LEVENSHTEIN(name, 'Freda Kallo')
FROM artists
ORDER BY LEVENSHTEIN(name, 'Freda Kallo') ASC
LIMIT 5
1612021208 101 Cum se utilizeaza potrivirea sirului fuzzy cu Postgresql
Artistul mexican Frida Kahlo este cel mai apropiat meci, urmat de Fred Niblo, Fred Taylor și Frank Gallo

Mulțumesc pentru lectură!

Sperăm că această prezentare generală a potrivirii șirurilor fuzzy în Postgresql v-a oferit câteva idei și idei noi pentru următorul dvs. proiect.

Există desigur și alte metode de potrivire a șirurilor neclare care nu sunt acoperite aici și în alte limbaje de programare.

De exemplu, dacă utilizați Python, aruncați o privire la pachet fuzzywuzzy. Sau, dacă preferați R, puteți utiliza incorporat agrep() sau încercați funcția pachet stringdist.