incompatibility według Levenshteina...

incompatibility według Levenshteina...
EM
  • Rejestracja:prawie 13 lat
  • Ostatnio:ponad 10 lat
  • Postów:271
0

Pisze prostą wyszukiwarkę plików / zasobów na dysku. Znalazłem podobny temat procentowa zgodność tekstów

polecono tam wykorzystać Algorytm Levenshteina - wyszukałem, zapoznałem się, zaimplementowałem do swoich potrzeb, jednak wyniki jakie uzyskuje nie do końca mnie satysfakcjonują, podam przykład ::

pełna nazwa szukanego pliku na dysku ::

Kopiuj
std::string source_base( "zaawansowane c++ wraz z bibliotekami boost" );

tekst podany w wyszukiwarce

Kopiuj
std::string source_search( "c++ i boost" );

na wyjściu uzyskuje :: compatibility :: 27 %
problem w tym że każdy znak w tekście ma taką samą wagę i pomimo podania 2 słów można je nazwać kluczowymi ( c++, boost ) plik nie zostałby wyszukany z powodu zbyt małej zgodności dla której min ustawiłem na 75 %. Nie chciałbym zmniejszać dopuszczalnego min zgodności więc co mogę zrobić aby dodać mojej wyszukiwarce trochę "inteligencji" ;) ?
Wypróbowałem już opcje z podzieleniem szukanej frazy na części, wrzuceniem tego do std::vector i sprawdzaniu czy podane słowa / znaki występują w oryginale za pomocą std::string::find ale to też się nie sprawdziło...
mogę prosić o podrzucenie jakiegoś pomysłu, wskazówek?

edytowany 2x, ostatnio: emacs
Shalom
  • Rejestracja:ponad 21 lat
  • Ostatnio:około 3 lata
  • Lokalizacja:Space: the final frontier
  • Postów:26433
1

Dzielenie na słowa + cosine similarity? :)
Albo miara Jaccarda, albo nawet lepiej: zmodyfikowana wersja miary jaccarda gdzie zamiast sumy zbiorów w mianowniku masz rozmiar jednego ze zbiorów (liczysz to dla obu zbiorów a potem bierzesz to dla którego masz większy wynik).

http://en.wikipedia.org/wiki/Cosine_similarity
http://en.wikipedia.org/wiki/Jaccard_index
http://en.wikipedia.org/wiki/Bag-of-words_model


"Nie brookliński most, ale przemienić w jasny, nowy dzień najsmutniejszą noc - to jest dopiero coś!"
edytowany 3x, ostatnio: Shalom
EM
nie wiem czy dobrze rozumiem cosine similarity - należy podzielić przecięcie zbiorów przez ich sumę?
Shalom
To jest akurat zmodyfikowana miara Jaccarda ;] Cosine similarity to jest zwykłe policzene cosinusa kąta pomiędzy dwoma wektorami z definicji iloczynu skalarnego. Iloczyn skalarny dwóch wektorów podzielony przez iloczyn długości tych wektorów.
EM
Jeżeli w std::vector są liczby to nie ma problemu z cosine similarity ale jak wykonać te obliczenia na tekście? ASCII?
Shalom
No nie żartujmy sobie... Budujesz po prostu przestrzeń wektorową gdzie każdy wymiar jest określony przez jedno słowo w tekście. Skorzystaj z modelu BOW (link wrzucę do postu).
EM
Dziękuje ;)

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.