levenshtein distance

Kako se to implementira na veliko podatkov v bazi ?
Ok milijon stringov in primerjanje vsakega z vsakim ?
Vem za stram kjer naredi fuzzy match v parih sekundah, naprimer za tole

Fosilella farinosa (dani string)
Fosliella farinosa (string ki ga najde)

Če bi primerjali vsak string v bazi s danim stringom, par sekund ni variante ?
Da dela s sondex-om dvomim ker najde rešitve tudi za bolj zatipkane stringe.

Ok, si bom prebral kaj je ta metaphone.

Najbrž metaphone ne bi delal če bi stavek kar zlepil skupaj (ves presledke ven) ...

Hvala.

Red_Mamba je 18. jan 2016 ob 16:31 izjavil:

a to rabis samo cele stringe primerjat?
ker ce ja izracunas hash vrednosti za vse in jih primerjas po teh

S tem si pač ne moreš pomagat nič, to ti samo pove če sta enaka, kar pa že tako ali tako veš brez hash - a.

Če dobro pogledaš ta dva stringa sta malo različna, drugi nekaj pomeni, prvi pa čisto nič.

Fosilella farinosa (dani string)
Fosliella farinosa (string ki ga najde)

alora nekaj, kar slućajno vem da ni nič (ali skoraj gotovo nič) (jih imam par 100 v eni tabeli), hočem primerjat z eno tabelo (recimo milijon recordov) kjer pa so zagotovo vredu stringi.

BRBR je 18. jan 2016 ob 16:34 izjavil:

alora nekaj, kar slućajno vem da ni nič (ali skoraj gotovo nič) (jih imam par 100 v eni tabeli), hočem primerjat z eno tabelo (recimo milijon recordov) kjer pa so zagotovo vredu stringi.

takale ad-hoc zadeva ni vredna kakšnega igranja z zgoščevanjem, to bi imelo smisel kvečjemu, če rabiš dati uporabniku trenutne povratne informacije, recimo ob vnosu, tako pa poženeš direkt levenstheina na celi miljonski tabeli enkrat, ko zadeva ni močno obremenjena, naslednje jutro preveriš rezultate, pa je.

double metaphone ti izračuna do dve zgoščevalni oznaki za posamezno besedo, zaradi različnih črkovanj v različnih jezikih (v tvojem primeru ali je g v aglitheis tih je zgošč. oznaka ALTS, če se g izgovarja in je oznaka AKLOS, pri carinata teh razlik ni in je edina oznaka KRNT), pri nas smo uporabili ujemanje po katerikoli oznaki za identificiranje kandidata.

Nekako takole (primer je treba še popraviti, da ne bo ujemanja v null vrednosti, če imaš za besed samo en metaphone):

select originaltable.* from words word1 innerjoin words word2 on word1.foreignkey = word2.foreignkey inner join originaltable on word1.foreignkey = originaltable.key
where (word1.metaphone1 = @word1metaphone1 or word1.metaphone2 = @word1metaphone1 or word1.metaphone1 = @word1metaphone2 or word1.metaphone2 = @word1metaphone2)
and (word2.metaphone1 = @word2metaphone1 or word2.metaphone2 = @word2metaphone1 or word2.metaphone1 = @word2metaphone2 or word2.metaphone2 = @word2metaphone2)
and word1.ordinal +1 = word2.ordinal;

Indeksiraš, potem po potrebi query še optimiziraš, čez kandidate poženeš levenstheina in tudi pri miljonskih tabelah se da dobiti odziv v redu nekaj sto milisekund za približno iskanje.

Sistem za katerega smo to pred mnogimi leti naredili je že nekaj časa v pokoju in ga ne bi oživljal. Koda za to je napisana v VBScriptu, ker se je poizvedbe delalo v ASP in pa celo v Outlookovem formularju (kjer je bil VBScript edina opcija). Sem pa poiskal kodo v starem repositoryju.

Download for 48 hours.