Witam. Mam problem z porównywaniem tekstów. Potrzebuję algorytmu, pomysłu bądź też jakichś wskazówek jak zaprojektować sprawdzanie czy dany tekst jest w x% zgodny z zadeklarowanym wcześniej wzorcem i działać z w miarę znośną złożonością. Sprowadza się to do tego że chcę zastosować go w wyszukiwarce i pomijać drobne literówki bądź błędy użytkowników. Jeśli np 90-95 procent szukanej frazy będzie zgodne z wzrocem zwrócić ten konkretny wynik. Ma mi to pomóc uniknąć deklarowania setek wzorców. Docelowo będę to pisał w javie. Myślałem o zliczaniu pojedynczych charów, ale wydaje mi się to mało trafionym pomysłem. Czy ktoś wie jak sobie z tym poradzić. Jestem otwarty na wszelkie porady/propozycje/linki.
Algorytm Levenshteina
alternatywa: długość http://en.wikipedia.org/wiki/Longest_common_subsequence_problem / liczba_znaków_wzorca
Porównuj 2 teksty, lecąc przez długość krótszego - zliczaj wystąpienie różności znaków, pod koniec dodając do wyniku różnice długości mniejszej i większej, odpowiednio formatując na %
okej... Zaraz temu zaradzę.
Liczy niezgodne znaki, czyli bez formatowania procentowego:
#include <iostream>
#include <string>
using namespace std;
#define PierwszyNapis "spartanPAGE podał niezbyt przemyślany algorytm"
#define DrugiNapis "*spartanPAGE podał niezbyt przemyślany algorytm"
#define Wyzeruj(a) for(int i = 0; i < 256; ++i) a[i] = 0;
#define ZliczZnaki(a, b) for(int i = 0; i < a.length(); ++i) \
++b[a[i]-1];
int Suma_Znakow(int* tab)
{
int licznik = 0;
for(int i = 0; i < 256; ++i)
licznik += tab[i];
return licznik;
}
int Roznica_Znakow(int* tab1, int* tab2)
{
int TablicaRoznic[256];
Wyzeruj(TablicaRoznic);
for(int i = 0; i < 256; ++i)
{
TablicaRoznic[i] = abs(int(tab1[i] - tab2[i]));
}
return Suma_Znakow(TablicaRoznic);
}
int Roznica(string s1, string s2)
{
int Znaki_w_Pierwszym[256];
Wyzeruj(Znaki_w_Pierwszym);
ZliczZnaki(s1, Znaki_w_Pierwszym);
int Znaki_w_Drugim[256];
Wyzeruj(Znaki_w_Drugim);
ZliczZnaki(s1, Znaki_w_Drugim);
int licznik_roznicy = Roznica_Znakow(Znaki_w_Pierwszym, Znaki_w_Drugim);
licznik_roznicy += abs(int(s1.length() - s2.length()));
return licznik_roznicy;
}
int main()
{
cout << Roznica(PierwszyNapis, DrugiNapis) << endl;
system("pause");
return 0;
}
Wyjście:
(jak nie zadziała zdjęcie: http://www.mediafire.com/view/?46czhmcmx7454#m5twnxm62g6li1w )
A dla literałów:
#define PierwszyNapis "anka"
#define DrugiNapis "*anka "
na wyjściu jest
3
Czyli dobrze, ponieważ nie zgadzają nam się 2 spacje i gwiazdka.
Ale szukasz tutaj bezwzględnych wzorców? Bo w przypadku wyszukiwarki to może być słaby pomysł. Co z kolejnością słów we frazie wyszukiwanej na przykład? Ja bym jednak użył podobieństwa cosinusowego (cosine similarity). Chodzi tutaj o przedstawienie tekstów w postaci wektora n-wymiarowego (gdzie n to ilość różnych tokenów "języka") i potem porównanie tych wektorów. Złożoność ma to znikomą (bo liniową) a w twoim przypadku chyba lepiej się sprawdzi.
@ Szukanie ma się odbywać wg. określonych ściśle zasad więc kolejność jest narzucona jak np. wyszukiwanie w katalogach bibliotecznych etc;)
Dziękuję za odpowiedzi, mam jeszcze jedno pytanie. W jaki sposób zaimplementować pomijanie wielkości liter.
Co chcę osiągnąć- żeby wyszukiwanie np "t" brało pod uwagę zarówno "t" jak i "T", analogicznie z innymi literami.
@Marat: poszukaj hasła SoundEx, najlepiej polską wersję (jeśli hasła mają być też polskie).
Przed poddaniem słów temu algorytmowi trzeba je znormalizować - podział słów, uppercase, konwersja/eliminacja dziwnych znaczków.