procentowa zgodność tekstów

0

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.

0

Algorytm Levenshteina

0

alternatywa: długość http://en.wikipedia.org/wiki/Longest_common_subsequence_problem / liczba_znaków_wzorca

0

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 %

0

okej... Zaraz temu zaradzę.

0

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:
user image
(jak nie zadziała zdjęcie: http://www.mediafire.com/view/?46czhmcmx7454#m5twnxm62g6li1w )

0

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.

0

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.

0

@ 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.

0

@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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1