Cautare fuzzy si cu regular expression - aglomerare de cuvinte

Salut,

Caut in mai multe fisiere text o aglomerare de cuvinte cheie. Am un program mic in python, dar de fapt poate sa fie in oricare alt limbaj.
Folosesc regular expressions ceva de genul asta:
(white|black|green|yellow|blue).{1,300}(white|black|green|yellow|blue).{1,300}(white|black|green|yellow|blue)
(white|black|green|yellow|blue).{1,300}(white|black|green|yellow|blue).{1,300}(white|black|green|yellow|blue)

Adica caut 6 repetitii de cuvinte cheie.
Apoi daca nu gasesc nimic caut 5 repetitii, apoi, 4....

Dificultatea este ca daca ai un typo si in loc de black in text e "blck" sau "bleck" atunci nu mai merge strategia asta.
Am gasit un fuzzy search cu libraria fuzzysearch, dar ca orice librarie foloseste o functie find_near_matches(target, content, max_l_dist=3) si eu functia asta nu pot sa o pun in regular expression. Merge singura independenta, dar apoi nu mai am aglomeratia, pentru ca asa trebuie sa caut pentru fiecare cuvant cheie, in exemplul meu e vorba de culorile din limba engleza, si nu prea mi se pare asta o forma eficienta. Daca ar trebui sa continui ar trebuie sa gasesc toate formele cuvintelor cheie, e.g. yelow (cu un singur l) si apoi sa construiesc cu asta o regular expression?

Sau e mai bine sa incep cu regular expression, dar asa nu pot sa aplic fuzzy...
Puteti sa ma ajutati va rog? cum sa fac?

Va multumesc

Cam cat de "retard" te astepti sa fie textul in care cauti?
Altfel spus: e acceptabil ca "xg" sa fie o greseala pentru "black"? Daca da: de unde stii ca autorul a intentionat sa scrie "black" si nu "red" (avand in vedere ca oricum nici unul nu are legatura cu "xg")?
Stii ce zic?

Nu e acceptabil sa insiri toate "greselile": (white|black|green|yellow|blue|blck|bleck|whte|gren|yelow|<alte greseli>).{1,300}{1,6} ?

Edited by darkangel2, 07 January 2024 - 14:20.

Nu ar fi mai bine ca prima data sa-ti definesti ce vrei sa consideri ca match si ce nu ?
Eu as defini cit mai clar/concret la ce vreau sa fac match inainte sa ma gindesc cum sa scriu expresia regulata sau cum sa fac fuzzy search

In felul in care ai scris tu expresia aia eu inteleg ca vrei sa faci match doar pentru culorile din lista respectiva care sint scrise corect si sint scrise doar cu litere mici.

De exemplu, fara sa intram in lucruri complicate cum ar fi typo-urile:
black == black
Black != black
wHite != White

Edited by cralin, 07 January 2024 - 14:26.

darkangel2, on 07 ianuarie 2024 - 14:17, said:

Cam 2-3 caractere diferite maxim pentru fiecare cuvant cheie

cralin, on 07 ianuarie 2024 - 14:19, said:

Expresia regulata era doar un exemplu. Si de fapt nu merge sa fac fuzzy search pe expresia regulata.
Am nevoie sa pot sa folosesc expresia regulata dar cu un levensthein_distance de 2 pe fiecare cuvant cheie. Levensthein o face functia fuzzy_search-ul care nu pot sa-l aplic in expresia regulata.

ai incercat cu agrep ?

NAME
	 agrep - print lines approximately matching a pattern
SYNOPSIS
	 agrep [OPTION]... PATTERN [FILE]...
DESCRIPTION
	 Searches for approximate matches of PATTERN in each FILE or standard
	 input. Example: `agrep -2 optimize foo.txt' outputs all lines in file
	 `foo.txt' that match "optimize" within two errors. E.g. lines which
	 contain "optimise", "optmise", and "opitmize" all match.

Edited by cralin, 07 January 2024 - 15:11.

