Ce algoritm ați utiliza cel mai bine pentru similaritatea șirurilor de caractere? (Inginerie software, Algoritmi, Potrivirea Șirurilor De Caractere)

Squiggs. a intrebat.
a intrebat.

Proiectez un plugin care să identifice în mod unic conținutul din diverse pagini web, pe baza adreselor.

Așadar, s-ar putea să am o adresă care să arate astfel:

1 someawesome street, anytown, F100 211

mai târziu pot găsi această adresă într-un format ușor diferit.

1 someawesome street, F100 211,

sau poate la fel de vagă ca

someawesome street F100

Acestea sunt, din punct de vedere tehnic, aceeași adresă, dar cu un anumit nivel de similaritate. Aș dori să a) generez un identificator unic pentru fiecare adresă pentru a efectua căutări și b) să îmi dau seama când apare o adresă foarte asemănătoare.

Ce algoritmi / tehnici / metrici de șiruri ar trebui să analizez? Distanța Levenshtein pare a fi o alegere evidentă, dar sunt curios dacă există alte abordări care s-ar preta aici.

Comentarii

  • „Distanța Levenshtein” nu este un algoritm. –  > Por gnasher729.
  • Dacă nu introduceți o analiză de bază, distanța Levenstein brută nu va fi atât de bună. Ar trebui să încercați cel puțin să identificați cuvintele care ar putea fi nume de străzi, de orașe etc. și cele care ar putea fi numere de străzi sau coduri poștale. Apoi, poate aplicați Levenstein pe acestea cu ajutorul unui corector statistic fuzzy matcher alimentat de nume reale de localități/străzi. Nu este un lucru ușor 🙂 – utilizator44761
  • @gnasher: Dar o funcție care să calculeze distanța Levenshtein este un algoritm. Fără o astfel de funcție, distanța Levenshtein este doar o curiozitate intelectuală. –  > Por Robert Harvey.
  • Am găsit o explicație foarte practică, cu exemple, aici: comparația algoritmilor. În concluzie, ei recomandă să folosiți The Jaro-Winkler deoarece algoritmul lui Levenstein depinde de lungimea șirului de caractere, deci nu este utilă pentru comparație. –  > Por Sandra Meneses.
  • Vă rugăm să nu scrieți răspunsuri numai cu link-uri. –  > Por Jan Doggen.
7 răspunsuri
Christophe

Algoritmul lui Levenstein se bazează pe numărul de inserții, ștergeri și substituiri în șiruri de caractere.

Din păcate, nu ia în considerare o greșeală de ortografie comună, care este transpunerea a 2 caractere (de exemplu, someawesome vs someaewsome). Așadar, aș prefera metoda mai robustă algoritmul Damerau-Levenstein.

Nu cred că este o idee bună să aplicăm distanța pe șiruri întregi, deoarece timpul crește brusc odată cu lungimea șirurilor comparate. Dar și mai rău, atunci când componentele adreselor, cum ar fi ZIP, sunt eliminate, adrese complet diferite pot să se potrivească mai bine (măsurate folosind calculatorul Levenshtein online):

1 someawesome street, anytown, F100 211       (reference) 
1 someawesome st.,anytown                     (difference of 15, same address)     
1 otherplaces street,anytown,F100211          (difference of 13, different ddress) 
1 sameawesome street, othertown, CA98200      (difference of 13, different ddress)
anytown, 1 someawesome street                 (28 different same address)
anytown, F100 211, 1 someawesome street       (37 different same address)

Aceste efecte tind să se înrăutățească în cazul numelor de străzi mai scurte.

Așa că ar fi bine să folosiți algoritmi mai inteligenți. De exemplu, Arthur Ratz a publicat pe CodeProject un algoritm pentru compararea inteligentă a textului. Algoritmul nu tipărește o distanță (cu siguranță poate fi îmbogățit în consecință), dar identifică unele lucruri dificile, cum ar fi mutarea blocurilor de text (de exemplu, schimbarea între oraș și stradă între primul și ultimul meu exemplu).

Dacă un astfel de algoritm este prea general pentru cazul dumneavoastră, ar trebui atunci să lucrați cu adevărat pe componente și să comparați doar componentele comparabile. Acest lucru nu este un lucru ușor dacă doriți să analizați orice format de adresă din lume. Dar dacă ținta este mai specifică, să zicem SUA, este cu siguranță fezabil. De exemplu, „street”, „st.”, „st.”, „place”, „plazza” și greșelile lor obișnuite de ortografie ar putea dezvălui partea stradală a adresei, a cărei parte din față ar fi, în principiu, numărul. Codul poștal ar ajuta la localizarea orașului sau, alternativ, este probabil ultimul element al adresei sau, dacă nu vă place să ghiciți, ați putea căuta o listă de nume de orașe (de exemplu, descărcând o bază de date gratuită cu coduri poștale). Apoi ați putea aplica Damerau-Levenshtein doar pe componentele relevante.

Comentarii

  • Ce ziceți de sortarea ambelor șiruri de comparație înainte de comparație? Am constatat că acest lucru poate ajuta cu transpoziția. –  > Por openwonk.
Dan Wilson

Întrebați despre algoritmi de similaritate a șirurilor de caractere, dar șirurile dvs. sunt adrese. Aș trimite adresele la un API de localizare, cum ar fi Google Place Search și să utilizați formatted_address ca punct de comparație. Aceasta pare a fi cea mai precisă abordare.

Pentru șirurile de adrese care nu pot fi localizate prin intermediul unei API, puteți recurge la algoritmi de similaritate.