jimmyy, on 07 ianuarie 2024 - 14:31, said:

Cred ca iti trebuie o librarie de expresii regulate "desteapta":
- fie una care deja stie "approximate matches"; plecand de la sugestia lui @cralin, am gasit https://github.com/laurikari/tre
- fie una care permite crearea de "custom matchers" si iti creezi tu un "approximate matcher" bazat pe distanta Levensthein (n-am gasit o astfel de librarie la o cautare rapida)

Aici gasesti pe web pagina de help pentru agrep, are si sectiune cu exemple:   https://www.tgries.d...p/agrephlp.html

In Linux ai man page pentru agrep.

Pentru Python:
AGREPY: Python port of agrep string matching with errors

Edited by cralin, 07 January 2024 - 16:17.

jimmyy, on 07 ianuarie 2024 - 13:44, said:

Am avut acum multa vreme (7-8 ani) acceasi problema: trebuia sa caut diverse forme (flexionari etc) ale aceluiasi cuvant, dar, in acelasi timp, puteam sa am si typos etc. Pe vremea aceea - exact ca si in problema ta - existau doar biblioteci care faceau doar un tip de comparare (regex sau levenshetein distance). Aparuse atunci o biblioteca chiar in python (sper sa o regasesc) care rezolva ambele probleme. Returna un scor de apropiere, ceva de genul numar de caractere diferite etc. Revin daca gasesc numele bibliotecii.

Poti incepe cautand singur: https://www.google.c...gex levenshtein

Nu mai stiu daca e chiar una din bibliotecile de aici - cred ca fuzzywuzzy:
https://www.datacamp...y-string-python

Sau vezi https://maxhalford.g...-python-library

... sau cauta dupa "fuzzy regex python". Cred ca s-au mai schimbat lucrurile multisor de-atunci, in materie de librarii. Sunt vreo 8 ani...

LE2: Tocmai ce citii - chiar noile versiuni regex din Python ar permite asa ceva (sper sa nu ma insel, nu mai am capul in asta):

https://pypi.org/project/regex/ - vezi Sectiunea "Approximate “fuzzy” matching"

Poate revii si cu un feedback. Mersi.

Vă mulțumesc frumos.
Cu siguranță o să revin,  mai întâi trebuie să citesc și să încerc.  În seara asta trebuie să lucrez un pic pentru la servici și să mă ocup de copii.

aaaa4567, on 07 ianuarie 2024 - 20:46, said:

Multumesc frumos, da asa e Approximate "fuzzy" matching ar fi solutia, dar nu merge, si nici nu cred ca ar putea sa mearga.

Codul asta functioneaza

print(regex.search(r'(alb|negr|neagr).{1,300}(alb|negr|neagr){e<=3}', 'hjalbi nxxegtrut'))

pentru ca reuseste sa-l gaseasca pe alb in hjalbi si apoi cu 3 schimbari ajunge la 'hjalbi negrut' si asta e ok, se potriveste cu paternul.


Codul asta nu merge, returneaza None si e gresit.

		print(regex.search(r'(alb|negr|neagr).{1,300}(alb|negr|neagr){e<=2}', 'hjaljb negtrut'))

Este gresit pentru ca daca scot litera 'j' si 't' si ajung la 'hjalb negrut' atunci cu dous schimbari am ajuns la paternul meu.
Parerea mea e ca nu merge pentru ca am shimbari si la alb si la negru in acelasi timp. Am citit

O sa mai citesc. Pare usoara la prima vedere, dar m-am pierdut un pic in explicatiile de backtracking... si parca prin clasa a IX am studiat backtracking-ul...
Ma intreb daca oare chiar este posibil, poate incerc sa rezolv ceva care e imposibil.... si atunci inseamna ca imi pierd timpul. Dar inca nu m-am dat batut

In orice caz va multumesc pentru ajutor, ca fara el cautam pe google inca doi ani de zile si nu gaseam link-urile pe care le-ati postat.
Mai citesc si mai revin