Comentarii

  • +1 Externalizați, astfel încât să beneficiați de puterea experților care să facă munca în locul dumneavoastră. Nu trebuie să fie Google, deoarece există câțiva furnizori de servicii. Nu vă pierdeți timpul făcând acest lucru decât dacă potrivirea adreselor este activitatea dvs. principală. –  > Por LoztInSpace.
paparazzo

Distanța Levenshtein este mai bună pentru cuvinte

Dacă cuvintele sunt (în mare parte) scrise corect, atunci uitați-vă la sac de cuvinte. S-ar putea să pară o exagerare, dar TF-IDF și similitudinea cosinusului.

Sau ați putea folosi gratuit Lucene. Cred că face similaritate cosinusală.

Ucenna

În primul rând, va trebui să analizați pagina web pentru adrese, RegEx este o metodă pe care o puteți folosi, însă poate fi foarte dificil să analizați adresele folosind RegEx. Probabil că va trebui să parcurgeți o listă de formate de adrese potențiale și să folosiți una sau mai multe expresii care să corespundă acestora. Nu sunt prea familiarizat cu parsarea adreselor, dar v-aș recomanda să aruncați o privire la această întrebare care urmează o linie de gândire similară: General Address Parser for Freeform Text.

Distanța Levenshtein este utilă, dar numai după ce ați separat adresa în părțile sale. Luați în considerare următoarele adrese. 123 someawesome st. și 124 someawesome st. Aceste adrese sunt locații total diferite, dar distanța Levenshtein este de numai 1. Acest lucru poate fi aplicat și la ceva de genul 8th st. și 9th st. Nume de străzi similare nu apar de obicei pe aceeași pagină web, dar nu este ceva neobișnuit. De exemplu, pe pagina web a unei școli ar putea apărea adresa bibliotecii de peste drum, sau a bisericii aflate la câteva străzi mai jos. Acest lucru înseamnă că singurele date pentru care distanța Levenshtein poate fi utilizată cu ușurință sunt distanța dintre 2 puncte de date, cum ar fi distanța dintre stradă și oraș.

În ceea ce privește modul de separare a diferitelor câmpuri, este destul de simplu odată ce obținem adresele în sine. Din fericire, cele mai multe adrese vin în formate foarte specifice și, cu puțină magie RegEx, ar trebui să fie posibil să le separăm în diferite câmpuri de date. Chiar dacă adresele nu sunt bine formatate, mai există încă o speranță. Adresele urmează întotdeauna (aproape) ordinea de mărime. Adresa dvs. ar trebui să se încadreze undeva pe o grilă liniară ca aceasta, în funcție de cât de multe informații sunt furnizate și care sunt acestea:

StreetNumber < Street < City < State < Country

Se întâmplă foarte rar, dacă nu chiar deloc, ca adresa să sară de la un câmp la unul care nu este adiacent. Nu veți vedea foarte des o stradă, apoi o țară, sau un număr de stradă, apoi un oraș.

Comentarii

  • Cu excepția faptului că adresele de stradă nu sunt regulate și nu pot fi analizate în mod fiabil prin expresii regulate. Cu siguranță nu pot fi identificate cu exactitate dacă sunt încorporate în text liber. Puteți, desigur, să scrieți câteva expresii regulate diferite pentru a se potrivi cu diferite formate comune, dacă știți deja unde căutați. –  > Por Inutil.
  • @Useless Este adevărat. Este fezabil în teorie, dar am subestimat cantitatea de muncă necesară pentru a pune în ea. Mai ales atunci când există opțiuni potențial mai bune disponibile. Mi-am modificat răspunsul pentru a reflecta acest lucru. –  > Por Ucenna.
John Greene

Un algoritm interesant care este util, dar care necesită o bază de date prestabilită de răspunsuri anterioare se numește: Line edit distance.

Distanța de editare a liniilor, ca funcție, poate returna un răspuns de tipul „cât de diferite sunt aceste două cuvinte”.

Un cuvânt precum „dogma” și „dog”, veți primi înapoi o valoare de 3 (pentru 3 caractere în plus).

Sau „pisică” și „pălărie”, veți primi înapoi o valoare de 1 (pentru un caracter diferit).

(Sursă: https://en.wikipedia.org/wiki/Edit_distance )

Comentarii

  • Care este avantajul față de Levensthtein menționat de OP ? –  > Por Christophe.
kjaquier

Într-adevăr, utilizarea unei funcții de distanță pare a fi o abordare bună. Dar problema este atunci de a găsi cel mai apropiat șir de la o adresă dată, ceea ce este departe de a fi trivial.

Descrieți aici o categorie largă de algoritmi. Consultați Căutarea celui mai apropiat vecin

După cum s-a menționat într-un comentariu, dacă găsiți o modalitate de a separa componentele adresei (numele străzii, numărul etc.), sarcina va fi mult mai ușoară.

Altair7852

LongestCommonSubsequence (din Apache commons-text) poate fi o altă abordare de încercat cu adresele. Dacă definiți similitudinea a două ca raport dintre „lungimea subsecvenței comune / max(lungimi adrese)„, atunci puteți aplica un prag de toleranță – de exemplu, 0,8, care va defini potrivire/neîmperechere. În acest fel, veți putea potrivi adrese precum „1 someawesome st. 1, anytown” și „1 someawesome street. 1, anytown„.

Nu este un algoritm foarte rapid, așa că este posibil să doriți să aplicați rapid failback-uri pentru a minimiza comparațiile. Un exemplu ar fi – evitarea comparației dacă codurile poștale nu se potrivesc sau dacă secvența de cifre extrase este diferită.